Integer Partitions and the Twelvefold Way

A cell $(i,j)$ belongs to the Ferrers diagram of $\lambda$ exactly when the $i$-th row has length at least $j$, and by [F1] this is equivalent to the $j$-th row of ${\lambda }^{\mathrm{\prime }}$ having length at least $i$. Therefore the cells of ${\lambda }^{\mathrm{\prime }}$ are exactly the transpose $(j,i)$ of the cells of $\lambda$.

Transposing the same finite set of cells a second time sends $(j,i)$ back to $(i,j)$, so the twice-conjugated diagram is the original diagram. Hence its row lengths are again $\lambda$, that is, $({\lambda }^{\mathrm{\prime }}{)}^{\mathrm{\prime }}=\lambda$.

If $k=0$ and $n>0$, then there is no partition of $n$ with exactly $0$ parts and no partition of $n$ whose largest part is $0$, so both displayed sets are empty. If $k=0$ and $n=0$, then both displayed sets consist only of the empty partition; by the partition convention recalled in [F1], its largest part is $0$. Thus the claim holds when $k=0$. Assume now $k\ge 1$. Let $\lambda$ be a partition of $n$ with exactly $k$ parts. Then its Ferrers diagram has exactly $k$ rows by [F1]. After transposition, the conjugate diagram has top row length $k$, because the first column of the original diagram had one cell in each of the $k$ rows. Thus ${\lambda }^{\mathrm{\prime }}$ has largest part $k$. The same argument in reverse shows that any partition with largest part $k$ conjugates to one with exactly $k$ parts.

Step 1.1 shows that conjugation maps each of the two displayed sets into the other, and [L1] shows that this map has its own inverse. Therefore it is a bijection between them, so the two sets have equal cardinality.

Let $\lambda$ be a partition of $n$ with at most $k$ parts. If $\lambda$ has exactly $j$ parts, then $j\le k$, and [L1] sends $\lambda$ by conjugation to a partition whose largest part is $j$. By [F1], every part of the conjugate is therefore at most $k$. The same reasoning in reverse sends any partition all of whose parts are at most $k$ to one with at most $k$ parts.

Thus conjugation restricts to a bijection between the two displayed sets, so they have equal cardinality.

A partition of $n$ into exactly $k$ positive parts either contains a part equal to $1$ or has every part at least $2$. These two cases are disjoint and exhaustive.

In the first case, delete one part equal to $1$. The remaining parts still form a partition, now of $n-1$, and they are exactly $k-1$ positive parts. Conversely, adjoining one part equal to $1$ to any partition of $n-1$ into $k-1$ positive parts gives a partition of $n$ into $k$ positive parts containing a $1$. So the first case contributes $p_{k-1}(n-1)$.

In the second case, subtract $1$ from each of the $k$ parts. Because each part was at least $2$, the result is a partition of $n-k$ into exactly $k$ positive parts. Conversely, adding $1$ to each part of any partition of $n-k$ into $k$ positive parts recovers a partition of $n$ into $k$ parts all at least $2$. So the second case contributes $p_k(n-k)$. If $n-k<0$, then [F1] makes this contribution $0$, exactly as it should.

The two disjoint cases of steps 2.1 and 2.2 cover every partition counted by $p_k(n)$, so their cardinalities add to $p_k(n)$. This is the stated recurrence.

By [F1], a partition into distinct parts is exactly a subset of the set $\{u_1,u_2,\dots \}$: include $u_m$ when the part $m$ occurs, and omit it otherwise. The total size of the chosen subset is the sum of the selected part sizes.

Applying [L1] to the class with one object $u_m$ in each positive size $m$ gives one factor $(1+x^m)$ for every $m\ge 1$. Step 1.1 identifies the resulting powerset objects with distinct-part partitions, so their generating function is ${\prod }_{m\ge 1}(1+x^m)$.

By [F1], a partition into odd parts is exactly a multiset of the objects $v_1,v_2,\dots$: the multiplicity of $v_m$ records how often the odd part $2m-1$ occurs. The total size of the multiset is the sum of the odd parts.

Applying [L1] to the class $\{v_1,v_2,\dots \}$ gives the product ${\prod }_{m\ge 1}(1-x^{2m-1}{)}^{-1}$. Step 1.1 identifies its multiset objects with partitions into odd parts, so this is the generating function for $p_{\mathrm{o}\mathrm{d}\mathrm{d}}(n)$.

