Problem 11237
(American Mathematical Monthly, Vol.113, August-September 2006) Proposed by E. Deutsch (USA).
Prove that the number of2s occurring in all partitions of n is equal to the number of singletons occurring in all partitions of n −1, where a singleton in a partition is a part occurring once.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
If p(n) is the number of integer partitions of n then the generating function of this sequence is
P(z) =
∞
X
n=0
p(n)zn=
∞
Y
n=1
1
(1 − zn) = 1 + z + 2z2+ 3z3+ 5z4+ 7z5+ 11z6+ 15z7+ 22z8+ o(z8).
In order to compute the number of 2s we introduce a parameter t 1 − z2
1 − tz2 ·P(z) then the generating function which counts the 2s is
T(z) =
∞
X
n=0
t(n)zn= d dt
1 − z2 1 − tz2 ·P(z)
t=1
= z2
1 − z2·P(z) = z2+z3+3z4+4z5+8z6+11z7+19z8+o(z8).
On the other hand, the generating function which counts the singletons that are equal to n ≥ 1 is zn(1 − zn) · P (z)
therefore the generating function which counts all the singletons is
S(z) =
∞
X
n=0
s(n)zn=
∞
X
n=1
zn(1 − zn)
!
·P(z) =
z
1 − z− z2 1 − z2
·P(z) = z
1 − z2 ·P(z).
Since T (z) = zS(z) then
t(n) = s(n − 1).
