40.01.01 · combinatorics / enumeration-generating-functions

Basic Counting and the Twelvefold Way

shipped3 tiersLean: none

Anchor (Master): Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §1.2-1.9 and Notes (Rota's twelvefold way, the q-analogues, the exponential formula prelude); Rota 1964 *Amer. Math. Monthly* 71 (the Mobius-function programme that frames enumeration); Andrews 1976 *The Theory of Partitions* Ch. 1 for the integer-partition column

Intuition Beginner

Counting sounds like the easiest thing in mathematics, and for small collections it is: you point at the things and recite numbers. The difficulty starts when the collection is described rather than displayed. How many five-letter passwords are there? How many ways can ten students be sorted into three project teams? How many ways can you make change for a dollar? You cannot point at these things one at a time, because there are far too many. You need rules that count without listing.

Two rules do most of the work. The first is the sum rule: if a choice can be made in one of two separate ways, with no overlap, the total number of outcomes is the two counts added. The second is the product rule: if a task breaks into steps done one after another, and each step has its own number of options regardless of the earlier choices, the total is the counts multiplied. A meal with three starters and four mains offers three plus four single dishes but three times four full meals.

The deepest counting trick is the bijection: to count a hard collection, match its members one-for-one with the members of an easier collection you already understand. If every item in one bag pairs with exactly one item in another bag and nothing is left over, the two bags hold the same number of items, even if you never count either bag directly. Most of the surprising formulas in this unit are really just one well-chosen pairing.

The organising idea of this unit is that an enormous range of counting questions are secretly the same question asked twelve different ways. You are placing some balls into some boxes, and the answer depends only on four yes-or-no settings: are the balls labelled, are the boxes labelled, and do you forbid two balls sharing a box, or instead require every box to be used? Those settings give a table of twelve famous answers — the twelvefold way — and learning to read the table replaces memorising a dozen formulas.

Visual Beginner

Picture $n$ balls and $k$ boxes. A way of placing the balls is a rule that assigns each ball to a box. Whether two placements count as the same depends on what you can tell apart. If the balls carry names you can distinguish them; if not, only the count in each box matters. The same holds for the boxes.

The table below names the twelve cells. Across the top: are the balls (the $n$ elements being placed) distinguishable, and are the boxes (the $k$ targets) distinguishable. Down the side: is the placement unrestricted, at most one per box (injective), or every box used (surjective).

balls \ boxes	any placement	at most one per box	every box used
labelled balls, labelled boxes	$k^{n}$	$k (k - 1) \dots (k - n + 1)$	surjections, $k! S (n, k)$
plain balls, labelled boxes	multiset count	$(n k)$	$(n - k n - 1)$
labelled balls, plain boxes	$S (n, 0) + \dots + S (n, k)$	one if $n \leq k$ , else zero	$S (n, k)$
plain balls, plain boxes	partitions of $n$ into $\leq k$ parts	one if $n \leq k$ , else zero	partitions of $n$ into exactly $k$ parts

Every entry is a count you can verify by hand for small $n$ and $k$ , and the rest of the unit explains where each one comes from.

Worked example Beginner

Place $n = 3$ labelled balls, call them $1, 2, 3$ , into $k = 2$ labelled boxes, call them $A$ and $B$ . We fill in the top row of the table for these numbers.

Step 1. Any placement. Each ball independently picks a box: ball $1$ has $2$ choices, ball $2$ has $2$ choices, ball $3$ has $2$ choices. By the product rule the total is $2 \times 2 \times 2 = 8$ . Listing confirms it: $AAA, AA B, A B A, A B B, B AA, B A B, B B A, B B B$ , where the three letters say where balls $1, 2, 3$ go.

Step 2. At most one ball per box. With only $2$ boxes and $3$ balls, some box must receive two balls, so no placement avoids a repeat. The count is $0$ , matching the falling-factorial rule $2 \times 1 \times 0 = 0$ once the third factor reaches zero.

Step 3. Every box used. From the $8$ placements in Step 1, remove the two that leave a box empty: $AAA$ uses only $A$ , and $B B B$ uses only $B$ . That leaves $8 - 2 = 6$ placements in which both boxes are occupied. The formula $k! S (n, k) = 2! \times S (3, 2)$ gives $2 \times 3 = 6$ , where $S (3, 2) = 3$ counts the ways to split three balls into two unlabelled groups.

What this tells us: a single small example pins down three different cells of the table, and the formulas agree with brute-force listing. The product rule handles the unrestricted case, a falling product handles the no-repeat case, and removing the empty-box placements handles the every-box-used case.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $N$ is a set of size $n$ and $X$ a set of size $k$ ; we count maps $f : N \to X$ . The four symmetry regimes arise because two finite symmetric groups act: $Sym (N)$ by precomposition $f \mapsto f \circ σ^{- 1}$ (relabelling the domain) and $Sym (X)$ by postcomposition $f \mapsto τ \circ f$ (relabelling the codomain). Declaring the elements of $N$ distinguishable or not amounts to counting maps, or $Sym (N)$ -orbits of maps; likewise for $X$ and $Sym (X)$ .

Definition (ordinary and falling powers). The ordinary power is $x^{n} = x \cdot x \dots x$ ( $n$ factors). The falling factorial is $(x)_{n} = x (x - 1) (x - 2) \dots (x - n + 1)$ , a product of $n$ terms, with $(x)_{0} = 1$ . The rising factorial is $x^{(n)} = x (x + 1) \dots (x + n - 1)$ . For a set of size $k$ , the number of functions $N \to X$ is $k^{n}$ and the number of injective functions is $(k)_{n}$ .

Definition (binomial and multiset coefficients). The binomial coefficient $(k n) = \frac{n !}{k ! ( n - k )!}$ counts the $k$ -element subsets of an $n$ -set. The multiset coefficient $((n k)) = (n k + n - 1)$ counts the $n$ -element multisets drawn from a $k$ -set, equivalently the weak compositions $a_{1} + \dots + a_{k} = n$ with $a_{i} \in Z_{\geq 0}$ .

Definition (Stirling numbers). The Stirling number of the second kind $S (n, k)$ is the number of partitions of an $n$ -set into exactly $k$ nonempty unlabelled blocks. The (unsigned) Stirling number of the first kind $c (n, k)$ is the number of permutations of an $n$ -set with exactly $k$ cycles. The signed Stirling number of the first kind is $s (n, k) = (- 1)^{n - k} c (n, k)$ . These are the entries of the two change-of-basis matrices between the monomial basis ${x^{n}}$ and the falling-factorial basis ${(x)_{n}}$ of the polynomial ring, defined by $$ (x)n = \sum{k=0}^{n} s(n,k),x^k, \qquad x^n = \sum_{k=0}^{n} S(n,k),(x)_k . $$

Definition (integer partitions). A partition of $n$ into at most $k$ parts is a sequence $λ_{1} \geq λ_{2} \geq \dots \geq λ_{k} \geq 0$ of integers summing to $n$ ; we write $p_{\leq k} (n)$ for the count, and $p_{= k} (n)$ for the count with all $λ_{i} \geq 1$ (exactly $k$ positive parts). The elementary/bijective theory of these counts is owned here; their analytic and generating-function depth is developed at 21.16.01.

Definition (twelvefold way). The twelvefold way is the $3 \times 4$ table whose entry is the number of maps $f : N \to X$ counted (rows) without restriction, with $f$ injective, or with $f$ surjective, and (columns) with $N$ and $X$ each either distinguishable (count maps) or indistinguishable (count $Sym (N)$ - or $Sym (X)$ -orbits). The twelve cells are filled by the objects above, as tabulated in the Visual section and proved below.

Counterexamples to common slips Intermediate+

"Multisets are counted by $k^{n}$ ." The count $k^{n}$ is for functions (labelled balls into labelled boxes, any placement). An $n$ -multiset from a $k$ -set forgets the labels on the balls, so it is the $Sym (N)$ -orbit count $(n k + n - 1)$ , generally far smaller. For $n = k = 3$ the function count is $27$ while the multiset count is $(3 5) = 10$ .
" $S (n, k)$ counts surjections onto a $k$ -set." It counts set partitions into $k$ unlabelled blocks. Surjections onto a labelled $k$ -set are $k! S (n, k)$ , since each partition can be matched to the $k$ boxes in $k!$ ways. Confusing the two drops or inserts a factor of $k!$ .
"Injective and surjective are symmetric, so their indistinguishable-codomain cells look alike." They are not symmetric here. The injective cell with plain boxes is $1$ when $n \leq k$ and $0$ otherwise (an injection into unlabelled boxes records only whether it fits), whereas the surjective cell with plain boxes is $S (n, k)$ , a rich count.
" $(x)_{n}$ means $x$ to the $n$ , just written oddly." The falling factorial $(x)_{n} = x (x - 1) \dots (x - n + 1)$ agrees with $x^{n}$ only at $n = 0, 1$ . The two bases are related by the Stirling numbers, not by a typographical convention.

Key theorem with proof Intermediate+

The signature theorem is the closed form for the labelled-into-labelled surjective cell, because it forces the appearance of the Stirling numbers of the second kind and ties the surjection count to set partitions and to inclusion-exclusion in one stroke.

Theorem (surjection count). The number of surjective functions from an $n$ -set onto a $k$ -set is $$ \operatorname{Surj}(n,k) ;=; k!,S(n,k) ;=; \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n . $$

Proof. First we prove $Surj (n, k) = k! S (n, k)$ by a bijection. A surjection $f : N \to X$ has fibres $f^{- 1} (x_{1}), \dots, f^{- 1} (x_{k})$ , which are nonempty (by surjectivity), pairwise disjoint, and cover $N$ ; they form an ordered partition of $N$ into $k$ nonempty blocks, the order being the labelling of $X$ . Conversely an unordered partition of $N$ into $k$ nonempty blocks, together with a bijection from the $k$ blocks to the $k$ elements of $X$ , determines a surjection. The number of unordered partitions into $k$ blocks is $S (n, k)$ by definition, and the number of bijections from the blocks to $X$ is $k!$ . Composing these choices is a bijection between surjections and (partition, labelling) pairs, so $Surj (n, k) = k! S (n, k)$ .

Next the inclusion-exclusion form. For a subset $T \subseteq X$ let $A_{T}$ be the set of functions $N \to X$ whose image misses every element of $T$ , i.e. lands in $X ∖ T$ ; then $∣ A_{T} ∣ = (k - ∣ T ∣)^{n}$ . A function is a surjection precisely when it lies in none of the sets $A_{{x}}$ for $x \in X$ . By the inclusion-exclusion principle, $$ \operatorname{Surj}(n,k) = \sum_{T \subseteq X} (-1)^{|T|} |A_T| = \sum_{j=0}^{k} (-1)^j \binom{k}{j}(k-j)^n, $$ grouping the $(j k)$ subsets $T$ of each size $j$ . Both expressions count the same set of surjections, so they are equal, and in particular $S (n, k) = \frac{1}{k !} \sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}$ . $□$

