If $p'_A(n)$ denotes the number of partitions of $n$ subject to some some set of restrictions $A$, the ordinary generating function for the sequence $\{p'_A(n)\}_{n\geq 0}$ is defined to be \[ A(q)=\sum_{n=0}^{\infty}p'_A(n)q^n. \] One reason generating functions are of interest is that they can be used to give analytic proofs of partition identities.

For this and other reasons, it is of interest to find alternative expressions for the generating function $A(q)$. Euler derived an infinite product expression for the generating function for the sequence $p(n)$, the number of unrestricted partitions of $n$ (where $p(0)$ is defined to have the value 1): \begin{equation}\label{pngen1} \sum_{n=0}^{\infty}p(n)q^n = \frac{1}{(q;q)_{\infty}}. \end{equation} Informally, this can be seen to follow from expanding each factor in the infinite product on the right side of \eqref{pngen1} as a geometric series. \begin{align}\label{pngen2} \frac{1}{(q;q)_{\infty}}&=\frac{1}{\prod_{k=1}^{\infty}(1-q^k)}\\ &=\prod_{k=1}^{\infty}(1+q^{1.k}+q^{2.k}+q^{3.k}+\dots + +q^{j.k}+ \dots)\notag\\ &=\sum_{n_1=0}^{\infty}\sum_{n_2=0}^{\infty}\sum_{n_3=0}^{\infty}\dots \sum_{n_k=0}^{\infty}\dots q^{n_1.1+n_2.2+n_3.3+\dots +n_k.k+\dots}.\notag \end{align} For each positive integer $n$, each occurrence of the term $q^n$ will be of the form $q^{n_1.1+n_2.2+n_3.3+\dots +n_k.k}$, for some non-negative integers $n_1,n_2, \dots , n_k$, with $k\leq n$. This exponent may be considered as a partition of $n$ consisting of $n_1$ parts of size 1, $n_2$ parts of size 2, $\dots$, $n_k$ parts of size $k$. Each occurrence of $q^n$ arises in this way from a partition of $n$, and each partition of $n$ occurs as an exponent in some term $q^n$. Hence, after collecting all powers of $q^n$ together, the coefficient of $q^n$ in the expanded multi-series at \eqref{pngen2} is $p(n)$. This argument may be made rigorous by using the fact that $p(n)$ is the coefficient of $q^n$ in \[ \frac{1}{(q;q)_n} = \frac{1}{\prod_{k=1}^{n}(1-q^k)}, \] since a partition of $n$ cannot have any part that exceeds $n$.

By similar reasoning, it is possible to prove the following general results.

Theorem. Let $S$ be any set (finite or infinite) of positive integers. Let $p(S,m,n)$ denote the number of partitions of $n$ consisting of exactly $m$ parts (counting repetitions) from $S$, and let $Q(S,m,n)$ denote the number of partitions of $n$ consisting of exactly $m$ distinct parts from $S$. Then \begin{align}\label{pngen3} \sum_{n=0}^{\infty}\sum_{m=0}^{\infty}p(S,m,n)z^mq^n&=\frac{1}{\prod_{k\in S}(1-zq^k)},\\ \sum_{n=0}^{\infty}\sum_{m=0}^{\infty}Q(S,m,n)z^mq^n&=\prod_{k\in S}(1+zq^k). \label{pngen4} \end{align} Partition identities may be proved by showing that two generating functions are equal, and analytic identities may be proved by exhibiting bijections between the two sets of partitions for which the analytic functions are generating functions.

Back to the main Partitions page