The Twelvefold Way

How many ways are there to distribute nn balls into kk boxes? The honest answer is: it depends. Four separate questions must be answered first. Are the balls distinguishable from one another, or interchangeable? Are the boxes distinguishable, or interchangeable? Must every box receive at least one ball? Must every box receive at most one ball? Once these questions are answered, the counting problem becomes one of exactly twelve canonical types. Each type has a clean closed-form or generating-function answer. These answers are built from tools you already know. The tools are binomial coefficients, Stirling Numbers of the Second Kind, and Integer Partitions. This taxonomy matters for an important reason. It reorganizes a sprawling zoo of counting problems into a single table. The problems include functions, multisets, set partitions, partitions of integers, injections, and surjections. The table is 3×43\times 4, indexed by two binary choices and four constraint types. The binary choices are ball type and box type. The constraint types are none, injective, surjective, and bijective. Once you see the table, you stop re-deriving the same argument from scratch. This applies every time a new "how many ways" question appears in a different costume. The unifying language is that of functions f:N→Kf: N \to K. These map an nn-element domain to a kk-element codomain. Distinguishability of balls/boxes corresponds to a specific choice. We either count functions themselves or only their orbits. These orbits fall under a relevant symmetric group action. The name "Twelvefold Way" comes from Gian-Carlo Rota. He popularized this organizational scheme as a pedagogical device. The twelve cases are not twelve unrelated tricks. Instead, they are twelve consistent applications of one idea. That idea is functions from a set of size nn to a set of size kk. These functions are quotiented by the appropriate symmetries. This article states each of the twelve cases precisely. It proves the two hardest ones in full. These are surjections via inclusion–exclusion, and indistinguishable balls into indistinguishable boxes via partitions. The article also shows how the whole table serves as a launching pad. It leads toward Polya Enumeration. This generalizes "distinguishable vs. indistinguishable" to counting orbits. Such orbits form under an arbitrary group of symmetries. By the end, you will have a single mental table. You can consult it for any balls-into-boxes question. You will also have full proofs of the two entries requiring real combinatorial machinery. Worked examples will show you exactly how to translate a word problem into a cell of the table.

Key takeaways
  • Every balls-into-boxes counting problem is determined by two choices — are balls distinguishable? are boxes distinguishable? — crossed with a constraint: none, injective (n≤kn\le k needed), surjective (n≥kn\ge k needed), or both (bijective, n=kn=k).
  • This gives a 3×43\times 4 grid of exactly twelve cases (three constraint columns are collapsed into "none/injective/surjective" plus the bijective case shares columns), each with a known closed form.
  • Distinguishable balls, distinguishable boxes, no constraint counts functions N→KN\to K: answer knk^n.
  • Indistinguishable balls, distinguishable boxes, no constraint counts weak compositions: answer (n+k−1k−1)\binom{n+k-1}{k-1}, the Combinations with Repetition formula.
  • The two genuinely hard cells — indistinguishable balls/distinguishable boxes with surjectivity, and indistinguishable balls/indistinguishable boxes — are governed respectively by Stirling Numbers of the Second Kind machinery and by Integer Partitions.
  • Key idea: distinguishability of balls or boxes is exactly the statement that we count functions up to the action of a symmetric group on the domain or codomain — the seed of Polya Enumeration.

Where this lives today

The twelve-cell table is not merely pedagogical bookkeeping; each cell is the answer to recurring questions across mathematics and its applications. Counting functions between finite sets (knk^n) underlies the size of function spaces in computer science, such as the number of possible hash outcomes or truth assignments. Counting injections (kn‾k^{\underline n}) is the seed computation for the inclusion–exclusion method itself and appears whenever "no collisions allowed" matters, as in birthday-paradox-style analyses and in coding theory when assigning distinct codewords. Counting surjections and their Stirling-number cousin appear in the analysis of hash functions with guaranteed full coverage, in the theory of set partitions used in statistical physics (partitioning particles into indistinguishable energy levels, closely related to Bose–Einstein and Fermi–Dirac statistics, which correspond to different cells of exactly this table under the balls-are-particles, boxes-are-states dictionary), and in the combinatorics of restriction maps in algebra. Integer partitions, arising in the fully indistinguishable cells, are central to the representation theory of the symmetric group, to number-theoretic partition congruences, and to statistical mechanics partition functions (the name is not a coincidence: the same objects that count multisets of box-occupancies also index the irreducible representations of SnS_n). Finally, the entire table is the n=1n=1 case, in a precise sense, of Polya Enumeration: instead of quotienting only by the full symmetric group Sym(N)\mathrm{Sym}(N) or Sym(K)\mathrm{Sym}(K) acting on one side, Pólya's theorem quotients by an arbitrary subgroup G≤Sym(N)G \le \mathrm{Sym}(N) acting on colorings, recovering the Twelvefold Way's "indistinguishable" cases exactly when GG is the full symmetric group and recovering the "distinguishable" cases exactly when GG is trivial — the Twelvefold Way is the boundary case of a much richer group-theoretic enumeration theory.