Corollary (Stirling recurrence). For $1 \leq k \leq n$ , $S (n, k) = k S (n - 1, k) + S (n - 1, k - 1)$ , with $S (0, 0) = 1$ and $S (n, 0) = 0$ for $n \geq 1$ . Indeed, in any partition of ${1, \dots, n}$ into $k$ blocks the element $n$ either sits in a block by itself — leaving a partition of the remaining $n - 1$ elements into $k - 1$ blocks, counted by $S (n - 1, k - 1)$ — or joins one of the $k$ blocks of a partition of the first $n - 1$ elements, giving $k S (n - 1, k)$ . The two cases are disjoint and exhaustive.

Bridge. This theorem is the foundational reason the twelvefold table is one object rather than twelve coincidences: every cell is an orbit count of the function space $X^{N}$ under a subgroup of $Sym (N) \times Sym (X)$ , and the surjective–labelled–labelled cell is the hinge where the orbit count $S (n, k)$ first appears multiplied by the codomain symmetry $k!$ . The two formulas for $Surj (n, k)$ are dual descriptions of the same set — one bijective, one by inclusion-exclusion — and this is exactly the pattern that builds toward the generating-function machinery of the chapter, where the same counts reappear as coefficients: $\sum_{n} S (n, k) x^{n} / n!$ has the closed form $(e^{x} - 1)^{k} / k!$ , putting these together so that the exponential generating function repackages the surjection count as a product. The bijective half generalises to the orbit-counting (Burnside) reading of all twelve cells, and the inclusion-exclusion half is the central insight that links elementary counting to the Mobius function on the Boolean lattice, which appears again in 40.02.01 as Mobius inversion on a poset.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the stars-and-bars formula: the number of weak compositions $a_{1} + a_{2} + \dots + a_{k} = n$ with each $a_{i} \in Z_{\geq 0}$ is $(k - 1 n + k - 1)$ .