Fix $N\ge 1$. Using $1+x^m=(1-x^{2m})(1-x^m{)}^{-1}$ for $1\le m\le N$ and canceling only the even factors that already appear in the denominator gives ${\prod }_{m=1}^N(1+x^m)=({\prod }_{m=\lfloor N\mathrm{/}2\rfloor +1}^N(1-x^{2m}))/({\prod }_{\begin{array}{c}1\le j\le N\\ j\text{ odd}\end{array}}(1-x^j))$. Every uncancelled numerator factor has degree $>N$, so the left-hand side and $1\mathrm{/}{\prod }_{1\le j\le N,j\text{ odd}}(1-x^j)$ have the same coefficients through degree $N$.

Fix $n\ge 0$ and choose $N>n$. By step 1.1, the coefficient of $x^n$ in ${\prod }_{m=1}^N(1+x^m)$ equals the coefficient of $x^n$ in $1\mathrm{/}{\prod }_{1\le j\le N,j\text{ odd}}(1-x^j)$. Factors with index $>N$ have degree $>n$ in both products, so this is also the common coefficient of $x^n$ in the two infinite products ${\prod }_{m\ge 1}(1+x^m)$ and ${\prod }_{m\ge 1}(1-x^{2m-1}{)}^{-1}$.

Substitute the two product expansions from [L1] and [L2] into step 2.1. The resulting formal series are equal, so [L3] gives equality of every coefficient. Hence $p_{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}}(n)=p_{\mathrm{o}\mathrm{d}\mathrm{d}}(n)$ for all $n\ge 0$.

Let $\lambda$ be a partition of $n$ into odd parts. For each odd integer $m$, let $c_m$ be its multiplicity in $\lambda$, and write the binary expansion

Conversely, let $\mu$ be a partition of $n$ into distinct parts. Write each part uniquely as $2^{j}u$ with $u$ odd, and replace it by $2^j$ copies of the odd part $u$. The resulting partition $H(\mu )$ has only odd parts and still sums to $n$.

The parts of $G(\lambda )$ are distinct. Indeed, every positive integer has a unique expression $2^{j}u$ with $u$ odd, so two equal parts in $G(\lambda )$ would come from the same odd core $u$ and the same power $2^j$, hence from the same binary digit.

The two constructions are inverse. Starting from $\lambda$, step 1.2 reconstructs from each part $2^{j}m$ of $G(\lambda )$ exactly the $2^j$ copies of $m$ encoded by the corresponding binary digit, so $H(G(\lambda ))=\lambda$. Starting from $\mu$, step 1.1 groups together all parts with the same odd core and reassembles exactly the original powers of two, so $G(H(\mu ))=\mu$. Therefore $G$ is a bijection.

Let $\lambda$ be a self-conjugate partition, and let $d=d(\lambda )$. For each diagonal cell $(i,i)$ with $1\le i\le d$, let $h_i$ be the length of its hook: the cell itself together with the cells directly to its right in row $i$ and directly below it in column $i$. Self-conjugacy pairs the cells to the right with the cells below, so each $h_i$ is odd. As $i$ increases, each later diagonal hook lies strictly inside the previous one, so $h_1>h_2>\cdots >h_d$. The diagonal hooks are disjoint and cover the whole diagram, hence $h_1+\cdots +h_d=\mathrm{\mid }\lambda \mathrm{\mid }=n$. Thus $\lambda$ determines a partition of $n$ into distinct odd parts.

Conversely, let $h_1>h_2>\cdots >h_d>0$ be distinct odd parts summing to $n$, and write $h_i=2a_i+1$. Then $a_1>\cdots >a_d\ge 0$, and since these are $d$ distinct nonnegative integers one has $a_i\ge d-i$ for each $i$. Build a diagram by placing diagonal cells $(i,i)$ for $1\le i\le d$, then adjoining $a_i$ cells to the right of $(i,i)$ and $a_i$ cells below $(i,i)$. The inequalities $a_i\ge d-i$ and $a_1>\cdots >a_d$ make these hooks nest to form a Ferrers diagram, and the construction is visibly symmetric across the main diagonal, so the resulting partition is self-conjugate.

The diagonal hooks of the partition from step 1.2 have lengths $h_1,\dots ,h_d$ by construction, so step 1.2 inverts step 1.1. Therefore the two constructions are mutually inverse bijections.

