Chapter 7: Partitions and Structure Types

Why do compositions and partitions have different counts?

Grouping four identical units into non-empty batches illustrates a fundamental combinatorics lesson: the exact counting model depends on whether order matters and whether elements are labeled.

Four identical units must be grouped into nonempty batches. If the batches are processed in sequence, a batch of three followed by a batch of one differs from a batch of one followed by a batch of three. If we care only about batch sizes, those descriptions represent the same grouping.

An ordered list of positive sizes summing to four is a composition of four. An unordered collection of positive sizes summing to four is an integer partition of four. We write an integer partition in decreasing order to give it a unique representation.

There is a third model. If the units are four distinct tasks, a grouping must record which tasks belong together. This is a set partition. Two groupings can have the same block sizes but different memberships.

The word “partition” therefore needs an object and a convention: are we partitioning an integer into sizes, or a labeled set into blocks? Are the parts ordered? Are empty parts permitted? Answering these questions determines the count.

---

7.1 Compositions of integers

A composition of a positive integer $n$ is an ordered tuple $(a_1,\ldots,a_k)$ of positive integers with sum $n$. Its length is the number of parts $k$. For example, $(1,3,2)$ is a length-three composition of six.

Place $n$ units in a row. There are $n-1$ gaps between consecutive units. Choose which gaps receive cuts; each resulting segment contributes its positive length. For $n=6$, cutting after units one and four produces $(1,3,2)$.

Conversely, a composition determines its cuts through the partial sums $a_1,a_1+a_2,\ldots,a_1+\cdots+a_{k-1}$. These lie in $\{1,\ldots,n-1\}$ and recover the original segments. This proves a bijection between compositions of $n$ and subsets of the $n-1$ gaps.

Therefore, for $n\ge1$,

$$\#\{\text{compositions of }n\}=2^{n-1},$$

and, for $1\le k\le n$,

$$\#\{\text{length-}k\text{ compositions of }n\} =\binom{n-1}{k-1}.$$

Exactly $k-1$ cuts produce $k$ positive parts. Summing over lengths gives the row-sum identity for row $n-1$ of Pascal's triangle.

Worked example. The six length-three compositions of five are

$$(1,1,3),\ (1,2,2),\ (1,3,1),\ (2,1,2),\ (2,2,1),\ (3,1,1).$$

Their count is $\binom{4}{2}=6$. The cuts for $(2,1,2)$ occur after units two and three.

A weak composition permits zero parts, but its length must be fixed. For $n\ge0$ and $k\ge1$, Chapter 4's stars-and-bars bijection gives $\binom{n+k-1}{k-1}$ weak compositions of length $k$. Allowing arbitrary lengths would produce infinitely many descriptions by adding zeros.

We adopt one composition of zero: the empty tuple, of length zero. No positive-length composition with positive parts sums to zero. The formula $2^{n-1}$ is stated only for $n\ge1$.

Exercise. Count compositions of seven into exactly three positive parts. Hint: Choose two cuts from six gaps. Answer: $\binom{6}{2}=15$.

---

7.2 Set partitions and Stirling numbers of the second kind

A set partition of a finite set is a collection of nonempty, pairwise disjoint subsets called blocks, whose union is the entire set. The blocks have no order, and the elements within a block have no order. For example, $\{\{1,3\},\{2\}\}$ partitions $\{1,2,3\}$ into two blocks.

Write $S(n,k)$ for the Stirling number of the second kind, the number of partitions of an $n$-element labeled set into exactly $k$ blocks. The boundary values are

$$S(0,0)=1,\qquad S(n,0)=0\ (n\ge1),\qquad S(0,k)=0\ (k\ge1).$$

There are no partitions into more than $n$ nonempty blocks, so $S(n,k)=0$ for $k > n$.

Recurrence. For $n\ge1$ and $k\ge1$,

Distinguish element $n$. If it forms a singleton block, partition the other elements into $k-1$ blocks. Otherwise remove $n$ from its block; the remaining partition still has $k$ nonempty blocks, and there are $k$ choices of block into which to restore it. These cases are disjoint, and each construction has a unique inverse.