Hint

Encode a solution as a row of $n$ stars and $k - 1$ bars: the bars split the stars into $k$ runs whose lengths are $a_{1}, \dots, a_{k}$ . Count arrangements of the symbols.

Answer

Represent a solution by a sequence of $n$ stars and $k - 1$ bars in a row of length $n + (k - 1)$ . The bars cut the row into $k$ (possibly empty) blocks; let $a_{i}$ be the number of stars in the $i$ -th block. Reading left to right gives a weak composition with $\sum_{i} a_{i} = n$ , and every weak composition arises from exactly one such arrangement, since the block lengths determine the bar positions and conversely. The number of arrangements is the number of ways to choose which $k - 1$ of the $n + k - 1$ positions hold bars, namely $(k - 1 n + k - 1) = (n n + k - 1)$ . This is a bijection between solutions and bar-placements, so the counts coincide. Rubric: full credit for the explicit bijection (both directions stated) and the resulting binomial count.

Exercise 4 (medium, symbolic).

Prove Vandermonde's identity $(r m + n) = \sum_{j = 0}^{r} (j m) (r - j n)$ by a counting argument.

Hint

Count $r$ -subsets of a set split into a part of size $m$ and a part of size $n$ . Sort by how many chosen elements come from the first part.

Answer

Split a set $S$ of size $m + n$ as $S = A ⊔ B$ with $∣ A ∣ = m$ , $∣ B ∣ = n$ . The left side $(r m + n)$ counts the $r$ -element subsets of $S$ . Classify each such subset by the number $j$ of its elements lying in $A$ ; then $r - j$ of its elements lie in $B$ , with $0 \leq j \leq r$ . For fixed $j$ there are $(j m)$ ways to choose the part in $A$ and $(r - j n)$ ways to choose the part in $B$ , independent choices, giving $(j m) (r - j n)$ subsets by the product rule. Summing the disjoint classes over $j$ recovers all $r$ -subsets, so $(r m + n) = \sum_{j = 0}^{r} (j m) (r - j n)$ by the sum rule. Rubric: full credit for the disjoint classification by overlap with $A$ and the sum/product-rule assembly.