Let $\lambda$ be a partition with Durfee length $k$. Removing its $k\times k$ Durfee square leaves two pieces: a right-hand piece $\alpha$ consisting of the cells to the right of the square, and a lower piece $\beta$ consisting of the cells below the square. The piece $\alpha$ has at most $k$ rows, while each row of $\beta$ has length at most $k$. Conversely, given $k$, a partition $\alpha$ with at most $k$ parts, and a partition $\beta$ with all parts at most $k$, one reconstructs $\lambda$ uniquely by adjoining $\alpha$ to the right side and $\beta$ below the square.

For fixed $k$, the square contributes the factor $x^{k^2}$. By [L2], the right-hand piece $\alpha$ has the same generating function as partitions with parts at most $k$, namely ${\prod }_{i=1}^k(1-x^i{)}^{-1}$; the lower piece $\beta$ has the same generating function for the same direct multiplicity reason. Thus partitions whose Durfee square has size $k$ contribute $x^{k^2}\mathrm{/}{\prod }_{i=1}^k(1-x^i{)}^2$.

Every partition has exactly one Durfee length, so summing the contributions of step 2.1 over all $k\ge 0$ counts every partition exactly once. Therefore the coefficient of $x^n$ on the right is $p(n)$ for every $n\ge 0$, and [L1] gives the displayed identity.

By [L1], an arbitrary placement is determined by the list of its positive occupancies, written in nonincreasing order. These occupancies sum to $n$, so they form a partition of $n$; because there are only $k$ boxes, there can be at most $k$ positive occupancies. Conversely, any partition of $n$ with at most $k$ parts becomes such a placement by reading its parts as the nonzero box occupancies. This proves clause 1 in its "at most $k$ parts" form.

A placement is surjective exactly when every box is occupied, so there are exactly $k$ positive occupancies. By step 1.1 these are exactly the partitions of $n$ into $k$ positive parts, which are counted by $p_k(n)$. This is clause 3.

A placement is injective exactly when every occupied box contains one ball. Therefore the positive occupancy list must be $(1,\dots ,1)$ with $n$ entries. Such a list exists exactly when $n\le k$, and when it exists it is unique. This proves clause 2.

The second description in clause 1 follows from [L2].

For labelled balls and labelled boxes, clause 1 is [L1] and clause 2 is [L2]. For clause 3, a surjection $f:[n]\to [k]$ has $k$ nonempty fibres, which form a partition of $[n]$ into exactly $k$ blocks; conversely, labelling the $k$ blocks of any such partition by the elements of $[k]$ recovers a surjection. By [L3], there are therefore $k!S(n,k)$ surjections.

For unlabelled balls and labelled boxes, the data are occupancy vectors $(a_1,\dots ,a_k)$. Arbitrary placements are weak compositions, so clause 4 is [L4]. Surjective placements are positive compositions, so clause 6 is [L4]. Injective placements are exactly the $0$-$1$ occupancy vectors with total $n$, so one chooses which $n$ of the $k$ labelled boxes are occupied; this gives clause 5, namely $\left(\genfrac{}{}{0px}{}{k}{n}\right)$.

For labelled balls and unlabelled boxes, one remembers only the fibres and forgets their labels. Thus a surjective placement is exactly a partition of $[n]$ into $k$ nonempty blocks, giving clause 9 as $S(n,k)$ by [L3]. An arbitrary placement uses some number $j$ of nonempty boxes with $1\le j\le \min (n,k)$, so clause 7 is the sum of the counts $S(n,j)$ over those $j$. For injective placements every fibre is a singleton, hence there is one orbit when $n\le k$ and none when $n>k$, proving clause 8.

Clauses 10, 11, and 12 are exactly the three conclusions of [L5].

Let $\lambda =({\lambda }_1>\cdots >{\lambda }_{\mathrm{\ell }})$ be a nonempty partition into distinct parts. Write $s={\lambda }_{\mathrm{\ell }}$ for its smallest part, and let $t$ be the largest index such that ${\lambda }_i={\lambda }_1-i+1$ for every $1\le i\le t$. Thus the first $t$ rows form the maximal upper-right staircase. If $s\le t$ and $\lambda \mathrm{\ne }(2s-1,2s-2,\dots ,s)$, define $\alpha (\lambda )$ by deleting the last part $s$ and adding $1$ to each of the first $s$ parts. If $s>t$ and $\lambda \mathrm{\ne }(2t,2t-1,\dots ,t+1)$, define $\beta (\lambda )$ by subtracting $1$ from each of the first $t$ parts and adjoining a new last part $t$.