This also connects partitions to functions. A surjection from an $n$-element set onto $k$ labeled outputs determines $k$ nonempty fibers. Forgetting the output labels gives a set partition. Each partition has exactly $k!$ assignments of its blocks to the outputs, so the surjection count is $k!S(n,k)$.

---

7.3 Integer partitions and Ferrers/Young diagrams

An integer partition of $n\ge1$ is a sequence

$$\lambda=(\lambda_1,\ldots,\lambda_k),\qquad \lambda_1\ge\cdots\ge\lambda_k\ge1,\qquad \lambda_1+\cdots+\lambda_k=n.$$

The decreasing convention records an unordered multiset of positive sizes exactly once. Write $\lambda\vdash n$ to mean that $\lambda$ partitions $n$, and write $p(n)$ for the number of such partitions. Set $p(0)=1$, corresponding to the empty partition.

Worked example. The five partitions of four are $(4)$, $(3,1)$, $(2,2)$, $(2,1,1)$, and $(1,1,1,1)$. These are size patterns, rather than assignments of labeled objects to groups.

Their relationship to set partitions is visible in this table:

The total is $15$, although there are only five integer partitions. Sorting the block sizes forgets memberships, and different patterns have different numbers of labeled realizations.

A Ferrers diagram represents each part by a row of dots. A Young diagram uses square cells instead. We use the English convention: rows are left-justified, with the longest row at the top. Other drawing conventions exist, so the orientation should always be stated.

For $\lambda=(4,2,1)$, the rows contain four, two, and one units. The two diagrams below represent the same partition of seven. The orange region marks a square of side two; Section 7.6 will explain its role.

Drawing rows from the parts and reading their lengths back are inverse operations. This representation makes restrictions geometric: a bound on the largest part is a bound on width, and a bound on the number of parts is a bound on height.

Exercise. List all partitions of five into exactly two positive parts. Hint: The smaller part is at most two. Answer: $(4,1)$ and $(3,2)$.

---

7.4 Bell numbers and restricted-growth strings

The Bell number $B_n$ counts all set partitions of an $n$-element labeled set, regardless of their number of blocks. Thus

$$B_n=\sum_{k=0}^n S(n,k),\qquad B_0=1.$$

The first values are $B_0=1$, $B_1=1$, $B_2=2$, $B_3=5$, and $B_4=15$. These are counts of set partitions, not integer partitions.

For an algorithm, unordered blocks need a canonical encoding. Order the blocks by their least elements and label them $0,1,2,\ldots$. For each element $i$ in the ordered set $\{1,\ldots,n\}$, record the label of its block. The resulting restricted-growth string $(r_1,\ldots,r_n)$ satisfies

A newly encountered block receives the next unused label; an existing block keeps its label. Conversely, a string satisfying this rule groups elements with equal labels, and the rule guarantees that labels appear in the required order. This is a bijection, so the encoding introduces no duplicate block orderings.

Worked example. Partition $\{1,3\}\mid\{2,4\}$ becomes $0101$. The five strings for a three-element set are

$$000,\quad001,\quad010,\quad011,\quad012.$$

They encode respectively one block; block pair $\{1,2\}\mid\{3\}$; block pair $\{1,3\}\mid\{2\}$; block pair $\{1\}\mid\{2,3\}$; and three singleton blocks. The number of blocks in a nonempty string is one plus its maximum label.

A recursive generator starts with $0$ and, after a prefix with maximum label $m$, tries each next label in $\{0,\ldots,m+1\}$. Each valid string follows exactly one path. The empty string represents the unique partition of the empty set.

Another Bell recurrence is

$$B_{n+1}=\sum_{j=0}^n\binom{n}{j} B_j.$$

Distinguish the new element. Choose the $j$ old elements outside its block, partition those elements in $B_j$ ways, and place every remaining element in the distinguished block. The outside set and its partition are uniquely recoverable. For $n=3$, this gives $B_4=1+3+6+5=15$.