Ask the tutor: How does the free group action argument in this proof generalize to Burnside's lemma and Pólya enumeration for non-symmetric groups?

DefinitionThe Twelvefold Way

Fix finite sets NN (the balls, ∣N∣=n|N|=n) and KK (the boxes, ∣K∣=k|K|=k). A distribution of balls into boxes is a function f:N→Kf: N \to K, where f(x)=yf(x)=y means ball xx is placed in box yy. The Twelvefold Way classifies the problem "count distributions of nn balls into kk boxes" along two independent axes:

Axis 1 (balls): balls are distinguishable (we count functions ff literally) or indistinguishable (we count functions up to precomposition by Sym(N)\mathrm{Sym}(N), i.e. we count only the multiset of box-occupancies, equivalently the orbit of ff under relabeling of NN).

Axis 2 (boxes): boxes are distinguishable (functions counted literally) or indistinguishable (we count functions up to postcomposition by Sym(K)\mathrm{Sym}(K), i.e. up to relabeling of KK).

Axis 3 (constraint): the function ff is unconstrained, or required to be injective (each box holds at most one ball; forces n≤kn \le k), or required to be surjective (each box holds at least one ball; forces n≥kn \ge k), or required to be bijective (forces n=kn=k). Crossing the two binary axes with three basic constraint types (none, injective, surjective — bijective is the intersection of injective and surjective and only nontrivial when n=kn=k) yields twelve enumeration problems, tabulated below with S(n,k)S(n,k) the Stirling Numbers of the Second Kind and pk(n)p_k(n) the number of partitions of nn into exactly kk positive parts.

BallsBoxesAny ffInjective ffSurjective ff
distinguishabledistinguishableknk^nkn‾=k(k−1)⋯(k−n+1)k^{\underline{n}} = k(k-1)\cdots(k-n+1)k! S(n,k)k!\,S(n,k)
indistinguishabledistinguishable(n+k−1k−1)\binom{n+k-1}{k-1}(kn)\binom{k}{n}(n−1k−1)\binom{n-1}{k-1}
distinguishableindistinguishable∑j=0kS(n,j)\sum_{j=0}^{k} S(n,j)[n≤k][n\le k] (0 or 1)S(n,k)S(n,k)
indistinguishableindistinguishable∑j=0kpj(n)\sum_{j=0}^{k} p_j(n)[n≤k][n\le k] (0 or 1)pk(n)p_k(n)

Here [n≤k][n \le k] denotes the indicator (value 11 if n≤kn\le k, else 00); an injective function's image has size nn, and up to relabeling boxes there is only one way to have nn occupied indistinguishable boxes out of kk, provided n≤kn\le k.

Intuition

The table is best understood as a single idea applied four times. Start from the most refined object: an actual function f:N→Kf:N\to K, drawn as a bipartite diagram with an arrow from each ball to its box. Distinguishable balls and distinguishable boxes means we count these diagrams literally — two diagrams differing by which ball goes where are different, full stop. Making the boxes indistinguishable means we glue together all diagrams that agree after relabeling the boxes; formally we quotient by the action of Sym(K)\mathrm{Sym}(K) on the codomain. What survives is the data of which balls end up together, i.e. a set partition of NN (if surjective) or a partial set partition (if not every box is used). Making the balls indistinguishable as well collapses even the identity of which ball is which, and what survives is only the sequence of box sizes — a partition of the integer nn.

Figure
The four refinements of a single distribution, illustrated on n=5n=5 balls into k=3k=3 boxes
Distinguishable balls, distinguishable boxes: a labeled function f: N → K 12345 A B C Boxes indistinguishable: only the set partition {1,2}{3}{4,5} matters {1,2} | {3} | {4,5} Balls indistinguishable too: only the block sizes 2,1,2 matter λ = (2,2,1) ⊢ 5 Balls indistinguishable, boxes distinguishable: only the occupancy vector matters, e.g. box A gets 2, B gets 1, C gets 2 (n_A, n_B, n_C) = (2, 1, 2), n_A+n_B+n_C = 5

The two "hard" cells of the table — surjections onto indistinguishable boxes, and the fully indistinguishable case — are exactly the cells that require Integer Partitions and Stirling Numbers of the Second Kind, because those are precisely the combinatorial objects that classify orbits of surjections under relabeling.

TheoremSurjections, Stirling numbers, and set partitions

