Integer Partitions: Theory, Ferrers Diagrams, Examples

An integer partition of n is a way of writing n as a sum of positive integers where order does not matter. The partitions of 4 are 4, 3+1, 2+2, 2+1+1 and 1+1+1+1, so p(4) = 5. Note that 3+1 and 1+3 are the same partition.

Partitions appear wherever identical objects are divided into groups: distributing identical balls into boxes and representing integers in additive number theory. The numbers p(n) grow astonishingly fast: p(100) = 190,569,292.

Key Concepts

• Partition of n: a multiset of positive integers summing to n; order is irrelevant.
• Partition number p(n): the count of partitions of n. Values: p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7.
• p(n, k): partitions of n into exactly k parts.
• Ferrers diagram: a left-justified stack of dot rows, one row per part, visualizing the partition's shape.
• Conjugate partition: reflecting the Ferrers diagram swaps rows and columns, bijecting partitions of n into k parts with partitions of n with largest part k.

Formulas

• Recurrence for fixed parts: p(n, k) = p(n−1, k−1) + p(n−k, k). Either some part equals 1 (remove it: p(n−1, k−1)) or all parts exceed 1 (subtract 1 from each part: p(n−k, k)).
• Generating function: Σₙ p(n)·xⁿ = ∏ₖ 1/(1−xᵏ). Each factor 1/(1−xᵏ) = 1 + xᵏ + x²ᵏ + … chooses how many k's appear.
• Two parts: p(n, 2) = ⌊n/2⌋, the number of pairs (a, b) with a ≥ b ≥ 1 and a + b = n.
• Euler's pentagonal recurrence: p(n) = p(n−1) + p(n−2) − p(n−5) − p(n−7) + … alternates signs at the generalized pentagonal numbers.

Worked Example

List all partitions of 5 and verify the recurrence for p(5, 2):

• All partitions of 5: 5; 4+1; 3+2; 3+1+1; 2+2+1; 2+1+1+1; 1+1+1+1+1. That is 7 partitions, so p(5) = 7.
• Exactly 2 parts: 4+1 and 3+2, so p(5, 2) = 2, matching ⌊5/2⌋ = 2.
• Recurrence check: p(5, 2) = p(4, 1) + p(3, 2) = 1 + 1 = 2 (only "4" and "2+1" respectively).
• Ferrers view: the diagram of 3+2 reflects to 2+2+1, a partition of 5 with largest part 2.

Common Misconceptions

• "3+1 and 1+3 are different partitions." They are the same. If order mattered you would count compositions (2ⁿ⁻¹ of them, far more).
• "p(n) counts factorizations or something similar." It counts only additive decompositions into positive integers. Multiplicative structure is a different topic.
• "The parts must be distinct." Not in ordinary partitions; 2+2+1 is perfectly valid. Partitions into distinct parts are a separate, also interesting, counting problem.

Real-World Applications

• Statistical physics: distributing identical energy units among particles is a partition problem.
• Generating functions: Euler's product for partitions launched the whole method of generating functions in combinatorics.
• Coin change: counting ways to make change with unlimited coins is counting partitions with restricted part sizes.

Integer partitions break n into unordered sums, counted by p(n), refined by p(n, k), visualized with Ferrers diagrams and governed by recurrences and Euler's generating function. Remember the golden rule, order does not matter, and partitions become a clean, endlessly rich counting world.