Exercise 6 (medium, symbolic).

Prove the connection $x^{n} = \sum_{k = 0}^{n} S (n, k) (x)_{k}$ holds as a polynomial identity, by interpreting both sides as counting functions when $x$ is a positive integer.

Hint

For a positive integer $x = k$ , count functions $f : N \to X$ with $∣ X ∣ = x$ by the size of the image. A function with image of size $j$ is a surjection onto a $j$ -subset.

Answer

Fix a positive integer value $x$ and let $X$ have $∣ X ∣ = x$ . The number of functions $N \to X$ with $∣ N ∣ = n$ is $x^{n}$ . Classify each function by its image size $j$ : choose the $j$ -element image in $(j x) = (x)_{j} / j!$ ways, then choose a surjection of $N$ onto that image in $Surj (n, j) = j! S (n, j)$ ways. The product is $(j x) j! S (n, j) = (x)_{j} S (n, j)$ . Summing the disjoint image-size classes gives $x^{n} = \sum_{j = 0}^{n} S (n, j) (x)_{j}$ . This equality of polynomial functions holds at every positive integer $x$ , hence as an identity of polynomials in $x$ (two polynomials agreeing at infinitely many points coincide). Rubric: full credit for the image-size decomposition, the surjection factor, and the infinitely-many-points argument promoting it to a polynomial identity.

Exercise 7 (hard, symbolic).

Prove that the number of permutations of an $n$ -set with exactly $k$ cycles, $c (n, k)$ , satisfies $c (n, k) = (n - 1) c (n - 1, k) + c (n - 1, k - 1)$ , and deduce $\sum_{k} c (n, k) = n!$ .

Hint

Insert the element $n$ into a permutation of ${1, \dots, n - 1}$ : either as a new fixed point (a new cycle) or into an existing cycle, immediately after one of the $n - 1$ other elements.

Answer

Build a permutation of ${1, \dots, n}$ from one of ${1, \dots, n - 1}$ by placing the element $n$ . There are two disjoint options. First, $n$ forms its own $1$ -cycle: this adds one cycle, so it turns a permutation with $k - 1$ cycles into one with $k$ cycles, contributing $c (n - 1, k - 1)$ . Second, $n$ is inserted into an existing cycle by placing it immediately after some element $i \in {1, \dots, n - 1}$ in the cycle notation; there are $n - 1$ choices of $i$ , and this does not change the cycle count, contributing $(n - 1) c (n - 1, k)$ . Every permutation of ${1, \dots, n}$ arises exactly once this way (delete $n$ to recover the smaller permutation and the insertion point), so $c (n, k) = (n - 1) c (n - 1, k) + c (n - 1, k - 1)$ . Summing over $k$ , let $T (n) = \sum_{k} c (n, k)$ ; the recurrence gives $T (n) = (n - 1) T (n - 1) + T (n - 1) = n T (n - 1)$ , and $T (1) = 1$ , so $T (n) = n!$ . This also says permutations are partitioned by cycle number, recovering $\sum_{k} c (n, k) = n!$ . Rubric: full credit for the insertion bijection with $n - 1$ positions, the disjoint new-fixed-point case, and the telescoping to $n!$ .

Exercise 8 (hard, symbolic).

