Problem 11464
(American Mathematical Monthly, Vol.116, November 2009) Proposed by D. Beckwith (USA).
Let a(n) be the number of ways to place n identical balls into a sequence of urns U1, U2, . . . in such a way that U1receives at least one ball, and while any balls remain, each successive urn receives at least as many balls as in all the previous urns combined. Let b(n) denote the number of partitions of n into powers of2, with repeated powers allowed. Prove that a(n) = b(n) for all n ∈ N.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
The generating function of the sequence {bn} is
B(z) = Y∞ k=0
1 1 − z2k. Let ak(n) be the number of ways we can put n balls into k urns.
Let ui be the number of balls which goes in urn Ui for i = 1, . . . , k, then u1 = 1 + x1
u2 = u1+ x2= 1 + x1+ x2
u3 = u1+ u2+ x3= 2 + 2x1+ x2+ x3
· · ·
uk = uk−1+ xk = 2k−2+ 2k−2x1+ 2k−3x2+ · · · + 2xk−2+ xk−1+ xk
with xi≥ 0. Hence for n, k ≥ 1
n= u1+ u2+ u3+ · · · + uk = 2k−1+ 2k−1x1+ 2k−2x2+ · · · + 4xk−2+ 2xk−1+ xk,
and X
n≥1
ak(n)zn= X
x1,...,xk≥0
zu1+···+uk= z2k−1
(1 − z)(1 − z2)(1 − z4) · · · (1 − z2k−1). Since a(n) =P
k≥1ak(n), the generating function of the sequence {an} is A(z) = 1 +X
n≥1
a(n)zn= 1 +X
k≥1
z2k−1
(1 − z)(1 − z2)(1 − z4) · · · (1 − z2k−1). Moreover, it can be verified by induction that for any positive integer N
1 + XN k=1
z2k−1
(1 − z)(1 − z2)(1 − z4) · · · (1 − z2k−1)=
N −1Y
k=0
1 1 − z2k.
Hence A(z) = B(z) and it follows that a(n) = b(n) for all n ∈ N.