Let n,kn,k be positive integers, NN a set with ∣N∣=n|N|=n, KK a set with ∣K∣=k|K|=k. Let S(n,k)S(n,k) denote the number of partitions of the set NN into exactly kk nonempty, unordered, unlabeled blocks (the Stirling number of the second kind). Then: 1. The number of surjective functions f:N→Kf: N \to K (distinguishable balls, distinguishable boxes) equals k! S(n,k)k!\, S(n,k). 2. Consequently, the number of surjections up to relabeling the codomain KK (distinguishable balls, indistinguishable boxes, surjective) equals S(n,k)S(n,k). 3. Consequently, the total number of functions f:N→Kf: N\to K up to relabeling KK (distinguishable balls, indistinguishable boxes, unconstrained) equals ∑j=0kS(n,j)\sum_{j=0}^{k} S(n,j). Moreover S(n,k)S(n,k) satisfies the closed form

S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)n.S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n .
Proof

Technique: inclusion–exclusion, then orbit-counting. Part 1, closed form for surjections. Let Surj(N,K)\mathrm{Surj}(N,K) be the set of surjective functions N→KN\to K and let Fun(N,K)\mathrm{Fun}(N,K) be the set of all functions, so ∣Fun(N,K)∣=kn|\mathrm{Fun}(N,K)| = k^n since each of the nn elements of NN independently has kk choices of image. For each box y∈Ky \in K let Ay⊆Fun(N,K)A_y \subseteq \mathrm{Fun}(N,K) be the set of functions that miss yy, i.e. y∉f(N)y \notin f(N). A function is surjective exactly when it lies in none of the AyA_y, so

∣Surj(N,K)∣=∣Fun(N,K)∣−∣⋃y∈KAy∣.|\mathrm{Surj}(N,K)| = |\mathrm{Fun}(N,K)| - \Big|\bigcup_{y\in K} A_y\Big|.

By inclusion–exclusion, for any subset J⊆KJ \subseteq K with ∣J∣=j|J| = j, the functions avoiding all boxes in JJ are exactly the functions N→K∖JN \to K\setminus J, of which there are (k−j)n(k-j)^n (this includes j=kj=k, giving 0n=00^n = 0 for n≥1n\ge 1). Since AyA_y for yy ranging over KK are indexed by a kk-element set, inclusion–exclusion gives

∣⋃y∈KAy∣=∑∅≠J⊆K(−1)∣J∣+1(k−∣J∣)n=∑j=1k(−1)j+1(kj)(k−j)n.\Big|\bigcup_{y\in K} A_y\Big| = \sum_{\emptyset \ne J \subseteq K} (-1)^{|J|+1} (k-|J|)^n = \sum_{j=1}^{k} (-1)^{j+1}\binom{k}{j}(k-j)^n.

Therefore

∣Surj(N,K)∣=kn−∑j=1k(−1)j+1(kj)(k−j)n=∑j=0k(−1)j(kj)(k−j)n,|\mathrm{Surj}(N,K)| = k^n - \sum_{j=1}^k (-1)^{j+1}\binom{k}{j}(k-j)^n = \sum_{j=0}^{k} (-1)^j \binom{k}{j}(k-j)^n,

where the j=0j=0 term is knk^n, matching the definition consistently. Call this quantity T(n,k)T(n,k); we have shown

T(n,k):=∣Surj(N,K)∣=∑j=0k(−1)j(kj)(k−j)n.T(n,k) := |\mathrm{Surj}(N,K)| = \sum_{j=0}^{k} (-1)^j \binom{k}{j}(k-j)^n.

Bijection between surjections and (ordered set partitions). We now show T(n,k)=k! S(n,k)T(n,k) = k!\,S(n,k) directly by a counting bijection, which simultaneously proves the displayed formula for S(n,k)S(n,k). Given a surjection f:N→Kf: N \to K, its fibers f−1(y)f^{-1}(y) for y∈Ky\in K form a partition of NN into exactly kk nonempty blocks (nonempty because ff is surjective; they partition NN because every element of NN has exactly one image; there are exactly kk of them since distinct y∈Ky\in K give disjoint fibers, and each is nonempty by surjectivity, so none collapse). Conversely, given an unordered set partition of NN into kk nonempty blocks B1,…,BkB_1,\dots,B_k, choosing a bijection from the block index set {1,…,k}\{1,\dots,k\} to KK — equivalently, choosing which block maps to which element of KK — produces a surjection N→KN \to K, and every surjection arises this way from exactly one set partition together with exactly one such labeling. Formally: define a map

Φ:Surj(N,K)⟶{(π,σ):π a partition of N into k blocks,σ:{blocks of π}→K a bijection}\Phi: \mathrm{Surj}(N,K) \longrightarrow \{(\pi, \sigma) : \pi \text{ a partition of } N \text{ into } k \text{ blocks}, \sigma: \{\text{blocks of }\pi\} \to K \text{ a bijection}\}