Prove the orthogonality of the Stirling matrices: $\sum_{k} s (n, k) S (k, m) = δ_{nm}$ , where $s (n, k) = (- 1)^{n - k} c (n, k)$ and $δ_{nm}$ is $1$ if $n = m$ and $0$ otherwise.

Hint

The two Stirling families are the matrices of the change of basis between ${x^{n}}$ and ${(x)_{n}}$ in the polynomial ring. Composing the two changes of basis is the identity.

Answer

By definition the falling-to-power change of basis is $(x)_{n} = \sum_{k} s (n, k) x^{k}$ , and the power-to-falling change is $x^{k} = \sum_{m} S (k, m) (x)_{m}$ . Substituting the second into the first, $$ (x)_n = \sum_k s(n,k),x^k = \sum_k s(n,k)\sum_m S(k,m),(x)_m = \sum_m \Big(\sum_k s(n,k)S(k,m)\Big)(x)m . $$ The falling factorials ${(x)_{m}}_{m \geq 0}$ are linearly independent in the polynomial ring (they have distinct degrees), so comparing coefficients of $(x)_{m}$ on both sides forces $\sum_{k} s (n, k) S (k, m) = δ_{nm}$ . Equivalently, the lower-triangular matrices $[s (n, k)]$ and $[S (k, m)]$ are mutual inverses. Rubric: full credit for identifying both Stirling families as change-of-basis matrices, substituting one expansion into the other, and using linear independence of the falling-factorial basis to extract $\delta{nm}$.

Advanced results Master

The elementary table is the degree-zero stratum of enumerative combinatorics; its cells acquire structure once read through symmetry, generating functions, and $q$ -analogues.

Theorem 1 (twelvefold way as orbit counts). Each cell of the table is the cardinality of the quotient of the function space $X^{N}$ by a subgroup $H \leq Sym (N) \times Sym (X)$ , restricted to the arbitrary, injective, or surjective locus. With $H = 1$ the count is $k^{n}$ , $(k)_{n}$ , $k! S (n, k)$ down the first column; with $H = Sym (N)$ it is $(n k + n - 1)$ , $(n k)$ , $(k - 1 n - 1)$ ; with $H = Sym (X)$ it is $\sum_{j \leq k} S (n, j)$ , $[n \leq k]$ , $S (n, k)$ ; with $H = Sym (N) \times Sym (X)$ it is $p_{\leq k} (n)$ , $[n \leq k]$ , $p_{= k} (n)$ ^{[Stanley §1.9]}. The cells in a row are related by Burnside's orbit-counting lemma, which expresses each orbit count as the average number of fixed functions over the acting group.

Theorem 2 (exponential generating functions). The Stirling numbers of the second kind have the bivariate exponential generating function $$ \sum_{n \ge 0}\sum_{k \ge 0} S(n,k),y^k \frac{x^n}{n!} = e^{y(e^x - 1)}, \qquad \sum_{n \ge k} S(n,k)\frac{x^n}{n!} = \frac{(e^x - 1)^k}{k!}, $$ the second being a direct consequence of the surjection formula and the product rule for exponential generating functions: a set partition into $k$ blocks is an unordered collection of $k$ nonempty sets, and the exponential formula turns "a set of structures" into an exponential of the structure's generating function. The unsigned Stirling numbers of the first kind satisfy $\sum_{n \geq k} c (n, k) \frac{x ^{n}}{n !} = \frac{1}{k !} (lo g \frac{1}{1 - x})^{k}$ , the logarithm encoding cycles as the connected pieces of a permutation ^{[Comtet 1974]}.

Theorem 3 (Bell numbers and Dobinski). The total number of set partitions of an $n$ -set is the Bell number $B_{n} = \sum_{k = 0}^{n} S (n, k)$ , with exponential generating function $\sum_{n} B_{n} x^{n} / n! = e^{e^{x} - 1}$ , the recurrence $B_{n + 1} = \sum_{j = 0}^{n} (j n) B_{j}$ , and Dobinski's formula $B_{n} = e^{- 1} \sum_{m \geq 0} m^{n} / m!$ , a series expressing an integer as an infinite sum weighted by a Poisson distribution.

Theorem 4 ( $q$ -analogues and the Gaussian binomial). The subset count $(k n)$ has the $q$ -analogue $(k n)_{q} = \frac{( q ^{n} - 1 ) \dots ( q ^{n - k + 1} - 1 )}{( q ^{k} - 1 ) \dots ( q - 1 )}$ , the Gaussian binomial coefficient, which counts $k$ -dimensional subspaces of an $n$ -dimensional vector space over the field $F_{q}$ and, combinatorially, lattice paths weighted by area. As $q \to 1$ it degenerates to $(k n)$ . The falling factorial has the $q$ -analogue $(q; q)$ -Pochhammer, and the whole twelvefold table admits a $q$ -deformation whose $q \to 1$ limit is the classical table; the integer-partition cells $q$ -deform to the Gaussian-binomial generating function $(k n + k)_{q}$ for partitions in a box.