Exercise. Decode $0012$ and state its number of blocks. Hint: Group element positions carrying the same label. Answer: $\{1,2\}\mid\{3\}\mid\{4\}$, with three blocks.

---

7.5 Partition identities, including Euler's identity

A partition identity equates two restricted families of integer partitions. A good proof explains how to transform an object from one family into an object from the other and how to reverse that transformation.

Euler's odd–distinct identity. For every integer $n\ge0$, the number of partitions of $n$ into odd parts equals the number of partitions of $n$ into distinct parts. Odd parts may repeat; distinct parts may be even or odd. At $n=0$, both families contain the empty partition.

Bijection from odd parts to distinct parts. For each odd positive integer $u$, let $m_u$ be its multiplicity. Write that multiplicity in binary:

$$m_u=\sum_{j\ge0}\varepsilon_{u,j}2^j, \qquad \varepsilon_{u,j}\in\{0,1\}.$$

For every nonzero digit, replace the corresponding $2^j$ copies of $u$ by one part $2^ju$. The total is preserved. The resulting parts are distinct: every positive integer has a unique factorization as a power of two times an odd integer, so two different pairs $(u,j)$ cannot produce the same part.

Inverse. For each distinct part, write it uniquely as $2^ju$ with $u$ odd, then replace it by $2^j$ copies of $u$. Distinct parts with the same odd factor correspond to different binary digits. Uniqueness of the binary expansion proves that both transformations undo one another.

Worked example. The odd-part partition

$$5+3+1+1+1+1+1=13$$

has five copies of one. Since $5=4+1$ in powers of two, those copies become parts $4$ and $1$. The image is the distinct-part partition $5+4+3+1$. Replacing the part $4$ by four ones recovers the original partition.

For $n=6$, the correspondence is:

There are four objects in each family.

A generating-function view. A formal generating function records the count of total $n$ as the coefficient of $x^n$. For distinct parts, each size $r$ is absent or appears once, giving the factor $1+x^r$. For odd parts, each odd size can appear any number of times, giving a geometric-series factor. Thus

$$\prod_{r\ge1}(1+x^r) =\prod_{r\ge1}\frac{1-x^{2r}}{1-x^r} =\prod_{\substack{r\ge1\\r\text{ odd}}}\frac1{1-x^r}.$$

The middle expression cancels the factors for even sizes. This is a formal identity: for any fixed coefficient, only finitely many sizes matter. Section 7.7 develops this interpretation locally; the fuller treatment in Chapter 10, Section 10.1, is listed in the series roadmap. That later chapter is optional background, not an entry requirement here.

Exercise. List the odd-part and distinct-part partitions of five and pair them using the bijection. Hint: Five copies of one become parts four and one. Answer: $5\leftrightarrow5$, $3+1+1\leftrightarrow3+2$, and $1+1+1+1+1\leftrightarrow4+1$.

---

7.6 Durfee squares and conjugate partitions

The conjugate partition $\lambda'$ is obtained by transposing the Young diagram: its rows are the original columns. Formally,

$$\lambda'_j=\#\{i:\lambda_i\ge j\}.$$

The diagram of $(4,2,1)$ has column heights $3,2,1,1$, so its conjugate is $(3,2,1,1)$. Transposition preserves the number of cells and applying it twice restores the diagram. Thus conjugation is a bijection and an involution.

The largest part of $\lambda'$ is the number of parts of $\lambda$, and the number of parts of $\lambda'$ is the largest part of $\lambda$. Consequently, for every $n\ge0$ and $k\ge0$, conjugation pairs partitions of $n$ into at most $k$ parts with partitions of $n$ whose parts are at most $k$.

For example, the partitions of five into at most two parts are $(5)$, $(4,1)$, and $(3,2)$. Their conjugates are $(1,1,1,1,1)$, $(2,1,1,1)$, and $(2,2,1)$, exactly the partitions of five with largest part at most two.

The Durfee square is the largest square of cells in the upper-left corner of the diagram. Its side length is