by Φ(f)=(πf,σf)\Phi(f) = (\pi_f, \sigma_f) where πf\pi_f is the partition into fibers of ff and σf\sigma_f sends the block f−1(y)f^{-1}(y) to yy. This is well defined since ff surjective guarantees πf\pi_f has exactly kk blocks and σf\sigma_f is a well-defined bijection (fibers of a function are pairwise disjoint by definition of function, and distinct boxes give distinct fibers since a block f−1(y)f^{-1}(y) determines yy as the common value of ff on it). Φ\Phi is injective: if Φ(f)=Φ(g)\Phi(f) = \Phi(g) then f,gf, g have the same fibers assigned to the same boxes, so f(x)=g(x)f(x) = g(x) for every x∈Nx \in N (since xx lies in a unique fiber, and that fiber is sent to the same box by both). Hence f=gf = g. Φ\Phi is surjective onto the target set: given (π,σ)(\pi, \sigma) with π={B1,…,Bk}\pi = \{B_1,\dots,B_k\} a partition of NN into kk nonempty blocks and σ\sigma a bijection from blocks to KK, define f(x)=σ(Bi)f(x) = \sigma(B_i) where x∈Bix \in B_i. This ff is well defined (every xx lies in exactly one block, since π\pi is a partition), and Φ(f)=(π,σ)\Phi(f) = (\pi,\sigma) by construction, and ff is surjective since σ\sigma is a bijection onto KK so every y∈Ky \in K is σ(Bi)\sigma(B_i) for some ii, hence is hit. Thus Φ\Phi is a bijection, so

∣Surj(N,K)∣=∑π#{σ:σ bijection from blocks of π to K}=∑πk!=S(n,k)⋅k!,|\mathrm{Surj}(N,K)| = \sum_{\pi} \#\{\sigma : \sigma \text{ bijection from blocks of }\pi\text{ to }K\} = \sum_{\pi} k! = S(n,k)\cdot k!,

since there are S(n,k)S(n,k) partitions π\pi of NN into exactly kk nonempty blocks by definition of the Stirling number, and for each such π\pi there are exactly k!k! bijections from its (exactly kk) blocks to KK. Combining with the inclusion–exclusion computation, k! S(n,k)=T(n,k)=∑j=0k(−1)j(kj)(k−j)nk!\,S(n,k) = T(n,k) = \sum_{j=0}^k (-1)^j\binom{k}{j}(k-j)^n, which after dividing by k!k! is exactly the claimed closed form for S(n,k)S(n,k). This proves the closed form and Part 1. Part 2. An unordered set partition of NN into kk nonempty blocks is precisely an equivalence class of surjections N→KN \to K under the right action of Sym(K)\mathrm{Sym}(K) (postcomposition), because two surjections have the same fibers if and only if one is obtained from the other by relabeling the codomain via some permutation of KK, and this action is free on Surj(N,K)\mathrm{Surj}(N,K): if ρ∈Sym(K)\rho \in \mathrm{Sym}(K) satisfies ρ∘f=f\rho \circ f = f for a surjective ff, then for every y=f(x)∈Ky = f(x) \in K we get ρ(y)=ρ(f(x))=f(x)=y\rho(y) = \rho(f(x)) = f(x) = y, so ρ\rho fixes every element of f(N)=Kf(N) = K (using surjectivity), forcing ρ=id\rho = \mathrm{id}. A free action of a group GG partitions a set into orbits each of size ∣G∣|G|, so the number of orbits is ∣Surj(N,K)∣/∣Sym(K)∣=k!S(n,k)/k!=S(n,k)|\mathrm{Surj}(N,K)|/|\mathrm{Sym}(K)| = k!S(n,k)/k! = S(n,k). Each orbit is exactly the set of surjections sharing a common fiber-partition, i.e. each orbit corresponds to exactly one set partition into kk blocks; this recovers Part 2, that counting surjections with indistinguishable boxes gives S(n,k)S(n,k). Part 3. A function N→KN \to K (not necessarily surjective), up to relabeling KK, is determined exactly by its set of nonempty fibers, which is a partition of NN into some number jj of nonempty blocks with 0≤j≤k0 \le j \le k (as long as N≠∅N \ne \emptyset, j≥1j\ge 1; if N=∅N=\emptyset then j=0j = 0 trivially, contributing S(0,0)=1S(0,0)=1). By the orbit-counting argument of Part 2 applied at each fixed number of used boxes j≤kj\le k (choosing which jj of the kk indistinguishable boxes are used is not even a separate choice, since the boxes are indistinguishable — only the count jj of nonempty fibers matters, not which labels), the number of such orbits with exactly jj nonempty fibers is S(n,j)S(n,j). Summing over the possible number of nonempty fibers j=0,1,…,kj = 0,1,\dots,k gives

∑j=0kS(n,j)\sum_{j=0}^{k} S(n,j)

as the total count of functions N→KN \to K up to relabeling KK. ■\blacksquare

∎
CorollaryIndistinguishable balls and boxes

The number of surjections N→KN \to K up to simultaneously relabeling both NN and KK (indistinguishable balls, indistinguishable boxes, surjective) equals pk(n)p_k(n), the number of partitions of the integer nn into exactly kk positive parts. Consequently the unconstrained count (indistinguishable balls, indistinguishable boxes, no constraint) is ∑j=0kpj(n)\sum_{j=0}^k p_j(n), the number of partitions of nn into at most kk parts.