In the first case of step 1.1, the partition $\alpha (\lambda )$ is still distinct: the first $s$ parts remain strictly decreasing, the last changed part satisfies ${\lambda }_s+1>{\lambda }_{s+1}$ because those rows were consecutive, and deleting the old last part decreases the number of parts by $1$. The first $s$ parts of $\alpha (\lambda )$ are consecutive and its smallest part is larger than $s$, so $\alpha (\lambda )$ falls under the second construction with parameter $t=s$, and $\beta (\alpha (\lambda ))=\lambda$.

In the second case of step 1.1, the partition $\beta (\lambda )$ is still distinct: maximality of $t$ gives ${\lambda }_t-1>{\lambda }_{t+1}$, while the new last part $t$ is smaller than the previous smallest part because $s>t$. The first $t$ parts of $\beta (\lambda )$ are consecutive and its smallest part is exactly $t$, so $\beta (\lambda )$ falls under the first construction with parameter $s=t$, and $\alpha (\beta (\lambda ))=\lambda$. Thus steps 2.1 and 2.2 define a sign-reversing involution on all nonexceptional nonempty distinct partitions.

The empty partition contributes the constant term $1$. The only nonempty distinct partitions excluded from step 1.1 are the two staircase families $(2k-1,2k-2,\dots ,k)$ and $(2k,2k-1,\dots ,k+1)$. Their sizes are $k+(k+1)+\cdots +(2k-1)=k(3k-1)\mathrm{/}2$ and $(k+1)+(k+2)+\cdots +2k=k(3k+1)\mathrm{/}2$, and each has exactly $k$ parts, so each contributes the sign $(-1{)}^k$.

By step 2.2, all nonexceptional nonempty distinct partitions cancel in opposite-parity pairs. Step 2.3 leaves only the empty partition and the two exceptional staircase families, so [F2] gives ${\prod }_{m\ge 1}(1-x^m)=1+{\sum }_{k\ge 1}(-1{)}^k(x^{k(3k-1)\mathrm{/}2}+x^{k(3k+1)\mathrm{/}2})$, equivalently the two-sided sum over $r\in \mathbb{Z}$.

Multiply the identities of [L1] and [L2]. The two products are reciprocals, so $P(x){\sum }_{r\in \mathbb{Z}}(-1{)}^r{x}^{r(3r-1)\mathrm{/}2}=1$.

By [L3], the coefficient of $x^n$ on the left side of step 1.1 is ${\sum }_{r\in \mathbb{Z}}(-1{)}^{r}p\text{\hspace{0.17em}⁣}(n-\frac{r(3r-1)}{2})$, with the convention $p(m)=0$ for $m<0$. The coefficient on the right side is $0$ when $n>0$ and $1$ when $n=0$. This proves the equivalent formulation.

For $n>0$, isolate the $r=0$ term in step 2.1. The remaining nonzero terms occur in the pairs $r=\pm 1,\pm 2,\dots$, whose offsets are $1,2,5,7,12,15,\dots$. Moving them to the other side yields the displayed recurrence for $p(n)$.

Using [L1], one gets $p_3(5)=p_2(4)+p_3(2)=2+0=2$, corresponding to the two partitions $3+1+1$ and $2+2+1$.

By [L2], one has $\left(\genfrac{}{}{0px}{}{5-1}{3-1}\right)=\left(\genfrac{}{}{0px}{}{4}{2}\right)=6$.

Steps 1.1 and 1.2 give $p_3(5)=2\mathrm{\ne }6=\left(\genfrac{}{}{0px}{}{4}{2}\right)$, so the displayed claim is false. The binomial coefficient counts ordered compositions, not unordered partitions.

The Ferrers diagram of $(4,2,1)$ has column lengths $3,2,1,1$, so [L1] gives $(4,2,1{)}^{\mathrm{\prime }}=(3,2,1,1)$.

The conjugate partition $(3,2,1,1)$ has an even part, namely $2$, so it is not a partition into odd parts.

Therefore conjugation does not send every distinct-part partition to an odd-part partition, and the displayed claim is false. By [L2], the correct bijection is a different map.