Let S be the set of all lists (a1

Problem 11828

(American Mathematical Monthly, Vol.122, March 2015) Proposed by R. Tauraso (Italy).

Let n be a positive integer, and let z be a complex number that is not a kth root of unity for any k with 1 ≤ k ≤ n. Let S be the set of all lists (a1, . . . , an) of n nonnegative integers such that Pn

k=1kak= n. Prove that X

a∈S n

Y

k=1

1

ak!k^ak(1 − z^k)^ak =

n

Y

k=1

1 1 − z^k. For example, for n = 3 we have

1

6(1 − z)³ + 1

2(1 − z)(1 − z²)+ 1

3(1 − z³) = 1

(1 − z)(1 − z²)(1 − z³).

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

First solution. We have that

F (z, t) :=X

n≥0

tⁿ X

α1+2α2+···=n n

Y

k=1

1

αk!k^αk(1 − z^k)^αk

=

n

Y

k=1

X

α_k≥0

t^kαk α_k!k^αk(1 − z^k)^αk

= Y

k≥1

exp

 t^k k(1 − z^k)



= exp



 X

k≥1

t^k k(1 − z^k)





= exp



 X

j≥0

X

k≥1

(tz^j)^k k





=Y

j≥0

exp



 X

k≥1

(tz^j)^k k





=Y

j≥0

exp

 ln

 1

1 − tz^j



=Y

j≥0

1

1 − tz^j = 1 1 − t

Y

j≥1

1 1 − tz^j

Note that [tⁿz^N]F (z, t) is the number of integer partitions of N with at most n parts because it is known that

[tⁿz^N]Y

j≥1

1 1 − tz^j

is the number of integer partitions of N with exactly n parts. On the other side,

G(z, t) :=X

n≥0

tⁿ

n

Y

k=1

1 1 − z^k

and [tⁿz^N]G(z, t) is the number of integer partitions of N with at most n parts.

Hence F and G are equal and the identity is proved. 

Second solution. It suffices to prove that

X

σ∈π(I_n) n

Y

k=1

1 1 −Qk

j=1x_σ(j) = X

σ∈π(I_n) lσ

Y

k=1

1 1 −Q

j∈C_kxj

where σ ∈ π(In) is a permutation of In= {1, 2, . . . , n} which can be written as a product of disjoint cycles C1, C2, . . . , Cl_σ. The required identity follows by letting xj= z for j = 1, . . . , n.

We note that

n

Y

k=1

1 1 −Qk

j=1x_σ(j) = X

a₁≥a₂≥···≥a_n≥0 n

Y

j=1

x^a_σ(j)^j ,

and

l_σ

Y

k=1

1 1 −Q

j∈C_kx_j = X

a₁≥0,a₂≥0,··· ,a_lσ≥0 l_σ

Y

k=1



 Y

j∈C_k

xj





a_k

.

Hence, if a1= a2= · · · = an then

[x^a₁¹x^a₂²· · · x^a_nⁿ] X

σ∈π(In) n

Y

k=1

1 1 −Qk

j=1x_σ(j) = n! = [x^a₁¹x₂^a2· · · x^a_nⁿ] X

σ∈π(In) l_σ

Y

k=1

1 1 −Q

j∈C_kx_j. In general,

[x^a₁¹x^a₂²· · · x^a_nⁿ] X

σ∈π(I_n) n

Y

k=1

1 1 −Qk

j=1x_σ(j) =Y

i≥0

(|Ai|!)

where Ai= {j : aj= i} for i ≥ 0. By the above remark,

|Ai|! = [Y

j∈Ai

x^a_j^j] X

σ_i∈π(Ai) l_σi

Y

k=1

1 1 −Q

j∈C_k,ixj

.

Therefore

Y

i≥0

(|Ai|!) =Y

i≥0

[Y

j∈Ai

x^a_j^j] X

σ_i∈π(Ai) l_σi

Y

k=1

1 1 −Q

j∈C_k,ixj

= [x^a₁¹x^a₂²· · · x^a_nⁿ] X

σ∈π(I_n) l_σ

Y

k=1

1 1 −Q

j∈Ckxj

where σ is the product of σi ∈ π(Ai) for i ≥ 0.