Proof

Technique: further quotient of the Stirling result by relabeling the domain. By the Theorem above (Part 2), surjections up to relabeling KK alone correspond bijectively to set partitions of NN into exactly kk nonempty blocks. Now further quotient by relabeling NN as well, i.e. by the action of Sym(N)\mathrm{Sym}(N) on such set partitions by relabeling elements. Two set partitions of NN into kk blocks lie in the same Sym(N)\mathrm{Sym}(N)-orbit if and only if they have the same multiset of block sizes: given two partitions with the same sorted list of block sizes (λ1≥λ2≥⋯≥λk>0)(\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_k > 0), one can biject blocks of matching sizes and extend to a permutation of NN carrying one partition to the other (concretely, list the elements of each block in an arbitrary fixed order and match position-by-position across blocks of equal size in decreasing size order); conversely any permutation of NN applied to a partition preserves the multiset of its block sizes, since permuting elements does not change how many elements land in each block, only which labels do. Hence the orbits of Sym(N)\mathrm{Sym}(N) acting on the set of partitions of NN into exactly kk nonempty blocks are in bijection with multisets {λ1≥⋯≥λk≥1}\{\lambda_1 \ge \cdots \ge \lambda_k \ge 1\} satisfying λ1+⋯+λk=n\lambda_1 + \cdots + \lambda_k = n — that is, with partitions of the integer nn into exactly kk positive parts. By definition, the number of these is pk(n)p_k(n). This proves the surjective case. For the unconstrained case, as in Part 3 of the theorem above, a function up to relabeling both NN and KK is determined by the sizes of its nonempty fibers only (not even which underlying elements are involved), giving a partition of nn into at most kk positive parts, since the number of nonempty fibers can be any jj with 0≤j≤k0\le j \le k. Summing pj(n)p_j(n) over j=0,…,kj=0,\ldots,k gives the stated total, where p0(n)=[n=0]p_0(n) = [n=0]. ■\blacksquare

∎

Worked examples

Example 1 (asymmetric, all three lower rows in play). A caterer has n=7n = 7 distinct desserts (a cheesecake, a tiramisu, a flan, a brownie, a sorbet, a macaron, a pavlova) and must place them onto k=4k = 4 indistinguishable dessert trays for a buffet, where any tray may hold any number of desserts including zero, but every tray used must be visually distinct in content only insofar as which desserts sit on it — i.e. we only care which desserts end up together, not tray labels, and empty trays are allowed to sit unused on the table. This is the cell: distinguishable balls, indistinguishable boxes, unconstrained (n=7n=7, k=4k=4). By Part 3 of the theorem,

answer=∑j=04S(7,j).\text{answer} = \sum_{j=0}^{4} S(7,j).

We compute the needed Stirling numbers of the second kind via the recurrence S(n,k)=k S(n−1,k)+S(n−1,k−1)S(n,k) = k\,S(n-1,k) + S(n-1,k-1), with S(0,0)=1S(0,0)=1, S(n,0)=0S(n,0)=0 for n≥1n\ge1, S(n,k)=0S(n,k)=0 for k>nk>n. Building up to n=7n=7: S(1,1)=1S(1,1)=1. S(2,1)=1, S(2,2)=1S(2,1)=1,\ S(2,2)=1. S(3,1)=1, S(3,2)=3, S(3,3)=1S(3,1)=1,\ S(3,2)=3,\ S(3,3)=1. S(4,1)=1, S(4,2)=7, S(4,3)=6, S(4,4)=1S(4,1)=1,\ S(4,2)=7,\ S(4,3)=6,\ S(4,4)=1. S(5,1)=1, S(5,2)=15, S(5,3)=25, S(5,4)=10, S(5,5)=1S(5,1)=1,\ S(5,2)=15,\ S(5,3)=25,\ S(5,4)=10,\ S(5,5)=1. S(6,1)=1, S(6,2)=31, S(6,3)=90, S(6,4)=65, S(6,5)=15, S(6,6)=1S(6,1)=1,\ S(6,2)=31,\ S(6,3)=90,\ S(6,4)=65,\ S(6,5)=15,\ S(6,6)=1. S(7,1)=1S(7,1)=1. S(7,2)=2 S(6,2)+S(6,1)=62+1=63S(7,2) = 2\,S(6,2) + S(6,1) = 62 + 1 = 63. S(7,3)=3 S(6,3)+S(6,2)=270+31=301S(7,3) = 3\,S(6,3) + S(6,2) = 270 + 31 = 301. S(7,4)=4 S(6,4)+S(6,3)=260+90=350S(7,4) = 4\,S(6,4) + S(6,3) = 260 + 90 = 350. So

