Count partitions through diagrams and products

Try

The sum six can be partitioned as 4+2 or 2+4, but these are the same integer partition. Write parts in nonincreasing order to choose one representation. A composition remembers order; a set partition remembers the individual labels inside blocks; an integer partition remembers only the multiset of positive sizes. Confusing these three object classes changes the counting problem before any formula is applied.

Predict

Predict how a diagram exchanges size restrictions. Draw one left-aligned row of boxes for each part. For partition (4, 2, 1), the column heights are (3, 2, 1, 1). Transposing this Ferrers diagram exchanges rows and columns, preserves the total number of boxes, and reverses itself when repeated. Thus a bound on the largest part becomes a bound on the number of parts.

Experiment

Compare the two special families for total five.

Distinct parts	Odd parts
5	5
4+1	3+1+1
3+2	1+1+1+1+1

There are three of each, but the rows are not intended as the binary bijection. Apply that bijection yourself: five copies of one have binary multiplicity 101, producing parts four and one. Determine the images of the other two odd-part partitions.

Understand

Let p(n) count integer partitions, with p(0)=1 for the empty partition. Choosing the multiplicity of part j gives the factor 1+z^j+z^(2j)+…=(1−z^j)^(−1). Hence Σp(n)z^n=product over j≥1 of (1−z^j)^(−1). This formal infinite product is well-defined coefficientwise: factors with j>n cannot affect the coefficient of z^n. Distinct parts instead give product (1+z^j), while odd parts give the reciprocal product restricted to odd j. The identity 1+z^j=(1−z^(2j))/(1−z^j) cancels all even-index factors and proves the equality of these two generating functions, so their coefficients agree for every total.

Apply

The equality also has a constructive proof. In an odd-part partition, write the multiplicity of each odd part u in binary. A binary digit one in position k becomes one part 2^k u. These output parts are distinct because each positive integer has a unique odd factor times a power of two. Conversely, split each distinct part 2^k u into 2^k copies of its odd factor u. Binary uniqueness proves these operations inverse. This teaches more than a coefficient identity: it tells how to transform an individual object and why no information is lost.

Conjugation gives another coefficient identity: partitions of n with exactly k positive parts correspond, after subtracting one from each part, to partitions of n−k with at most k parts. Reversing the shift adds a column of height k. This is not the same as deleting all occurrences of the largest part; draw both operations on a Ferrers diagram to see why they yield different recurrences.

Continue

For computation with a maximum part k, use P(n, k)=P(n, k−1)+P(n−k, k): either no part k appears, or remove one such part. Set P(0, k)=1 and negative totals to zero; P(n, 0)=0 for positive n. A dynamic-programming table must respect these boundaries. Partition asymptotics and deeper modular identities require further theory. Here the proved results are diagram conjugation, a formal product, and an explicit distinct-to-odd bijection, all available without analytic convergence assumptions.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with enumerate permutations by cycle structure.