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 and be finite sets with and . The Twelvefold Way counts functions . A function may be arbitrary, injective, or surjective. It may also be counted up to one of four equivalences: none, permutations of , permutations of , or permutations of both. The 3 conditions times 4 equivalences give 12 counting problems.
Key Formula
Where:
- = Number of balls (the domain size)
- = Number of boxes (the codomain size)
- = Falling factorial, , equal to when and to when
- = Stirling number of the second kind: the number of ways to split n distinct objects into k nonempty unlabeled groups
- = Number of partitions of n into exactly k positive parts; allows at most k parts
- = Equals 1 if 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 .
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 . The result is .
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 . With identical bags, (1,3) and (3,1) are the same packing. That leaves the partitions 3+1 and 2+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 by to make the boxes identical when boxes are allowed to be empty.
Correction: Division by 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: is not even a whole number. The correct count is .