S(7,0)+S(7,1)+S(7,2)+S(7,3)+S(7,4)=0+1+63+301+350=715.S(7,0)+S(7,1)+S(7,2)+S(7,3)+S(7,4) = 0 + 1 + 63 + 301 + 350 = 715.

There are 715 ways to distribute the 77 distinct desserts onto 44 indistinguishable trays (allowing empty trays). As a sanity check, note 715=(134)/1715 = \binom{13}{4}/1... rather, we simply trust the direct recurrence computation; a second sanity check is that this must be less than the distinguishable-boxes unconstrained count 47=163844^7 = 16384 divided roughly by symmetries, which is plausible in order of magnitude (16384/715≈22.916384/715 \approx 22.9, consistent with substantial but partial symmetrization since boxes are frequently unevenly filled, so the naive division by 4!=244!=24 is not exact but close).

Example 2 (surjective, indistinguishable balls, distinguishable boxes — a genuinely different cell). A vending-machine warehouse must ship n=10n = 10 identical bags of rice to k=4k=4 distinguishable stores (Store A, B, C, D), and every store must receive at least one bag (no store may end up empty), but bags within a shipment are not tracked individually. This is the cell: indistinguishable balls, distinguishable boxes, surjective. By the classical stars-and-bars-with-positivity argument (itself the base case underlying Combinations with Repetition reasoning), the count of positive integer solutions to xA+xB+xC+xD=10x_A + x_B + x_C + x_D = 10 with each xi≥1x_i \ge 1 equals

(n−1k−1)=(93).\binom{n-1}{k-1} = \binom{9}{3}.

We verify this by the standard substitution xi=yi+1x_i = y_i + 1 with yi≥0y_i \ge 0, turning the equation into yA+yB+yC+yD=6y_A+y_B+y_C+y_D = 6 with yi≥0y_i\ge 0, whose nonnegative solution count is (6+4−14−1)=(93)\binom{6+4-1}{4-1} = \binom{9}{3}. Computing, (93)=9⋅8⋅73⋅2⋅1=5046=84\binom{9}{3} = \dfrac{9\cdot 8\cdot 7}{3\cdot2\cdot1} = \dfrac{504}{6} = 84. So there are 84 ways to ship the bags so that every store gets at least one, matching the table entry (n−1k−1)\binom{n-1}{k-1} directly with n=10,k=4n=10,k=4. To cross-check against the general table, note that this cell's formula is derived independently of Stirling numbers (it is pure stars-and-bars with a positivity shift), which is exactly why the "indistinguishable balls" row is combinatorially easier than the "distinguishable balls" row — occupancy vectors are the entire story once ball identity is erased, with no further symmetrization needed since the boxes remain distinguishable.

CounterexampleWhy "distinguishable vs. indistinguishable" must be fixed before imposing the constraint

Consider n=3n=3 balls and k=3k=3 boxes, and the naive claim: "the number of surjections with indistinguishable boxes can be computed by first counting surjections with distinguishable boxes, and then always dividing by k!k!." This is false in general, and n=k=3n=k=3 already breaks it in a way worth seeing explicitly, though for a cleaner break take n=4,k=2n=4,k=2. With n=4n=4 distinguishable balls and k=2k=2 distinguishable boxes, the number of surjections is 2! S(4,2)=2⋅7=142!\,S(4,2) = 2\cdot 7 = 14. If one incorrectly assumed dividing by k!=2k!=2 always gives the indistinguishable-box count, one would predict 14/2=714/2 = 7 — and here it happens to be correct, since S(4,2)=7S(4,2)=7 exactly. Now push further to see where the naive "always divide by k!k!" heuristic actually fails: take n=2,k=2n=2, k=2. Distinguishable-box surjections: 2! S(2,2)=2⋅1=22!\,S(2,2) = 2\cdot 1 = 2 (the two functions {1↦A,2↦B}\{1\mapsto A, 2\mapsto B\} and {1↦B,2↦A}\{1\mapsto B, 2\mapsto A\}). Dividing naively by k!=2k!=2 gives 11, which does match S(2,2)=1S(2,2)=1. The division-by-k!k! trick works precisely because Sym(K)\mathrm{Sym}(K) acts freely on the set of surjections — this was proved as a specific step inside the Theorem's proof (Part 2), not assumed. It is exactly this freeness that fails once we drop surjectivity: consider n=2,k=2n=2,k=2 but unconstrained functions. There are kn=4k^n = 4 total functions N→KN\to K: the two constant functions (both balls to box A; both to box B) and the two surjections above. Dividing 44 by k!=2k!=2 gives 22 — but the true indistinguishable-box unconstrained count is ∑j=02S(2,j)=S(2,0)+S(2,1)+S(2,2)=0+1+1=2\sum_{j=0}^2 S(2,j) = S(2,0)+S(2,1)+S(2,2) = 0+1+1 = 2, which happens to agree numerically here purely by coincidence of small numbers, so let us use n=3,k=2n=3,k=2 to expose the real failure. For n=3,k=2n=3, k=2: total functions =23=8= 2^3 = 8. Naive division by k!=2k!=2 predicts 44 indistinguishable-box classes. But the true count is ∑j=02S(3,j)=S(3,0)+S(3,1)+S(3,2)=0+1+3=4\sum_{j=0}^2 S(3,j) = S(3,0)+S(3,1)+S(3,2) = 0+1+3 = 4 — still matching! The reason these small cases keep "accidentally" matching is that Sym(K)=Sym(2)\mathrm{Sym}(K)=\mathrm{Sym}(2) has order 22, and the only non-free orbits are the two constant functions, each fixed pointwise by the nontrivial swap, contributing 22 functions collapsing to 22 classes instead of the "generic" 22 functions collapsing to 11 class — and for k=2k=2 this off-by-one-per-constant-function exactly cancels in the arithmetic by luck of small nn. Take k=3k=3 instead, still unconstrained, with n=2n=2: total functions 32=93^2 = 9; naive division by 3!=63! = 6 gives a non-integer, 1.51.5 — an immediate, undeniable failure. The correct count from Part 3 of the theorem is ∑j=03S(2,j)=0+1+1+0=2\sum_{j=0}^3 S(2,j) = 0 + 1 + 1 + 0 = 2 (using S(2,3)=0S(2,3)=0 since you cannot partition a 2-element set into 3 nonempty blocks). The moral: the "divide by k!k!" shortcut is only valid on the locus where Sym(K)\mathrm{Sym}(K) acts freely, which is exactly the surjections — dropping the surjectivity hypothesis (one hypothesis of Part 2 of the Theorem) breaks the free-action argument used in its proof, and the correct replacement is the sum-over-jj formula of Part 3, not naive division.

