12
CHU Wenchang and DI CLAUDIO Leontina
B1.1. Partitions with parts in S. We first investigate the generating
functions of partitions with parts in S, where the basic set S ⊆ N with N
being the set of natural numbers.
Let S be a set of natural numbers and p(n|S) denote the number of partitions
of n into elements of S (or in other words, the parts of partitions belong to
S). Then the univariate generating function is given by
∞
X
p(n|S) qn =
n=0
Y
k∈S
1
.
1 − qk
(B1.1a)
If we denote further by p` (n|S) the number of partitions with exactly `-parts
in S, then the bivariate generating function is
X
Y
1
p` (n|S) x` qn =
.
(B1.1b)
1 − xqk
`,n≥0
k∈S
Proof. For |q| < 1, we can expand the right member of the equation
(B1.1a) according to the geometric series
Y
k∈S
1
1 − qk
=
∞
Y X
qkmk =
k∈S mk =0
X
q
P
k∈S
kmk
Extracting the coefficient of qn from both sides, we obtain
Y 1
X P
X
n
k∈S kmk =
[qn]
=
[q
]
q
1 − qk
P
mk ≥0
k∈S
k∈S
.
mk ≥0
k∈S
1.
k∈S kmk =n
mk ≥0: k∈S
The last sum is equal to the number of solutions of the Diophantine equation
X
kmk = n
k∈S
which enumerates the partitions 1m1 , 2m2 , · · · , nmn of n into parts in S.
This completes the proof of (B1.1a). The bivariate generating function
(B1.1b) can be verified similarly.
In fact, consider the formal power series expansion
Y
k∈S
1
1 − xqk
=
∞
Y X
k∈S mk =0
xmk qkmk =
X
mk ≥0
k∈S
x
P
k∈S
mk
q
P
k∈S
kmk