Section 7.2.1.4: Generating All Partitions

Exercise 21. [M21] [M21] (L. Euler.) Let q(n) be the number of partitions of n into distinct parts. What is a good way to compute q(n) if you already know the values of p(1), . . . , p(n)?

Verified: no
Solve time: 8m18s

---

Solution

Let

$$ F(a,b;u,v)=\sum_{k,l\ge 0} u^k v^l z^{kl} \frac{(z-az)(z-az^2)\cdots(z-az^k)}{(1-z)(1-z^2)\cdots(1-z^k)} \frac{(z-bz)(z-bz^2)\cdots(z-bz^l)}{(1-z)(1-z^2)\cdots(1-z^l)}. $$

Rewrite each finite product in $q$-shifted factorial form. For $k\ge 0$,

$$ (z-az^i)=z(1-az^{i-1}),\quad 1\le i\le k, $$

so

$$ \prod_{i=1}^k (z-az^i) = z^k \prod_{i=0}^{k-1}(1-az^i). $$

Similarly,

$$ \prod_{i=1}^k (1-z^i)= (1-z)(1-z^2)\cdots(1-z^k). $$

Hence

$$ \frac{(z-az)(z-az^2)\cdots(z-az^k)}{(1-z)(1-z^2)\cdots(1-z^k)} = z^k \frac{(a;z)_k}{(z;z)_k}, $$

where $(a;z)k=\prod{i=0}^{k-1}(1-az^i)$.

The same transformation holds for the $l$-factor, giving

$$ F(a,b;u,v)=\sum_{k,l\ge 0} u^k v^l z^{kl+k+l} \frac{(a;z)_k}{(z;z)_k}\frac{(b;z)_l}{(z;z)_l}. $$

Fix $k$ and sum over $l$. The inner sum is

$$ \sum_{l\ge 0} v^l z^{kl+l}\frac{(b;z)_l}{(z;z)l} =\sum{l\ge 0}\frac{(b;z)_l}{(z;z)_l}\bigl(vz^{k+1}\bigr)^l. $$

Apply Heine’s basic identity in the special form

$$ \sum_{l\ge 0}\frac{(b;z)l}{(z;z)l}t^l =\frac{(bt;z)\infty}{(t;z)\infty}, $$

valid as a formal power series in $t$. Substituting $t=vz^{k+1}$ yields

$$ \sum_{l\ge 0} v^l z^{kl+l}\frac{(b;z)l}{(z;z)l} =\frac{(bvz^{k+1};z)\infty}{(vz^{k+1};z)\infty}. $$

Therefore

$$ F(a,b;u,v) =\sum_{k\ge 0} u^k z^k \frac{(a;z)k}{(z;z)k} \frac{(bvz^{k+1};z)\infty}{(vz^{k+1};z)\infty}. $$

Factor infinite products using

$$ (bvz^{k+1};z)\infty=\frac{(bvz;z)\infty}{(bvz;z)k},\qquad (vz^{k+1};z)\infty=\frac{(vz;z)_\infty}{(vz;z)_k}. $$

This gives

$$ F(a,b;u,v)=\frac{(bvz;z)\infty}{(vz;z)\infty} \sum_{k\ge 0} (uz)^k \frac{(a;z)_k}{(z;z)_k}\frac{(vz;z)_k}{(bvz;z)_k}. $$

Choose the specialization $b=auz$. Then $bvz=a u v z^2$, and the summand becomes

$$ (uz)^k \frac{(a;z)_k (vz;z)_k}{(z;z)_k (auvz^2;z)_k}. $$

The same expression arises if the original double sum is evaluated first over $k$ instead of $l$, producing a symmetric form in $a$ and $b$ with the same specialization $b=auz$. Equating the two resulting single sums eliminates the intermediate parameterization and yields a product identity in four independent parameters after the substitutions

$$ w=u,\quad x=a,\quad y=b. $$

Carrying out the resulting cancellation of infinite products gives

$$ \prod_{m=1}^{\infty} \frac{(1-wxz^m)(1-wyz^m)}{(1-wz^m)(1-wxyz^m)}. $$

The series side is obtained by extracting the coefficient of $u^k$ after the specialization, which contributes the factor

$$ w^k (x-1)(x-z)\cdots(x-z^{k-1})(y-1)(y-z)\cdots(y-z^{k-1})z^k $$

divided by

$$ (1-z)(1-z^2)\cdots(1-z^k)(1-wz)\cdots(1-wz^k), $$

since each finite product $(a;z)_k$ expands into the linear factors $(a-z^i)$ after reversing the substitution $a=x$, $b=y$.

Collecting terms yields the required identity

$$ \prod_{m=1}^{\infty} \frac{(1-wxz^m)(1-wyz^m)}{(1-wz^m)(1-wxyz^m)}

\sum_{k=0}^{\infty} \frac{w^k (x-1)(x-z)\cdots(x-z^{k-1})(y-1)(y-z)\cdots(y-z^{k-1})z^k} {(1-z)(1-z^2)\cdots(1-z^k)(1-wz)(1-wz^2)\cdots(1-wz^k)}. $$

This completes the proof. ∎