Mathwords logoMathwords

Twelvefold Way — Definition, Formula & Example

The Twelvefold Way is a table of the 12 basic ways to count placements of n balls into k boxes. The right formula depends on whether the balls are distinguishable, whether the boxes are distinguishable, and whether a box may hold any number of balls, at most one ball, or at least one ball.

Let NN and KK be finite sets with ∣N∣=n|N| = n and ∣K∣=k|K| = k. The Twelvefold Way counts functions f:N→Kf: N \to K. A function may be arbitrary, injective, or surjective. It may also be counted up to one of four equivalences: none, permutations of NN, permutations of KK, or permutations of both. The 3 conditions times 4 equivalences give 12 counting problems.

Key Formula

anyat most 1 per boxat least 1 per boxdistinct balls, distinct boxesknkn‾k! S(n,k)identical balls, distinct boxes(n+k−1n)(kn)(n−1k−1)distinct balls, identical boxes∑i=0kS(n,i)[n≤k]S(n,k)identical balls, identical boxesp≤k(n)[n≤k]pk(n)\begin{array}{l|c|c|c} & \text{any} & \text{at most 1 per box} & \text{at least 1 per box} \\ \hline \text{distinct balls, distinct boxes} & k^n & k^{\underline{n}} & k!\,S(n,k) \\ \text{identical balls, distinct boxes} & \binom{n+k-1}{n} & \binom{k}{n} & \binom{n-1}{k-1} \\ \text{distinct balls, identical boxes} & \sum_{i=0}^{k} S(n,i) & [n \le k] & S(n,k) \\ \text{identical balls, identical boxes} & p_{\le k}(n) & [n \le k] & p_k(n) \end{array}
Where:
  • nn = Number of balls (the domain size)
  • kk = Number of boxes (the codomain size)
  • kn‾k^{\underline{n}} = Falling factorial, k(k−1)⋯(k−n+1)k(k-1)\cdots(k-n+1), equal to k!(k−n)!\frac{k!}{(k-n)!} when n≤kn \le k and to 00 when n>kn > k
  • S(n,k)S(n,k) = Stirling number of the second kind: the number of ways to split n distinct objects into k nonempty unlabeled groups
  • pk(n)p_k(n) = Number of partitions of n into exactly k positive parts; p≤k(n)p_{\le k}(n) allows at most k parts
  • [n≤k][n \le k] = Equals 1 if n≤kn \le k and 0 otherwise

Worked Example

Problem: You pack 4 items into 2 bags, and neither bag may be empty. Count the packings in four settings: the items are distinct or identical, and the bags are distinct (red and blue) or identical.
Step 1: Distinct items, distinct bags. Each item has 2 choices of bag. Then subtract the 2 packings that leave a bag empty. This matches k! S(n,k)=2⋅7k!\,S(n,k) = 2 \cdot 7.
24−2=142^4 - 2 = 14
Step 2: Distinct items, identical bags. Every split now gets counted twice, once for each way to color the bags. No bag is empty, so you can divide by 2!2!. The result is S(4,2)S(4,2).
142!=7\frac{14}{2!} = 7
Step 3: Identical items. Only the bag sizes matter. With distinct bags, the possible (red, blue) sizes are (1,3), (2,2), and (3,1), so the count is (31)\binom{3}{1}. With identical bags, (1,3) and (3,1) are the same packing. That leaves the partitions 3+1 and 2+2.
(4−12−1)=3,p2(4)=2\binom{4-1}{2-1} = 3, \qquad p_2(4) = 2
Answer: The counts are 14, 7, 3, and 2. The same physical task gives four different answers, depending on what you treat as distinguishable.

Why It Matters

Gian-Carlo Rota introduced the Twelvefold Way, and it appears in the first chapter of Richard Stanley's Enumerative Combinatorics, Volume 1, a standard graduate text. It turns "which formula do I use?" into two yes-or-no questions and one three-way choice. It also shows where Stirling numbers and integer partitions come from. Problems in hashing, job scheduling, and particle statistics are all ball-and-box problems in disguise.

Common Mistakes

Mistake: Dividing knk^n by k!k! to make the boxes identical when boxes are allowed to be empty.
Correction: Division by k!k! works only when no two boxes can end up with the same contents, which is guaranteed when every box is nonempty. Once two or more boxes can be empty, swapping them gives no new arrangement. Take 3 distinct balls into 3 identical boxes: 27/6=4.527/6 = 4.5 is not even a whole number. The correct count is S(3,1)+S(3,2)+S(3,3)=1+3+1=5S(3,1)+S(3,2)+S(3,3) = 1+3+1 = 5.

Related Terms

  • Combinatorics — Parent field whose counting problems this table organizes
  • Permutation Calculator — Computes the injective case with distinct balls and boxes
  • Combination — Gives the injective case with identical balls, distinct boxes
  • Permutation — Counts ordered arrangements, a case in the table