Theorem 5 (twelvefold way and species). In Joyal's theory of combinatorial species, the rows of the table are the structures and the columns are the operations of taking the species (labelled), its quotient by relabelling (unlabelled), and the corresponding exponential and ordinary generating functions. The surjection-equals- $k! S (n, k)$ identity is the species isomorphism $Surj_{k} ≅ Sym_{k} \circ Set_{\geq 1}$ at the level of exponential generating functions, and the exponential formula $E \circ F$ for "sets of $F$ -structures" is the structural source of the $e^{e^{x} - 1}$ generating function for set partitions ^{[Stanley §1.9]}.

Synthesis. The twelvefold way is the foundational reason elementary enumeration is a single subject: every classical count — powers, falling factorials, binomial and multiset coefficients, both kinds of Stirling numbers, and the partition counts — is the cardinality of one quotient of the function space $X^{N}$ , and reading the four columns is reading off the orbits of $Sym (N)$ , $Sym (X)$ , both, or neither. The central insight is that the surjective–labelled cell $k! S (n, k)$ is the hinge: it is exactly the bijective decomposition that makes $x^{n} = \sum_{k} S (n, k) (x)_{k}$ a counting statement, and its inclusion-exclusion form is dual to the Mobius function on the Boolean lattice, which generalises to Mobius inversion on any poset in 40.02.01. Putting these together, the exponential generating functions $e^{e^{x} - 1}$ and $(lo g \frac{1}{1 - x})^{k} / k!$ are not separate facts but the species-level images of the row structures under the labelled-to-generating-function operation, so the table is the base case of analytic combinatorics; this is exactly the bridge that builds toward the symbolic method, where each cell becomes a construction (sequence, set, cycle) on generating functions, and the $q$ -analogue layer shows the same combinatorics governing subspace counts over finite fields. The elementary table and the deep theory are one object viewed at different resolutions.

Full proof set Master

Proposition 1 (function and injection counts). The number of functions $N \to X$ with $∣ N ∣ = n$ , $∣ X ∣ = k$ is $k^{n}$ , and the number of injections is the falling factorial $(k)_{n} = k (k - 1) \dots (k - n + 1)$ .

Proof. Order the elements of $N$ as $a_{1}, \dots, a_{n}$ . A function assigns to each $a_{i}$ an independent value in $X$ , so by the product rule the count is $k \cdot k \dots k = k^{n}$ . For an injection, $a_{1}$ may map to any of $k$ values, $a_{2}$ to any of the remaining $k - 1$ (distinct from $f (a_{1})$ ), and in general $a_{i}$ to any of $k - i + 1$ values not yet used; the choices are independent given the earlier ones, so the product rule gives $(k)_{n}$ . When $n > k$ the product reaches a zero factor, correctly recording that no injection exists. $□$

Proposition 2 (subset and multiset counts). The number of $n$ -subsets of a $k$ -set is $(n k)$ , and the number of $n$ -multisets from a $k$ -set is $(n k + n - 1)$ .

Proof. Ordered injective sequences of length $n$ from the $k$ -set number $(k)_{n}$ by Proposition 1; each $n$ -subset is the image of exactly $n!$ such sequences (its orderings), so the number of subsets is $(k)_{n} / n! = (n k)$ . For multisets, encode an $n$ -multiset from ${1, \dots, k}$ by its multiplicity vector $(a_{1}, \dots, a_{k})$ with $a_{i} \geq 0$ and $\sum a_{i} = n$ ; by the stars-and-bars bijection (Exercise 3) these number $(k - 1 n + k - 1) = (n n + k - 1)$ . $□$

