The integer partition function \( p(n) \) counts the number of ways of writing a positive integer \( n \) as an unordered sum of positive integers. Despite the simplicity of its definition, \( p(n) \) has fascinated mathematicians for three centuries and generated some of the most beautiful results in number theory. In this lesson, we build the combinatorial and analytic foundations: Ferrers diagrams, Euler’s generating function, and the pentagonal number theorem.
What Is a Partition?
A partition of a positive integer \( n \) is a way of writing \( n \) as a sum of positive integers, where the order of the summands does not matter. Each summand is called a part. The number of distinct partitions of \( n \) is denoted \( p(n) \). By convention, \( p(0) = 1 \) (the empty partition).
Two representations that differ only in the order of their parts are considered identical. Thus \( 3 + 1 + 1 \) and \( 1 + 3 + 1 \) and \( 1 + 1 + 3 \) all represent the same partition of 5.
Partitions of Small Numbers
The partitions of 4 are:
$$ \begin{aligned} 4 &= 4\\ 4 &= 3 + 1\\ 4 &= 2 + 2\\ 4 &= 2 + 1 + 1\\ 4 &= 1 + 1 + 1 + 1 \end{aligned} $$
Hence \( p(4) = 5 \).
The partitions of 5 are: \( 5 \), \( 4+1 \), \( 3+2 \), \( 3+1+1 \), \( 2+2+1 \), \( 2+1+1+1 \), \( 1+1+1+1+1 \). Hence \( p(5) = 7 \).
For small values we have:
- \( n \): \( p(n) \) | 0: 1 | 1: 1 | 2: 2 | 3: 3 | 4: 5 | 5: 7 | 6: 11 | 7: 15 | 8: 22 | 9: 30 | 10: 42 | 11: 56
The values grow quickly: \( p(100) = 190{,}569{,}292 \) and \( p(200) = 3{,}972{,}999{,}029{,}388 \).
Ferrers and Young Diagrams
A partition \( \lambda = (\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k > 0) \) with \( \sum \lambda_i = n \) can be visualized as a Ferrers diagram: an array of dots in which the \( i \)-th row contains \( \lambda_i \) dots. Equivalently, one may use boxes instead of dots; the resulting shape is called a Young diagram.
Young diagrams provide a uniform language for many combinatorial operations. They are also the foundation of the representation theory of the symmetric group, the Robinson-Schensted-Knuth correspondence, and much of algebraic combinatorics.
Conjugate Partitions
Given a partition \( \lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k) \), the conjugate partition \( \lambda’ = (\lambda_1′, \lambda_2′, \ldots) \) is defined by
$$ \lambda_j' = \#\{i : \lambda_i \geq j\}, $$
i.e., \( \lambda_j’ \) equals the length of the \( j \)-th column of the Young diagram.
Geometrically, the Young diagram of \( \lambda’ \) is obtained by reflecting the Young diagram of \( \lambda \) across its main diagonal.
For example, the conjugate of \( (5, 3, 3, 1) \) is \( (4, 3, 3, 1, 1) \). Both are partitions of 12.
Conjugation has an important self-duality property: \( (\lambda’)’ = \lambda \). It also transforms partitions into distinct parts into partitions into odd parts, as we see next.
Distinct Parts and Odd Parts: Euler’s Bijection
Let \( Q(n) \) denote the number of partitions of \( n \) into distinct parts (no part repeated), and \( O(n) \) the number of partitions of \( n \) into odd parts (each part is odd, repetitions allowed).
Theorem (Euler, c. 1748). For all \( n \geq 0 \), \( Q(n) = O(n) \).
Proof via generating functions. The generating function for partitions into distinct parts is
$$ \sum_{n=0}^{\infty} Q(n)\,q^n = \prod_{k=1}^{\infty}(1 + q^k). $$
The generating function for partitions into odd parts is
$$ \sum_{n=0}^{\infty} O(n)\,q^n = \prod_{\substack{k=1\\k \text{ odd}}}^{\infty} \frac{1}{1-q^k}. $$
Using the factorization \( 1 – q^{2k} = (1 – q^k)(1 + q^k) \):
$$ \prod_{k=1}^{\infty}(1 + q^k) = \prod_{k=1}^{\infty}\frac{1 – q^{2k}}{1 – q^k} = \frac{\prod_{k=1}^{\infty}(1 – q^{2k})}{\prod_{k=1}^{\infty}(1 – q^k)}. $$
The numerator product cancels the even-\( k \) terms of the denominator, leaving exactly the odd-\( k \) terms:
$$ = \frac{1}{\prod_{\substack{k=1\\k \text{ odd}}}^{\infty}(1 – q^k)} = \sum_{n=0}^{\infty} O(n)\,q^n. \quad \blacksquare $$
There is also a beautiful bijective proof: to convert a partition into distinct parts into one into odd parts, repeatedly replace each even part \( 2^a m \) (with \( m \) odd) by \( 2^a \) copies of the part \( m \). The inverse operation merges pairs of equal odd parts.
For \( n = 9 \), the distinct-parts partitions are: \( 9 \), \( 8+1 \), \( 7+2 \), \( 6+3 \), \( 6+2+1 \), \( 5+4 \), \( 5+3+1 \), \( 4+3+2 \). That gives \( Q(9) = 8 \). The odd-parts partitions of 9 also number 8.
Euler’s Generating Function
The central tool for studying \( p(n) \) is its generating function.
Theorem (Euler’s Generating Function). For \( |q| < 1 \):
$$ \sum_{n=0}^{\infty} p(n)\,q^n = \prod_{k=1}^{\infty} \frac{1}{1 – q^k}. $$
Proof. Expand each factor as a geometric series:
$$ \frac{1}{1 – q^k} = \sum_{m_k=0}^{\infty} q^{k\,m_k}, \qquad |q|<1. $$
Multiplying over all \( k \geq 1 \) (the product converges absolutely for \( |q| < 1 \)) gives
$$ \prod_{k=1}^{\infty}\frac{1}{1-q^k} = \prod_{k=1}^{\infty}\sum_{m_k=0}^{\infty} q^{k\,m_k} = \sum_{m_1, m_2, m_3, \ldots \geq 0} q^{m_1 + 2m_2 + 3m_3 + \cdots}. $$
A tuple \( (m_1, m_2, m_3, \ldots) \) with \( m_k \geq 0 \) and \( \sum_{k} k\,m_k = n \) encodes a partition of \( n \) in which part \( k \) appears \( m_k \) times. The coefficient of \( q^n \) in the product therefore counts exactly the number of such tuples, which equals \( p(n) \). \( \blacksquare \)
Important: The function \( F(q) = \prod_{k=1}^{\infty}(1-q^k)^{-1} \) is among the most important power series in combinatorics and number theory. Its reciprocal \( \prod_{k=1}^{\infty}(1-q^k) \) is essentially the Dedekind eta function \( \eta(\tau) = e^{\pi i\tau/12}\prod_{k=1}^{\infty}(1-e^{2\pi i k\tau}) \), a modular form of weight \( \frac{1}{2} \), and encodes deep arithmetic symmetries.
Restricted Partitions
The generating function can be factored to study restricted partitions:
$$ \sum_{n \geq 0} p_k(n)\,q^n = \prod_{j=1}^{k}\frac{1}{1-q^j}, $$
where \( p_k(n) \) counts partitions of \( n \) into parts of size at most \( k \). The Gaussian binomial coefficient \( \binom{m}{k}_q \) counts \( k \)-element subsets of an \( m \)-element set over \( \mathbb{F}_q \), and also governs the generating function for partitions fitting inside a \( k \times (m-k) \) rectangle.
The Pentagonal Number Theorem
The reciprocal of Euler’s product has a beautiful closed form.
The generalized pentagonal numbers are the integers
$$ \omega(k) = \frac{k(3k-1)}{2}, \qquad k = 0, \pm 1, \pm 2, \pm 3, \ldots $$
giving the sequence \( 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, \ldots \)
Theorem (Euler’s Pentagonal Number Theorem).
$$ \prod_{k=1}^{\infty}(1 – q^k) = \sum_{k=-\infty}^{\infty}(-1)^k\,q^{k(3k-1)/2} = 1 – q – q^2 + q^5 + q^7 – q^{12} – q^{15} + q^{22} + q^{26} – \cdots $$
The proof uses a beautiful combinatorial cancellation discovered by Franklin (1881): partitions with an even number of “hooks” and those with an odd number cancel in pairs, except at the pentagonal numbers where no cancellation occurs.
Franklin’s Bijective Proof (Outline)
Given a partition \( \lambda \), let \( s(\lambda) \) be the number of parts in the smallest run at the top (the “slope”) and \( b(\lambda) \) the length of the bottom row. Define a sign \( (-1)^{b(\lambda)} \). When \( s(\lambda) \neq b(\lambda) \) and \( s(\lambda) \neq b(\lambda) + 1 \), one can construct an involution that toggles the sign by moving dots between the slope and the bottom row. The fixed points of this involution are precisely those with shapes \( \omega(k) \) for \( k = 1, 2, 3, \ldots \), and the sign contributed is \( (-1)^k \).
Euler’s Recurrence for p(n)
The Pentagonal Number Theorem immediately yields a recurrence. Write
$$ \left(\sum_{n=0}^{\infty} p(n)\,q^n\right) \cdot \left(\sum_{k=-\infty}^{\infty}(-1)^k q^{k(3k-1)/2}\right) = 1. $$
Equating coefficients of \( q^n \) for \( n \geq 1 \):
Theorem (Euler’s Recurrence). For \( n \geq 1 \):
$$ \begin{aligned} p(n) &= p(n-1) + p(n-2) – p(n-5) – p(n-7) + p(n-12) + p(n-15) – \cdots\\ &= \sum_{\substack{k \neq 0 \\ \omega(k) \leq n}} (-1)^{k+1}\,p\bigl(n – \omega(k)\bigr), \end{aligned} $$
where \( p(m) = 0 \) for \( m < 0 \) and \( p(0) = 1 \).
Computing p(10) = 42
$$ \begin{aligned} p(10) &= p(9) + p(8) – p(5) – p(3) + p(-2) + \cdots\\ &= 30 + 22 – 7 – 3 + 0 + \cdots = 42. \checkmark \end{aligned} $$
This recurrence allows efficient computation of \( p(n) \) using only previously computed values: no infinite products, no complex analysis, just addition and subtraction with the pentagonal-number pattern of signs.
Appendix: Selected Values of p(n)
- \( n \): 0 | \( p(n) \): 1 | \( n \): 20 | \( p(n) \): 627 | \( n \): 50 | \( p(n) \): 204,226
- \( n \): 1 | \( p(n) \): 1 | \( n \): 21 | \( p(n) \): 792 | \( n \): 60 | \( p(n) \): 966,467
- \( n \): 2 | \( p(n) \): 2 | \( n \): 22 | \( p(n) \): 1,002 | \( n \): 70 | \( p(n) \): 4,087,968
- \( n \): 3 | \( p(n) \): 3 | \( n \): 23 | \( p(n) \): 1,255 | \( n \): 80 | \( p(n) \): 15,796,476
- \( n \): 4 | \( p(n) \): 5 | \( n \): 24 | \( p(n) \): 1,575 | \( n \): 90 | \( p(n) \): 56,634,173
- \( n \): 5 | \( p(n) \): 7 | \( n \): 25 | \( p(n) \): 1,958 | \( n \): 100 | \( p(n) \): 190,569,292
- \( n \): 10 | \( p(n) \): 42 | \( n \): 30 | \( p(n) \): 5,604 | \( n \): 150 | \( p(n) \): 30,048,805,969
- \( n \): 15 | \( p(n) \): 176 | \( n \): 40 | \( p(n) \): 37,338 | \( n \): 200 | \( p(n) \): 3,972,999,029,388
The congruences are evident: every entry in the \( 5n+4 \) column (\( n = 4, 9, 14, 19, 24, \ldots \)) is divisible by 5.
Exercises
-
List all partitions of 7 and verify that \( p(7) = 15 \).
-
For each partition of 6, draw its Ferrers diagram and find the conjugate partition.
-
Verify Euler’s identity \( Q(n) = O(n) \) for \( n = 8 \) by listing all distinct-parts partitions and all odd-parts partitions.
-
Use Euler’s recurrence to compute \( p(12) \) from the values \( p(0) \) through \( p(11) \).
-
The pentagonal numbers are \( 1, 5, 12, 22, 35, 51, \ldots \) Compute the first 8 generalized pentagonal numbers \( \omega(k) \) for \( k = 1, -1, 2, -2, 3, -3, 4, -4 \).
-
Prove that the number of partitions of \( n \) into at most \( k \) parts equals the number of partitions of \( n \) into parts of size at most \( k \). (Hint: use conjugation of Young diagrams.)
-
Use the generating function to show that the number of partitions of \( n \) into exactly 2 parts is \( \lfloor n/2 \rfloor \).