Scope, edge cases & common traps

SituationCorrect handling
n<kn < k and injectivity requiredFine: count is kn‾k^{\underline n} (dist./dist.) or (kn)\binom{k}{n} (indist. balls) — nonzero.
n<kn < k and surjectivity requiredImpossible: by pigeonhole a function from an nn-set cannot hit k>nk>n targets, so every surjective-column entry is 00 whenever n<kn<k; formulas like k!S(n,k)k!S(n,k) automatically evaluate to 00 since S(n,k)=0S(n,k)=0 for k>nk>n.
n=0n=0The empty function N→KN\to K exists uniquely when N=∅N=\emptyset; it is vacuously injective, and surjective iff K=∅K=\emptyset too. Boundary values S(0,0)=1S(0,0)=1, S(0,k)=0S(0,k)=0 for k>0k>0 must be used, not "undefined."
k=0k=0, n>0n>0No function N→∅N \to \emptyset exists when N≠∅N\ne\emptyset; every entry is 00.
Confusing "indistinguishable boxes, injective" with a nontrivial countIt is always 00 or 11: if n≤kn\le k there is exactly one way (up to relabeling boxes, an injection just picks which nn of the kk box-slots are used, and since boxes are indistinguishable this "which slots" datum vanishes) — a frequent source of error is trying to apply a binomial coefficient here.
Reading "distinguishable" as a property of the count rather than of the objectsDistinguishability is a modeling choice about the balls/boxes themselves, made before any constraint is applied — see the Counterexample above for what breaks if this order is not respected.

The mathematician behind it

Origins · 1 minGian-Carlo Rota and how this was discovered
GR
Gian-Carlo Rota
1932–1999 · Combinatorics and philosophy at MIT

Rota was an Italian-American mathematician and philosopher who spent most of his career at MIT, where he transformed enumerative and algebraic combinatorics from a collection of clever tricks into a subject organized around structural principles: incidence algebras, Möbius functions on posets, and umbral calculus. He was equally serious about phenomenology and the philosophy of mind, publishing in both mathematics and philosophy journals, and insisted that mathematical taxonomy — naming and organizing — was itself a creative act worthy of care. The "Twelvefold Way," presented in his lecture notes and later in the textbook Enumerative Combinatorics he co-authored pedagogical material around, is a signature example of his style: take a question every student already sort of knows the answer to, and reveal that the true content is a small, complete, and previously invisible table.

History
- 1932 — Gian-Carlo Rota born in Vigevano, Italy.
- 1950s — Rota's family emigrates in the wake of wartime upheaval; Rota studies at Princeton and Yale, earning his PhD under Jacob T. Schwartz in 1956.
- 1960s — Rota's foundational work on Möbius functions of partially ordered sets ("On the Foundations of Combinatorial Theory I," 1964) reframes inclusion–exclusion-type arguments, the same engine used to count surjections here, as instances of Möbius inversion on posets.
- 1970s — Rota, at MIT, develops and teaches the organizing scheme now called the Twelvefold Way as a way of unifying stars-and-bars, Stirling numbers, and integer partitions under one roof for students of enumerative combinatorics.
- 1978 — Rota's collaboration and mentorship contribute to Richard Stanley's Enumerative Combinatorics, where a version of the Twelvefold Way appears in expository form and becomes the standard reference presentation.
Why is it called the "Twelvefold Way" if the table above only shows a 4×34\times3 grid, which is twelve cells — isn't that just the same thing?

