Motivation
Partitioning an integer is different from partitioning a labeled set. The integer records indistinguishable units, so the order of its summands is discarded. A diagram makes that loss of order precise and reveals a useful symmetry: exchanging rows and columns swaps the number of parts with the largest part.
Multiplicities give a second description. They make generating functions natural because choosing how often each size occurs is independent of choosing the other sizes. The infinite product is formal: only finitely many factors can affect any one coefficient. A square inside the diagram then gives a less obvious decomposition into two smaller constrained partitions.
All counts, diagram maps and product identities below are proved.
Definitions
Definition 2.9.1
(Integer partitions and their diagrams)
A partition of a nonnegative integer is a finite nonincreasing list whose sum is . Its length is and its largest part is . The unique partition of zero is empty; its length and largest part are taken to be zero. Let count all partitions.
The Ferrers diagram has left-justified cells in row . Its conjugate has parts . The multiplicity is the number of parts equal to , so .
Let count partitions whose largest part is at most , with and for positive , and let count partitions of with exactly parts. Parts are positive, so a fixed partition uses only finitely many nonzero multiplicities. A formal variable records total size; a second variable can record length.
The Durfee side is the largest integer with , the side of the largest top-left square in the diagram. It is zero for the empty diagram. Maximality implies every row below that square has length at most .
Theorem/Proposition
Theorem 2.9.2
(Conjugation and subtracting one give exact restriction maps)
Conjugation is a size-preserving involution. It exchanges the number of parts and largest part. Thus partitions of with at most parts are equinumerous with partitions whose largest part is at most .
For and , partitions of with exactly parts correspond to partitions of with at most parts. For no such partition exists. Exactly zero parts occurs only at .
Theorem 2.9.3
(Formal generating products and odd/distinct equality)
The partition series and its length refinement are
A largest-part bound truncates the first product at . A multiplicity bound replaces its factor by the corresponding finite geometric sum. Moreover the number of partitions into distinct parts equals the number into odd parts at every size, with series identity
Theorem 2.9.4
(Durfee decomposition gives a second partition series)
Every partition is uniquely obtained from its Durfee square of side , a partition with at most parts to its right, and a partition with largest part at most below it. Consequently
The term is one, using the empty-product convention. At a fixed degree only indices with at most that degree can contribute.
Proof sketch or proof idea
Proof
(Transposition and the subtract-one map)
Transposing the cell coordinates interchanges rows and columns and preserves their number. Left justification and nonincreasing row lengths make the column lengths another nonincreasing list. Transposing twice returns the original cell set, proving the involution. Every column has at most as many cells as the original number of rows, and the first column has exactly that many; this proves the exchange of length and largest part.
For an exact-length partition, subtract one from every one of its parts and remove zeros. The resulting nonincreasing positive list has total and at most parts. Conversely pad such a list with zeros to length and add one to each entry. The two operations are inverse, including the case where the smaller partition is empty.
Proof
(Multiplicity products and the odd/distinct identity)
For the product, size can occur any nonnegative number of times, giving factor . Multiplying factors chooses exactly the multiplicities and sums their contributions to total size. The geometric factor is formally invertible since its denominator has constant term one. A factor with contributes only its constant term to degree , proving that the infinite product is well-defined coefficient by coefficient. Keeping one extra factor for each selected part gives the bivariate product by the same argument. No numerical value of or analytic convergence has been used.
The distinct-parts factor is . Since , canceling the even-index factors formally leaves only the odd-index denominator factors. To justify the cancellation, fix a desired degree and retain all relevant factors; unmatched factors whose nonconstant terms start above that degree do not affect it. Finite cancellation proves equality at that degree, and the degree was arbitrary.
There is also a direct bijection. In an odd-part partition, write each multiplicity in binary. For each nonzero binary digit at position , replace copies of odd part by the one part . Parts are now distinct, since every positive integer has a unique power-of-two factor and odd remainder. Conversely split each distinct part into that many copies of its odd remainder. The distinct powers for each remainder are precisely its binary multiplicity digits, so the maps undo each other and preserve the sum.
Proof X-ray
The multiplicity expansion supplies a reversible choice
Two uniqueness facts carry the binary bijection, and each is used in one direction. Uniqueness of binary expansion makes the forward map well defined: a multiplicity has exactly one set of digits, so the output is determined. Uniqueness of the factorization of a positive integer as a power of two times an odd number does double duty: it makes the output parts distinct, since two digits from different odd parts or different positions give different products, and it lets the inverse read off the odd remainder and the digit position from each distinct part. Total size is preserved because each replacement trades 2 to the copies of for one part of the same total. The generating-function proof reaches the same equality by a different route: there the key step is the finite truncation that licenses canceling infinitely many factors one degree at a time.
Proof
(Removing and reattaching the Durfee square)
For Durfee decomposition, remove the top-left square. The remaining cells to the right occupy at most its rows and have nonincreasing lengths. The remaining rows below it have length at most , by the definition of the maximal square. These are exactly the two stated constrained partitions.
Conversely attach any such right diagram to the square's rows and any such lower diagram below it. Row lengths within both regions are ordered; the last square row has length at least and the first lower row at most , so their boundary respects the partition condition. No larger square appears because the next row is too short. The reconstruction is unique. The square contributes size , and conjugation makes both residual-region generating series equal to the product truncated at . Multiplication counts the independent regions and summation over the unique square size proves the identity.
A coefficient table has a justified update order
Proposition 2.9.5
(Largest-part recurrence)
For and every integer ,
with for .
Proof
(Split by whether a part of size occurs)
Partitions of with largest part at most either contain no part equal to , which are counted by , or contain one. If such a part occurs, remove one copy; the remaining partition may still contain more copies, explaining the current subscript on that term. Adding the removed copy is the inverse operation.
To compute coefficients through size , begin with count one at zero and zero at other sizes. Process part sizes from one through ; for a current part size, update totals in increasing order by adding the count at that total minus the part. The lower total has already incorporated the current part size, exactly matching unrestricted multiplicity. Processing totals downward would instead impose a different one-use restriction. The outer order on part sizes prevents counting different orders of the same summands as different partitions.
This uses additions and stored values. For , every partition is one particular composition of its total, while compositions of a positive integer correspond to subsets of its intervening gaps. Hence and all table values need bits. Straightforward integer additions therefore give a polynomial bit bound in as well. This is a table through the numerical index, not a claim of time polynomial in the binary length of a request for one enormous index.
Worked examples
Worked example 2.9.6
(One diagram shows conjugation and both Durfee regions)
For , total size is twelve. Its conjugate is : column heights are four, three, three, one and one. Length four and largest part five have exchanged.
The Durfee side is three. Removing its nine cells leaves right partition of size two and lower partition of size one. Both meet their restrictions and . The maximal-square condition fails at the fourth row, so the side is not chosen arbitrarily among all squares that fit.
Worked example 2.9.7
(Binary multiplicities turn odd parts into distinct parts)
Take the odd-part partition of eleven. Three copies of three split by the binary expansion three equals one plus two, producing parts three and six. Two copies of one produce part two. The resulting distinct partition is .
For the inverse, six contributes two copies of three, three contributes one more, and two contributes two copies of one. The original multiplicities return exactly. The map does not replace every repeated pair blindly without tracking its odd remainder; the unique power-of-two factorization is what prevents collisions.
Worked example 2.9.8
(Seven partitions of five, with two equal subfamily counts)
The partitions of five are , , , , , and . Thus .
The distinct ones are . The odd-part ones are . The bijection sends these odd partitions respectively to . Counting all partitions and counting a restricted subfamily are different coefficient questions, even when the same product construction organizes both.
Concept lensCombinatorial
Rows, multiplicities and square regions describe the same weighted objects
Conjugation changes a boundary restriction, multiplicities separate choices by part size, and a Durfee square isolates a unique central shape with two independent remainders. Each viewpoint retains total size and specifies how to reconstruct the partition. That common weight permits the generating identities and exact restriction counts to agree.
Common mistakes
Counterexample mode
Integer partitions are not labeled-set partitions
The integer three has partitions , only three. A labeled three-element set has five set partitions: the block-size pattern two plus one has three choices for its singleton label. Those choices are absent from the integer partition. The fibers over size patterns have different sizes, so no one uniform division converts the labeled count into the integer count.
Formal products do not automatically permit substituting a numerical value such as one: at every factor is undefined.
Common mistake
(Allowing zero as a part)
If zero were an unrestricted part size, , , , and so on would all be different partitions of two, and would be infinite. Parts are positive; the empty partition of zero is the one exception, and it has no parts at all.
Common mistake
(At most parts versus exactly parts)
Partitions of six with at most two parts are , four in all; with exactly two parts there are three. The subtract-one map links exactly parts of to at most parts of , not of .
Common mistake
(Using a square that is not maximal)
In a square also fits in the corner. Removing it leaves rows below, whose largest part exceeds two, so the lower region is not a partition with largest part at most the side. Only the maximal square, here of side three, gives the decomposition and makes it unique.
Summary
Conjugation and subtracting one give exact maps between part restrictions. Multiplicity choices produce well-defined formal products, while binary expansion proves odd-part/distinct-part equality directly. The maximal Durfee square supplies a second complete decomposition, and its coefficient algorithm depends on the correct unrestricted-multiplicity update order.
Exercises
Quick check
(Count the partitions of eight into exactly three positive parts. Relate them to partitions of five into at most three parts and list the results.)
Use padding with zeros before adding one back.
Solution · Answer
The partitions of five with at most three parts are . Padding to three entries and adding one gives . These are all five partitions requested, by the proved bijection rather than an assumption that a short list is exhaustive.
Quick check
(Find the coefficient counting partitions of six with exactly two parts. Give their conjugates with largest part exactly two.)
Compare direct enumeration with the exact-length generating expression.
Solution
The two-part partitions are . Subtracting one gives total four with at most two parts, whose series is . Its degree-four coefficient counts solutions of an unrestricted one-part/two-part multiplicity equation and is three. Equivalently the exact-length series is and its degree-six coefficient is three.
The conjugates are , each with largest part exactly two. Their uniqueness and completeness follow from conjugation's involution.
Quick check
(Prove that partitions in which every part occurs at most twice are equinumerous with partitions having no part divisible by three.)
Use a formal cancellation or replace the binary multiplicity bijection by base three; give a reversible construction.
Solution
Start with a partition whose parts are not divisible by three. For each part size , expand its multiplicity in base three. A digit zero, one or two at position produces that many parts of size . Every positive integer has a unique factorization into a power of three times a number not divisible by three, so the output uses each size at most twice. Reversing that factorization recovers the original multiplicities and total size.
The same identity is , obtained by writing each factor as and canceling coefficientwise. Both arguments prove a full equality of counts, not only a check of small examples.