$$d=\max\{i:\lambda_i\ge i\},$$

with $d=0$ for the empty partition. For $(4,2,1)$, the second row has at least two cells but the third has fewer than three, so $d=2$.

Removing the Durfee square leaves two independent pieces. To its right are row lengths

$$\alpha=(\lambda_1-d,\ldots,\lambda_d-d),$$

with zero entries omitted, so $\alpha$ has at most $d$ parts. Below it is $\beta=(\lambda_{d+1},\lambda_{d+2},\ldots)$, whose parts are at most $d$ because the square was maximal.

Worked decomposition. For $(4,2,1)$, the square contains four cells, the right piece is $(2)$, and the lower piece is $(1)$. Hence $7=4+2+1$.

Conversely, given $d$, a partition $\alpha$ with at most $d$ parts, and a partition $\beta$ with parts at most $d$, pad $\alpha$ with zeros to length $d$, add $d$ to each entry, and append the parts of $\beta$. The result is decreasing and has Durfee side exactly $d$. This reconstructs the original partition uniquely. Conjugation exchanges the roles of the right and lower pieces, transposing each.

Exercise. Find the conjugate and Durfee side of $(3,3,1)$. Hint: Count the heights of its three columns. Answer: Its conjugate is $(3,2,2)$, and its Durfee side is two.

---

7.7 Restricted partitions and partition generating functions

A restriction may specify allowed part sizes, multiplicities, the number of parts, or a diagram's dimensions. A generating function organizes these counts without requiring the later general theory.

For a formal series $F(x)=\sum_{n\ge0}a_nx^n$, the coefficient $a_n$ is recorded as $[x^n]F(x)$. Multiplication combines independent choices and adds their totals. Each coefficient calculation involves finitely many contributing choices in the products below, so no numerical convergence assumption is needed.

If positive part size $a$ is available without limit, its multiplicities contribute

$$1+x^a+x^{2a}+\cdots=\frac1{1-x^a}.$$

For an allowed set $A$ of positive sizes,

$$\#\{\text{partitions of }n\text{ with parts in }A\} =[x^n]\prod_{a\in A}\frac1{1-x^a}.$$

Each partition determines one multiplicity for every allowed size, and every such multiplicity choice determines one partition. We multiply once per size, so parts are not ordered. For a count up to total $N$, sizes greater than $N$ may be omitted even if $A$ is infinite.

Worked example. With allowed sizes $A=\{1,3,4\}$ and total six, the partitions are

$$4+1+1,\qquad3+3,\qquad3+1+1+1,\qquad1+1+1+1+1+1.$$

The count is four, the coefficient of $x^6$ in $1/((1-x)(1-x^3)(1-x^4))$.

Common restrictions modify the factors:

Consequently, the coefficient of $x^ny^k$ in $\prod_{a\ge1}(1-yx^a)^{-1}$ counts partitions of $n$ into exactly $k$ parts.

For unrestricted partitions,

$$P(x)=\sum_{n\ge0}p(n)x^n=\prod_{a\ge1}\frac1{1-x^a}.$$

Conjugation shows that partitions into at most $d$ parts have the same generating function as partitions with largest part at most $d$, namely $\prod_{a=1}^d(1-x^a)^{-1}$. The Durfee decomposition therefore gives another identity:

The square contributes $d^2$ cells; the right and lower pieces each contribute one of the two product factors. At any total $n$, only $d^2\le n$ can contribute. The $d=0$ term is one, using the empty-product convention.

Computing coefficients. For a finite allowed set $A$ and maximum total $N$, initialize $D(0)=1$ and $D(s)=0$ for $1\le s\le N$. Process each distinct allowed size $a$ once. For totals $s=a,a+1,\ldots,N$ in increasing order, replace $D(s)$ by $D(s)+D(s-a)$.

Before processing $a$, the array counts partitions using the previously processed sizes. At total $s$, the old term counts partitions with no copy of $a$; the already updated term at $s-a$ counts partitions with at least one copy after appending $a$. This invariant proves correctness. The increasing total order permits repeated use of the current size. For $A=\{1,3,4\}$, the final counts at totals zero through six are $1,1,1,2,3,3,4$.