Proposition 3 (Pascal's recurrence and the binomial theorem). For $0 < k < n$ , $(k n) = (k - 1 n - 1) + (k n - 1)$ , and $(x + y)^{n} = \sum_{k = 0}^{n} (k n) x^{k} y^{n - k}$ .

Proof. Fix an element $* \in N$ with $∣ N ∣ = n$ . The $k$ -subsets of $N$ split into those containing $*$ — equivalently $(k - 1)$ -subsets of $N ∖ {*}$ , numbering $(k - 1 n - 1)$ — and those omitting $*$ — equivalently $k$ -subsets of $N ∖ {*}$ , numbering $(k n - 1)$ . The two classes are disjoint and exhaustive, so the sum rule gives Pascal's recurrence. For the binomial theorem, expand $(x + y)^{n} = (x + y) (x + y) \dots (x + y)$ into $2^{n}$ monomials, one per choice of $x$ or $y$ from each factor; a monomial equals $x^{k} y^{n - k}$ exactly when $x$ is chosen from $k$ of the $n$ factors, and the number of such choices is $(k n)$ . Collecting like monomials gives the stated sum. $□$

Proposition 4 (the two indistinguishable-domain surjective cells). The number of surjections $N \to X$ counted up to relabelling the domain is $(k - 1 n - 1)$ ; counted up to relabelling both domain and codomain it is $p_{= k} (n)$ , the number of partitions of $n$ into exactly $k$ positive parts.

Proof. A surjection up to domain relabelling records only the fibre sizes over the labelled targets $x_{1}, \dots, x_{k}$ : a composition $(b_{1}, \dots, b_{k})$ with each $b_{i} \geq 1$ and $\sum b_{i} = n$ . Subtracting $1$ from each part gives a weak composition of $n - k$ into $k$ parts, counted by $(k - 1 ( n - k ) + k - 1) = (k - 1 n - 1)$ via stars and bars. If the codomain is also unlabelled, the order of the $b_{i}$ is forgotten and only the multiset of fibre sizes survives: a partition of $n$ into exactly $k$ positive parts, counted by $p_{= k} (n)$ . The injective and arbitrary cells in these columns are obtained the same way, giving $[n \leq k]$ and the multiset count $(n k + n - 1)$ , respectively, and $p_{\leq k} (n)$ for the arbitrary-both-unlabelled cell. $□$

Connections Master

The inclusion-exclusion form of the surjection count is the Boolean-lattice instance of Mobius inversion; the general theory on an arbitrary locally finite poset, with the Mobius function as the inverse of the zeta function in the incidence algebra, is developed in 40.02.01. The foundational reason the alternating sum $\sum_{j} (- 1)^{j} (j k) (k - j)^{n}$ counts surjections is that $(- 1)^{∣ T ∣}$ is the Mobius function of the subset lattice, so this unit is the elementary shadow of poset inversion.
The integer-partition cells $p_{\leq k} (n)$ and $p_{= k} (n)$ are the elementary, bijective face of a theory whose analytic depth — generating functions, the pentagonal number theorem, the Hardy-Ramanujan asymptotic — is owned by 21.16.01. This unit supplies the finite, hand-countable partition data; that unit supplies the modular and circle-method machinery. The boundary is deliberate: addition of parts here, the eta function there.
The exponential generating functions $e^{e^{x} - 1}$ for Bell numbers and $(e^{x} - 1)^{k} / k!$ for fixed-block-count set partitions are the first instances of the symbolic method that organises 40.08.01: the labelled constructions sequence, set, and cycle correspond to the operations $\frac{1}{1 - f}$ , $e^{f}$ , and $lo g \frac{1}{1 - f}$ on exponential generating functions, and the surjection-equals- $k! S (n, k)$ identity is the set-construction applied to nonempty blocks. The twelvefold way is the base case those generating-function constructions specialise from.

Historical & philosophical context Master

Systematic enumeration predates its name. The binomial coefficients appear in Pingala's Chandahsastra (c. 2nd century BCE) and in the medieval "Pascal" triangle of al-Karaji, Yang Hui, and Khayyam; the Stirling numbers were introduced by James Stirling in his 1730 Methodus Differentialis as the coefficients relating powers to falling factorials, the change-of-basis viewpoint that still defines them. The partition counts trace to Euler's 1748 generating-function method, whose analytic continuation this unit defers to 21.16.01.

The unifying frame is modern. Gian-Carlo Rota's 1964 paper On the foundations of combinatorial theory I ^{[Rota 1964]} reorganised enumeration around the incidence algebra of a poset and the Mobius function, making inclusion-exclusion a special case of a single inversion principle and giving combinatorics the structural standing of the rest of mathematics. Within that programme the twelvefold way is the elementary base case: the name was coined by Rota and popularised through Richard Stanley's Enumerative Combinatorics ^{[Stanley §1.9]}, where the $3 \times 4$ table first appears in textbook form, with the phrasing attributed to Joel Spencer. Joyal's 1981 theory of species later recast the rows as functors and the columns as the passage from labelled structures to generating functions, situating the table inside category theory and analytic combinatorics.

Bibliography Master

@book{stanley2012ec1,
  author    = {Stanley, Richard P.},
  title     = {Enumerative Combinatorics, Volume 1},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {49},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2012}
}

