Partitions of Integers

We work in the ring of formal power series $\mathbb{Z}[[x]]$, where an infinite product $\prod_{k \in S}(1-x^k)^{-1}$ is well-defined as a formal power series provided that for every fixed exponent $n$, only finitely many factors contribute a nonzero coefficient to $x^n$ — a mild convergence condition automatically satisfied here since the factor $(1-x^k)^{-1} = 1 + x^k + x^{2k} + \cdots$ contributes nothing below degree $k$, so only the factors with $k \le n$ affect the coefficient of $x^n$. Hence the infinite product is really, for each fixed $n$, a finite product computation, and the identity should be read coefficientwise.

Step 1: Expand each factor. For each $k \in S$, geometric series in the formal power series ring gives

where $m_k$ is a formal placeholder we interpret as "the number of times part $k$ is used." This is a valid formal power series identity because $(1-x^k)\sum_{m_k \ge 0} x^{km_k} = 1$, checked by multiplying out and observing all terms telescope except the constant term $1$.

Step 2: Multiply the factors and interpret the product. By definition of the product of formal power series,

where the sum on the right ranges over all functions $(m_k)_{k\in S}$ from $S$ to $\mathbb{Z}_{\ge 0}$ that are eventually zero (equivalently, finitely supported, i.e. $m_k = 0$ for all but finitely many $k$) — this finiteness is forced because we are forming a formal power series, and any nonzero coefficient of $x^n$ can only receive contributions from choices with $\sum k m_k = n < \infty$, hence only finitely many $m_k$ can be nonzero in any single contributing term. This finite-support condition is precisely what makes the infinite product converge formally, matching Step 1's factor-by-factor validity.

Step 3: Identify the coefficient of $x^n$. By Step 2, the coefficient of $x^n$ in $\prod_{k\in S}(1-x^k)^{-1}$ equals the number of finitely-supported functions $(m_k)_{k \in S}$ with $\sum_{k \in S} k\, m_k = n$.

Step 4: Bijection with partitions. There is a bijection between such functions $(m_k)_{k\in S}$ and partitions of $n$ into parts from $S$: given $(m_k)$, form the partition consisting of $m_k$ copies of the part $k$ for each $k \in S$ with $m_k > 0$, arranged in non-increasing order; conversely, given a partition of $n$ into parts from $S$, let $m_k$ be the number of times $k$ occurs as a part. These two maps are mutually inverse (both simply record "multiplicity of each part size"), so they establish a bijection between the finitely-supported solutions of $\sum k m_k = n$ and partitions of $n$ using parts from $S$.

Conclusion. Combining Steps 3 and 4, the coefficient of $x^n$ in $\prod_{k \in S} (1-x^k)^{-1}$ equals exactly $p_S(n)$, the number of partitions of $n$ with parts in $S$, for every $n \ge 0$. Since two formal power series with equal coefficients at every degree are equal, this proves

Taking $S = \mathbb{Z}_{>0}$ gives the stated formula for $P(x)$. $\blacksquare$

The proof mirrors the previous theorem, but each part size $k$ may now be used $0$ or $1$ times only, so its individual generating function is $1 + x^k$ (choose "not included," contributing $x^0$, or "included once," contributing $x^k$) rather than the full geometric series $\sum_m x^{km}$. Exactly as in Step 2 above, multiplying these factors over all $k \ge 1$ and extracting the coefficient of $x^n$ counts finitely-supported choice functions $\epsilon: \mathbb{Z}_{>0} \to \{0,1\}$ with $\sum_k k\,\epsilon(k) = n$, which biject with partitions of $n$ into distinct parts (namely the parts $k$ with $\epsilon(k)=1$) by the identical multiplicity-recording argument. $\blacksquare$

We give two independent proofs: an algebraic one via generating functions (in the spirit of the results above), and an explicit bijective one, since the theorem is a flagship example of both techniques working in harmony.

Proof 1 (generating functions). Let $\mathrm{Odd} = \{1,3,5,7,\dots\}$. By the first theorem applied with $S = \mathrm{Odd}$, the generating function for partitions into odd parts is