Yes — the name refers exactly to the fact that crossing two binary choices (balls distinguishable or not; boxes distinguishable or not) with three basic constraint types (no constraint, injective, surjective) yields 2×2×3=122\times2\times3=12 genuinely distinct enumeration problems. The table's four rows in this article group two axes into one column of four labeled row-pairs for readability, but the count of essentially different problems is twelve; the fourth "constraint," bijective, is not independently counted because it only makes sense when n=kn=k, at which point it coincides with either the injective or surjective column (both equal n!n! in the distinguishable/distinguishable case when n=kn=k), so it does not add a thirteenth genuinely new case.

Is there a slicker way to remember which cells use Stirling numbers versus integer partitions?

Yes: Stirling numbers of the second kind appear whenever balls are distinguishable but boxes are not (they count set partitions, which remember which specific balls are grouped together), while integer partitions appear whenever both balls and boxes are indistinguishable (only the sizes of the groups survive, not which elements form them). If boxes are distinguishable, you never need Stirling numbers or partitions at all — those cells reduce to binomial coefficients (Combinations with Repetition and its variants), because distinguishable boxes let you track an occupancy vector directly.

Does the injective column ever need Stirling numbers or partitions?

No. Injective functions have no repeated outputs, so there is no nontrivial "grouping" data to remember — an injection is already the simplest possible structure, an embedding of NN into KK. This is why the injective column of the table is uniformly simple: kn‾k^{\underline n}, (kn)\binom{k}{n}, and two trivial indicator cases. Injectivity and the need for Stirling numbers/partitions are in tension, since those objects exist precisely to encode non-trivial groupings that injectivity forbids.

How does this table relate to occupancy problems in statistical mechanics, like Bose–Einstein statistics?

Directly: modeling nn particles among kk energy states as "balls into boxes," classical (Maxwell–Boltzmann) statistics treats particles as distinguishable, giving the knk^n or related distinguishable-ball cells; Bose–Einstein statistics treats particles as indistinguishable bosons with distinguishable states, landing in the indistinguishable-balls/distinguishable-boxes row governed by (n+k−1k−1)\binom{n+k-1}{k-1}-type counts; and further constraints (like the Pauli exclusion principle for fermions, forcing at most one particle per state) correspond to the injective column, giving (kn)\binom{k}{n}. The Twelvefold Way is thus a combinatorial skeleton underlying the three classical quantum statistics.

What goes wrong if I try to compute the indistinguishable-balls, indistinguishable-boxes, unconstrained cell by summing binomial coefficients instead of partition numbers?

You get the wrong answer because binomial coefficients count occupancy vectors distinguishing which box got how many balls, which is exactly the information erased once boxes become indistinguishable. Once boxes are indistinguishable, occupancy vectors that are rearrangements of each other (like (3,1,0)(3,1,0) and (1,3,0)(1,3,0) for k=3k=3 boxes) must be identified, and the object that correctly accounts for this identification is an integer partition (an unordered list of positive part sizes), not a composition (an ordered list) counted by binomial coefficients.

Is the formula S(n,k)=1k!∑j(−1)j(kj)(k−j)nS(n,k) = \frac{1}{k!}\sum_j (-1)^j\binom{k}{j}(k-j)^n always guaranteed to be an integer, even though it has a k!k! in the denominator?

Yes, and this is a nontrivial fact guaranteed by the theorem's own proof: the sum ∑j(−1)j(kj)(k−j)n\sum_j(-1)^j\binom{k}{j}(k-j)^n was shown to equal ∣Surj(N,K)∣|\mathrm{Surj}(N,K)|, an actual count of functions, and separately shown to equal k! S(n,k)k!\,S(n,k) via the explicit bijection Φ\Phi with (partition, bijection-to-KK) pairs. Since S(n,k)S(n,k) is by definition a count of set partitions (an integer), the division by k!k! is guaranteed to land on an integer — the apparent fraction is an artifact of the inclusion–exclusion derivation, not evidence of non-integrality.

Where does this table lead next, and why should I care about Pólya enumeration afterward?

The Twelvefold Way handles only two extreme symmetry regimes on each side: the trivial group (distinguishable) and the full symmetric group (indistinguishable). Many real problems — coloring the faces of a cube, counting distinct necklaces under rotation, counting molecules with a specific symmetry group — need to quotient by some intermediate group of symmetries, like a rotation group, which is neither trivial nor the full symmetric group. Polya Enumeration generalizes exactly this, replacing "distinguishable/indistinguishable" with an arbitrary permutation group GG acting on the balls or boxes, and the Twelvefold Way's easy cells become the two extreme special cases of Pólya's much more general cycle-index formula.

Before this