Integer Partitions and Counting Structures
p(n), Euler’s product, the pentagonal number theorem, and the family of counting structures (Stirling, Bell, Catalan) that partitions belong to.
Leads to: 19.13 accelerates linear recurrences; 19.14 checks the feasibility of each method. The Euler Lab’s Combinatorics path has a family of partition and set-partition problems.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- Define an integer partition and derive Euler’s generating function \(\prod_{k\ge1}(1-x^k)^{-1}\) from the multiset decomposition.
- Compute \(p(n)\) by DP in \(O(n^2)\) and by the pentagonal number theorem in \(O(n^{3/2})\).
- Distinguish partitions of an integer from partitions of a SET (Stirling/Bell numbers) and count each correctly.
- Impose restrictions (distinct parts, odd parts, bounded parts) by editing the generating function, and prove Euler’s odd–distinct theorem.
- Implement partition counting and validate it against brute-force enumeration for small \(n\).
Key Vocabulary
- Integer partition
- A multiset of positive integers summing to \(n\); order does not matter. \(p(4)=5\): 4, 3+1, 2+2, 2+1+1, 1+1+1+1.
- Composition
- An ORDERED sum. There are \(2^{n-1}\) compositions of \(n\) - a much easier count than \(p(n)\), and a common source of confusion.
- Euler’s product
- \(\sum_{n\ge0}p(n)x^n=\prod_{k\ge1}\frac{1}{1-x^k}\): one factor per part size, each contributing a geometric series of multiplicities.
- Pentagonal number theorem
- \(\prod_{k\ge1}(1-x^k)=\sum_{j\in\Z}(-1)^j x^{j(3j-1)/2}\); it yields a recurrence for \(p(n)\) with only \(O(\sqrt n)\) terms.
- Stirling number (2nd kind)
- \(S(n,k)\): the number of ways to partition a SET of \(n\) labelled elements into \(k\) nonempty unlabelled blocks. \(S(n,k)=k\,S(n-1,k)+S(n-1,k-1)\).
- Bell number
- \(B_n=\sum_k S(n,k)\): all set partitions of an \(n\)-set. \(B_0..B_5=1,1,2,5,15,52\).
Intuition & Motivation
Euler’s product
A partition of \(n\) is determined by how many 1s, how many 2s, how many 3s, … it uses. Those choices are independent, and the size contributed by using \(m_k\) copies of \(k\) is \(m_kk\). Encoding ‘use \(m\) copies of \(k\)’ as \(x^{mk}\):
Restrictions are now edits to the product, which is the real power of the generating-function view:
| Restriction | Generating function | Reason |
|---|---|---|
| Any parts | \(\prod_{k\ge1}(1-x^k)^{-1}\) | unlimited multiplicity of each part |
| Distinct parts | \(\prod_{k\ge1}(1+x^k)\) | each part used 0 or 1 times |
| Odd parts only | \(\prod_{k\ \mathrm{odd}}(1-x^k)^{-1}\) | only odd factors survive |
| Parts \(\le M\) | \(\prod_{k=1}^{M}(1-x^k)^{-1}\) | finite product - exactly the coin-change DP |
| Exactly \(k\) parts | \(x^k\prod_{j=1}^{k}(1-x^j)^{-1}\) | conjugate partitions: parts \(\le k\) ↔ at most \(k\) parts |
Computing \(p(n)\)
Method 1 - DP (\(O(n^2)\)). This is (19.16) with coins \(1,2,\dots,n\): for each part size \(k=1..n\), for each amount \(a=k..n\), \(P[a] \mathrel{+}= P[a-k]\). Simple, exact, and fast enough to \(n\approx10^4\).
Method 2 - the pentagonal recurrence (\(O(n^{3/2})\)). Euler’s pentagonal number theorem states
Since (19.22) says that product is the reciprocal of \(\sum p(n)x^n\), multiplying the two series and equating coefficients gives a recurrence with only \(O(\sqrt n)\) nonzero terms:
Partitions of a SET are a different animal
Do not confuse \(p(n)\) (partitions of the integer \(n\)) with the number of ways to split a set of \(n\) labelled objects into groups. The latter is the Bell number \(B_n=\sum_k S(n,k)\), where the Stirling numbers of the second kind obey
(the new element either joins one of the \(k\) existing blocks, or starts its own). The counts diverge fast: \(p(5)=7\) but \(B_5=52\). ‘Partition’ in a problem statement is ambiguous until you ask are the objects labelled?
Coding workbench
Coin-sum problems, ‘in how many ways can \(n\) be written as a sum of …’, and the first \(p(n)\) divisible by a million - the Euler Lab’s Combinatorics path returns to partitions again and again, and the pentagonal recurrence is what makes the larger instances tractable.
- Counting compositions when the problem wants partitions: order matters in one and not the other (\(2^{n-1}\) vs \(p(n)\), wildly different).
- Ascending vs descending inner loop. Ascending = unlimited copies; descending = each part at most once. One character, a different theorem.
- Confusing \(p(n)\) with the Bell number \(B_n\). Ask whether the objects are labelled.
- Trying to compute \(p(n)\) from the Hardy–Ramanujan asymptotic \(p(n)\sim\frac{1}{4n\sqrt3}e^{\pi\sqrt{2n/3}}\) and rounding. It is an asymptotic, not an exact formula - the relative error is still ~2% at \(n=100\).
- Forgetting that \(p(n)\) grows sub-exponentially but very fast: \(p(100)=190{,}569{,}292\) and \(p(1000)\) has 31 digits. Use exact integers (19.4).
- Every restricted-partition count is an edit to Euler’s product - and every product is a DP loop. Learn the dictionary once and you can count anything of this shape.
- Conjugation (transpose the Young diagram) is a free bijection: partitions with parts \(\le k\) ↔ partitions with at most \(k\) parts. It converts many awkward restrictions into easy ones.
- For \(p(n)\bmod m\) (a common problem framing), run the pentagonal recurrence with all arithmetic mod \(m\) - \(O(n^{3/2})\) small operations, no big integers at all.
- Sanity-check any counting DP against a brute-force enumerator for \(n\le10\). Partition off-by-ones are invisible in the code and obvious in the counts.
Practice this in the Euler Lab
Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.
Warm-up:
#49 Prime Permutations (3%, tier A) #53 Combinatoric Selections (3%, tier A) #29 Distinct Powers (5%, tier A) #24 Lexicographic Permutations (6%, tier A)
Applied:
#336 Maximix Arrangements (16%, tier B) #265 Binary Circles (17%, tier B) #713 Turán's Water Heating System (19%, tier B)
Challenge:
#161 Triominoes (41%, tier C) #182 RSA Encryption (41%, tier C)
181 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.
Knowledge Check
Practical Exercise
(a) Derive the generating function for partitions into parts of size at most 3 and use it to compute the number of partitions of 10 into such parts. (b) Prove the conjugation bijection: partitions of \(n\) into at most \(k\) parts are equinumerous with partitions of \(n\) into parts each \(\le k\). (c) Estimate the cost of computing \(p(10^5)\) by the \(O(n^2)\) DP versus (19.24), in operations.
(a) \(G(x)=\frac{1}{(1-x)(1-x^2)(1-x^3)}\). Evaluate by the DP with coins \(\{1,2,3\}\): start \(P=[1,0,0,\dots]\). After part 1: all ones. After part 2: \(P=[1,1,2,2,3,3,4,4,5,5,6]\). After part 3: \(P[a] \mathrel{+}= P[a-3]\) for \(a=3..10\), giving \(P=[1,1,2,3,4,5,7,8,10,12,14]\). So there are 14 partitions of 10 into parts \(\le3\). (Check \(p(10)=42\) unrestricted - the restriction bites hard.)
(b) Draw the Young diagram of a partition \(\lambda=(\lambda_1\ge\lambda_2\ge\cdots)\): row \(i\) has \(\lambda_i\) cells. The conjugate \(\lambda^*\) is obtained by transposing the diagram: \(\lambda^*_j=\#\{i:\lambda_i\ge j\}\). Transposition preserves the total number of cells (\(n\)), is an involution (\(\lambda^{**}=\lambda\), hence a bijection), and swaps ‘number of rows’ with ‘largest column index’: the number of parts of \(\lambda\) equals the largest part of \(\lambda^*\). Therefore ‘at most \(k\) parts’ maps bijectively onto ‘every part \(\le k\)’. □
(c) The \(O(n^2)\) DP does \(\sum_{k=1}^{n}(n-k+1)\approx n^2/2=5\times10^9\) big-integer additions at \(n=10^5\) - hours in Python, and each addition is on numbers with hundreds of digits. The pentagonal recurrence does \(\sum_{m\le n}O(\sqrt m)\approx \tfrac23 n^{3/2}\approx2\times10^7\) additions - seconds. That is a 250× reduction in operation count (and the operands are the same size), which is the difference between ‘overnight’ and ‘interactive’. This is exactly the feasibility arithmetic of 19.14.
Lesson Summary
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: \(\sum_n p(n)x^n=\prod_{k\ge1}(1-x^k)^{-1}\). The factor for part size \(k\) is \(1+x^k+x^{2k}+\cdots\), recording how many copies of \(k\) the partition uses; multiplying makes the choices independent.
A: Run the inner (amount) loop DESCENDING instead of ascending, so each part size is used at most once - the 0/1-knapsack trick. By Euler's theorem the resulting count equals the number of odd-part partitions.
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Source References
This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.
- Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Ch. 10–11 - Infinite products, power series and rearrangement - the analytic licence behind manipulating Euler’s product and the pentagonal identity formally.
- Probability: Theory and Examples (Rick Durrett, 5th ed.) current - Ch. 1 - Counting structures as probability distributions (uniform random partitions, set-partition/occupancy models) and the combinatorial identities they generate.
- The Pragmatic Programmer (Thomas & Hunt, 2nd/20th Anniv. ed., 2019) current - Ch. 7 - Validate every counting DP against a brute-force enumerator for small \(n\) - an off-by-one in a partition loop is invisible in the source and obvious in the counts.