TY - JOUR

T1 - Euler's partition theorem and the combinatorics of ℓ-sequences

AU - Savage, Carla D.

AU - Yee, Ae Ja

N1 - Funding Information:
E-mail addresses: [email protected] (C.D. Savage), [email protected] (A.J. Yee). 1 Research supported in part by NSF grant DMS-0300034. 2 The author is an Alfred P. Sloan Research Fellow.

PY - 2008/8

Y1 - 2008/8

N2 - Euler's partition theorem states that the number of partitions of an integer N into odd parts is equal to the number of partitions of N in which the ratio of successive parts is greater than 1. It was shown by Bousquet-Mélou and Eriksson in [M. Bousquet-Mélou, K. Eriksson, Lecture hall partitions II, Ramanujan J. 1 (2) (1997) 165-185] that a similar result holds when "odd parts" is replaced by "parts that are sums of successive terms of an ℓ-sequence" and the ratio "1" is replaced by a root of the characteristic polynomial of the ℓ-sequence. This generalization of Euler's theorem is intrinsically different from the many others that have appeared, as it involves a family of partitions constrained by the ratio of successive parts. In this paper, we provide a surprisingly simple bijection for this result, a question suggested by Richard Stanley. In fact, we give a parametrized family of bijections, that include, as special cases, Sylvester's bijection and a bijection for the lecture hall theorem. We introduce Sylvester diagrams as a way to visualize these bijections and deduce their properties. In proving the bijections, we uncover the intrinsic role played by the combinatorics of ℓ-sequences and use this structure to give a combinatorial characterization of the partitions defined by the ratio constraint. Several open questions suggested by this work are described.

AB - Euler's partition theorem states that the number of partitions of an integer N into odd parts is equal to the number of partitions of N in which the ratio of successive parts is greater than 1. It was shown by Bousquet-Mélou and Eriksson in [M. Bousquet-Mélou, K. Eriksson, Lecture hall partitions II, Ramanujan J. 1 (2) (1997) 165-185] that a similar result holds when "odd parts" is replaced by "parts that are sums of successive terms of an ℓ-sequence" and the ratio "1" is replaced by a root of the characteristic polynomial of the ℓ-sequence. This generalization of Euler's theorem is intrinsically different from the many others that have appeared, as it involves a family of partitions constrained by the ratio of successive parts. In this paper, we provide a surprisingly simple bijection for this result, a question suggested by Richard Stanley. In fact, we give a parametrized family of bijections, that include, as special cases, Sylvester's bijection and a bijection for the lecture hall theorem. We introduce Sylvester diagrams as a way to visualize these bijections and deduce their properties. In proving the bijections, we uncover the intrinsic role played by the combinatorics of ℓ-sequences and use this structure to give a combinatorial characterization of the partitions defined by the ratio constraint. Several open questions suggested by this work are described.

UR - http://www.scopus.com/inward/record.url?scp=44149115203&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=44149115203&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2007.11.006

DO - 10.1016/j.jcta.2007.11.006

M3 - Article

AN - SCOPUS:44149115203

SN - 0097-3165

VL - 115

SP - 967

EP - 996

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

IS - 6

ER -