By the lemma, the generating function for partitions into distinct parts is

We show $O(x) = Q(x)$ as formal power series. First factor each term $1+x^k$ using the algebraic identity $1+x^k = \frac{1-x^{2k}}{1-x^k}$ (valid since $(1-x^k)(1+x^k) = 1-x^{2k}$ in any commutative ring, in particular $\mathbb{Z}[[x]]$). Hence

Consider the truncated product $Q_N(x) = \prod_{k=1}^N \frac{1-x^{2k}}{1-x^k}$. Split the denominator's index set $\{1,\dots,N\}$ into odd and even indices:

Therefore

The factors $\prod_{j=1}^{\lfloor N/2 \rfloor}(1-x^{2j})$ appearing in the denominator cancel against the matching initial segment of $\prod_{j=1}^N(1-x^{2j})$ in the numerator, leaving

As formal power series, we take $N \to \infty$ coefficientwise: fix any degree $d$. Once $N$ is large enough that $2(\lfloor N/2\rfloor+1) > d$, every factor in the remaining numerator product $\prod_{j=\lfloor N/2\rfloor+1}^N(1-x^{2j})$ contributes only terms of degree $> d$ beyond the constant term $1$, so this numerator product is $\equiv 1 \pmod {x^{d+1}}$. Hence, modulo $x^{d+1}$,

and letting $N \to \infty$ (all sufficiently large odd $k > d$ also become irrelevant mod $x^{d+1}$) gives $Q(x) \equiv O(x) \pmod{x^{d+1}}$. Since $d$ was arbitrary, every coefficient of $Q(x)$ equals the corresponding coefficient of $O(x)$, i.e. $Q(x) = O(x)$ as formal power series. By the theorem and lemma above, the coefficients of $Q(x)$ and $O(x)$ are exactly $q(n)$ and (the odd-part count) respectively, so these two counting functions agree for every $n$.

Proof 2 (explicit bijection, Glaisher's map). Given a partition $\lambda$ of $n$ into odd parts, write each distinct odd value $v$ occurring with multiplicity $m_v$ using its binary expansion $m_v = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_r}$ (distinct powers of $2$, guaranteed uniquely by binary representation). Replace the $m_v$ copies of $v$ by the parts $2^{a_1} v, 2^{a_2} v, \dots, 2^{a_r} v$. These new parts sum to $m_v \cdot v$, so the total sum $n$ is preserved. All resulting parts across all distinct odd $v$ are pairwise distinct: two parts $2^a v$ and $2^b w$ (for odd $v \ne w$ or $a \ne b$) coincide only if $v=w$ and $a=b$ by uniqueness of factoring an integer into an odd part times a power of $2$ (every positive integer $m$ factors uniquely as $m = 2^a v$ with $v$ odd, $a \ge 0$). Hence this map sends a partition into odd parts to a partition into distinct parts. Conversely, given a partition $\mu$ into distinct parts, write each part $\mu_i$ uniquely as $\mu_i = 2^{a_i} v_i$ with $v_i$ odd (existence and uniqueness of this factorization is the standard fact that every positive integer has a unique odd part after removing all factors of $2$). Group parts of $\mu$ by their odd component $v$, and for each such $v$, if the powers of two occurring are $2^{a_1}, \dots, 2^{a_r}$ (necessarily distinct since the $\mu_i = 2^{a_i}v$ are themselves distinct for fixed $v$), replace this group by $m_v = 2^{a_1}+\cdots+2^{a_r}$ copies of the odd part $v$. This produces a partition into odd parts summing to the same $n$. These two constructions are mutually inverse: starting from an odd-parts partition, splitting each multiplicity into binary powers and then regrouping by odd value exactly reconstructs the original multiplicities, since binary representation is unique; starting from a distinct-parts partition, factoring out odd cores and regrouping, then re-splitting via binary expansion of the resulting multiplicity, recovers the original distinct parts, again by uniqueness of binary representation. Hence Glaisher's map is a bijection between partitions of $n$ into odd parts and partitions of $n$ into distinct parts, for every $n$, proving the theorem constructively. $\blacksquare$