@article{rota1964mobius,
  author  = {Rota, Gian-Carlo},
  title   = {On the foundations of combinatorial theory I: Theory of M\"{o}bius functions},
  journal = {Zeitschrift f\"{u}r Wahrscheinlichkeitstheorie und verwandte Gebiete},
  volume  = {2},
  year    = {1964},
  pages   = {340--368}
}

@book{stirling1730methodus,
  author    = {Stirling, James},
  title     = {Methodus Differentialis: sive Tractatus de Summatione et Interpolatione Serierum Infinitarum},
  publisher = {Gul. Bowyer},
  address   = {London},
  year      = {1730}
}

@book{comtet1974advanced,
  author    = {Comtet, Louis},
  title     = {Advanced Combinatorics: The Art of Finite and Infinite Expansions},
  publisher = {D. Reidel},
  year      = {1974}
}

@article{joyal1981species,
  author  = {Joyal, Andr\'{e}},
  title   = {Une th\'{e}orie combinatoire des s\'{e}ries formelles},
  journal = {Advances in Mathematics},
  volume  = {42},
  number  = {1},
  year    = {1981},
  pages   = {1--82}
}

@book{vanlintwilson2001,
  author    = {van Lint, J. H. and Wilson, R. M.},
  title     = {A Course in Combinatorics},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2001}
}

@book{andrews1976partitions,
  author    = {Andrews, George E.},
  title     = {The Theory of Partitions},
  series    = {Encyclopedia of Mathematics and its Applications},
  volume    = {2},
  publisher = {Addison-Wesley},
  year      = {1976}
}

Prerequisites

none — this is a leaf unit

Tier anchors

beginner: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e (Cambridge) §1.1-1.2 (the sum and product rules, counting by bijection); Brualdi 2010 *Introductory Combinatorics* 5e (Pearson) Ch. 2-3 for the elementary table read by hand
intermediate: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §1.9 (the twelvefold way, set partitions and Stirling numbers, the falling factorial); van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 13-14
master: Stanley 2012 *Enumerative Combinatorics, Volume 1* 2e §1.2-1.9 and Notes (Rota's twelvefold way, the q-analogues, the exponential formula prelude); Rota 1964 *Amer. Math. Monthly* 71 (the Mobius-function programme that frames enumeration); Andrews 1976 *The Theory of Partitions* Ch. 1 for the integer-partition column

References

Stanley, R. P. — Enumerative Combinatorics, Volume 1 · Cambridge Studies in Advanced Mathematics 49, 2nd edition (2012). §1.2 develops the falling factorial $(x)_n$ and ordinary power $x^n$; §1.4 the binomial and multiset coefficients $\binom{n}{k}$ and $\left(\!\binom{n}{k}\!\right)$ with the stars-and-bars argument; §1.9 'The Twelvefold Way' assembles the $3 \times 4$ table of functions $f : N \to X$ under the (arbitrary / injective / surjective) regimes crossed with (distinguishable / indistinguishable) on each side, filling the cells with ordinary powers, falling factorials, binomial coefficients, multiset coefficients, Stirling numbers $S(n,k)$ and $c(n,k)$, and the partition counts $p_k(n)$; the Stirling recurrences and Pascal's recurrence are derived there.
Stanley, R. P. & Rota, G.-C. — The Twelvefold Way (attribution and notes) · Stanley, *Enumerative Combinatorics* Vol. 1, §1.9 Notes, attributes the name 'twelvefold way' to Gian-Carlo Rota (with the phrasing suggested by Joel Spencer); the organising idea descends from Rota's 1964 foundations-of-enumeration programme.
Rota, G.-C. — On the foundations of combinatorial theory I: Theory of Mobius functions · *Zeitschrift fur Wahrscheinlichkeitstheorie und verwandte Gebiete* 2 (1964), 340-368. The paper that reframed enumeration around the incidence algebra and the Mobius function, providing the structural viewpoint from which the twelvefold way is the elementary base case.
Andrews, G. E. — The Theory of Partitions · Encyclopedia of Mathematics and its Applications, Vol. 2 (1976; Cambridge 1998). Chapter 1 develops $p(n)$ and $p_k(n)$, the partitions of $n$ into at most $k$ parts, which fill the two indistinguishable-on-both-sides columns of the twelvefold way.
Comtet, L. — Advanced Combinatorics · Reidel (1974). Standard reference for Stirling numbers of both kinds, their generating functions, recurrences, and the orthogonality $\sum_k s(n,k) S(k,m) = \delta_{nm}$ relating the two change-of-basis matrices between $x^n$ and $(x)_n$.

Estimated time

beginner: 18m
intermediate: 45m
master: 85m