The Composition Enumeration Reciprocity Theorem: The Number of Compositions of n Into Parts k ( mod a) (k < a) Equals The Number of Compositions of n + a − k Into Parts a ( mod k) that are ≥ a

Doron ZEILBERGER^{1}

Theorem: See title .

Proof: Given a composition (k +an_{1}, k +an_{2}, …, k +an_{r}) of n, construct the word, in the alphabet {k, a}, w := ka^{n_{1}}ka^{n_{2}} … ka^{n_{r}} (whose sum is n). Now replace the first letter (k) of w by a, getting a word w′ := aa^{n_{1}}ka^{n_{2}} … ka^{n_{r}}, still in the alphabet {k, a} but whose sum is n + a − k, and now parse it as w′ = ak^{m_{1}}ak^{m_{2}} … ak^{m_{s}} that gives you the following composition of n + a − k into parts that are a(mod k) and ≥ a:

(a + m_{1}k, …, a + m_{s}k) .

Remark: The case k = 1, a = 2 (with essentially the same bijective proof) was done in Drew Sills’ nice article Compositions, Parititions, and Fibonacci Numbers, that appeared in the Fibonacci Quarterly 40 (2011), 348-354, available on-line at

http://math.georgiasouthern.edu/~asills/comps/CompositionsFQRev.pdf .

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/ . Feb. 28, 2012. Supported in part by the NSF. Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger.