14
CHU Wenchang and DI CLAUDIO Leontina
The last sum enumerates the solutions of Diophantine equation
X
kmk = n with mk = 0, 1
k∈S
which is equal to Q(n|S), the number of partitions of n into distinct parts
in S.
Instead, we can proceed similarly for the second formula as follows:
Y
(1 + xqk ) =
Y X
k∈S mk =0,1
k∈S
X
xmk qkmk =
x
P
k∈S
mk
q
P
k∈S
kmk
.
mk =0,1
k∈S
The coefficient of x` qn leads us to the following
[x`qn]
Y
(1 + xqk ) =
[x`qn ]
X
x
P
k∈S
mk
q
P
k∈S
kmk
mk =0,1
k∈S
k∈S
=
X
P
o
Pk∈S mk = `
k∈S kmk = n
1.
mk =0,1: k∈S
The last sum equals the number of solutions of the system of Diophantine
equations
X
k∈S
X
k∈S
mk = `
kmk = n
with mk = 0, 1
which correspond to the partitions 1m1 , 2m2 , · · · , nmn of n with exactly
` distinct parts in S.