The algorithm uses $O(|A|N)$ integer additions and $O(N)$ array entries. Exact counts can grow large, so these are arithmetic-operation bounds. Reversing the nesting of the size and total loops changes the counting interpretation and can count ordered compositions instead.

The broader ordinary-generating-function framework appears in Chapter 10, Section 10.1, listed in the series roadmap; everything needed for these products has been introduced here.

Exercise. Count partitions of five with largest part at most two. Hint: Use the coefficient of $x^5$ in $1/((1-x)(1-x^2))$. Answer: Three: $1+1+1+1+1$, $2+1+1+1$, and $2+2+1$.

---

7.8 Introduction to Young tableaux

Optional extension. A Young diagram records a shape. A Young tableau fills that shape with entries subject to rules. This section is not required for the chapter foundation.

A standard Young tableau of shape $\lambda\vdash n$ places the labels $1,2,\ldots,n$ into its cells, each exactly once, so that entries increase from left to right along rows and from top to bottom along columns. Write $f^\lambda$ for its count, with $f^{\varnothing}=1$.

Worked example. Shape $(3,2)$ has three cells in its top row and two directly beneath the first two. Its five standard tableaux are specified by these row entries:

The bottom entries align under the first two top entries. Check the row and column inequalities directly. Choosing any three labels for the top row and sorting both rows would give $\binom{5}{3}=10$ fillings with increasing rows, but only these five also satisfy the column conditions.

Why is the list complete? The largest label must occupy a removable corner: a cell with no cell immediately to its right or below, whose removal leaves a Young diagram. Removing that cell leaves a standard tableau of the smaller shape. Conversely, placing the new largest label in such a corner preserves all inequalities. Hence

$$f^\lambda=\sum_{c\text{ a removable corner of }\lambda}f^{\lambda\setminus c}.$$

For $(3,2)$, removing a corner gives shape $(2,2)$ or $(3,1)$. Their counts are two and three, respectively: $f^{(2,2)}=2$ and $f^{(3,1)}=3$. Thus $f^{(3,2)}=2+3=5$, proving completeness independently of the displayed list. These smaller counts follow by the same corner recurrence or direct listing.

A semistandard Young tableau uses positive integer entries that weakly increase along rows and strictly increase down columns; repetitions are allowed. For example, top row $(1,1,3)$ and bottom row $(2,2)$ give a semistandard tableau of shape $(3,2)$. It is not standard because labels repeat.

Tableaux also describe legal task orders. Regard each cell as a task that must occur after the cell immediately to its left and the cell immediately above it, when those cells exist. Labeling cells by their execution times gives exactly a standard tableau. Thus $f^\lambda$ counts the possible execution orders for this dependency pattern.

Exercise. List the standard tableaux of shape $(2,1)$. Hint: The upper-left cell must contain one. Answer: Top row $(1,2)$ with bottom entry $3$, or top row $(1,3)$ with bottom entry $2$; the count is two.

---

Construct partition bijections and enumerate restricted families

The chapter's models preserve different information. A composition records ordered sizes. An integer partition forgets their order. A set partition retains labeled memberships while forgetting block order. A Young tableau adds an ordered labeling to a diagram under row and column restrictions.

There is a concrete bridge from compositions to tableaux. For fixed shape $(3,2)$, the row sizes form the ordered size list $(3,2)$. Assigning five distinct labels to those rows and then sorting each row gives $5!/(3!2!)=10$ fillings. Column inequalities restrict that family to five standard tableaux. The composition specifies row sizes; the tableau records which labels occupy those positions and whether the dependencies are respected.

These distinctions matter in applications. Grouping distinct records into unlabeled clusters is a set-partition problem; retaining only the cluster-size distribution is an integer-partition problem. Scheduling batches in a fixed sequence uses compositions. Executing tasks with the diagram dependencies from Section 7.8 uses tableaux. Changing the representation changes which outcomes are considered distinct.