Mathematics.

enumerative combinatorics

The Twelvefold Way

Combinatorics50 minDifficulty8 out of 10

You should know: permutations, combinations, stirling numbers

Overview

The twelvefold way, a name popularized by Richard Stanley, is a unifying framework that organizes twelve related enumeration problems — all variations on 'distribute n balls into k boxes' — into a single 3-by-4 table. The three rows classify the balls and boxes as distinguishable or not (balls distinguishable/boxes distinguishable, balls indistinguishable/boxes distinguishable, or balls distinguishable/boxes indistinguishable), while the four columns impose different constraints on how balls land in boxes: no constraint, at most one ball per box (injective), at least one ball per box (surjective), or exactly one ball per box in a bijective sense restricted to counting arrangements. Each of the twelve cells corresponds to a counting formula already familiar from elsewhere in combinatorics — powers, falling factorials, binomial coefficients, Stirling numbers, or partition numbers — and seeing them side by side clarifies why those formulas exist and how they relate.

Intuition

Every one of the twelve problems answers 'how many ways to distribute n balls into k boxes?', and the only things that change are (1) whether swapping two balls creates a genuinely new arrangement (balls distinguishable) versus not, (2) whether swapping two boxes creates a new arrangement (boxes distinguishable) versus not, and (3) whether every box must get at least one ball, at most one ball, or there's no restriction. Distinguishable balls and boxes with no restriction gives every ball k independent choices of box: k^n, an exponential. Making the boxes indistinguishable collapses many of those labeled arrangements together — that collapsing is exactly what Stirling numbers of the second kind count. Making the balls indistinguishable instead turns the problem into distributing an amount (stars and bars) rather than assigning individuals. The twelvefold way is valuable precisely because it shows these are not twelve unrelated formulas but one problem viewed through three binary lenses.

Formal Definition

Definition

Fix n balls and k boxes. The twelve cases arise from choosing (a) whether balls are distinguishable, and if not-distinguishable whether boxes are distinguishable, and (b) whether the function from balls to boxes is arbitrary, injective, or surjective:

Distinguishable balls, distinguishable boxes, any function: kn\text{Distinguishable balls, distinguishable boxes, any function: } k^n
Case 1
Distinguishable balls, distinguishable boxes, injective (n≤k): k(k−1)⋯(k−n+1)=kn‾\text{Distinguishable balls, distinguishable boxes, injective (}n \le k\text{): } k(k-1)\cdots(k-n+1) = k^{\underline{n}}
Case 2
Distinguishable balls, distinguishable boxes, surjective: k! S(n,k)\text{Distinguishable balls, distinguishable boxes, surjective: } k!\, S(n,k)
Case 3
Indistinguishable balls, distinguishable boxes, any function: (n+k−1k−1)\text{Indistinguishable balls, distinguishable boxes, any function: } \binom{n+k-1}{k-1}
Case 4 (stars and bars)
Indistinguishable balls, distinguishable boxes, at most one per box: (kn)\text{Indistinguishable balls, distinguishable boxes, at most one per box: } \binom{k}{n}
Case 5
Indistinguishable balls, distinguishable boxes, at least one per box: (n−1k−1)\text{Indistinguishable balls, distinguishable boxes, at least one per box: } \binom{n-1}{k-1}
Case 6
Distinguishable balls, indistinguishable boxes, any function: ∑j=0kS(n,j)\text{Distinguishable balls, indistinguishable boxes, any function: } \sum_{j=0}^{k} S(n,j)
Case 7
Distinguishable balls, indistinguishable boxes, surjective (exactly k nonempty): S(n,k)\text{Distinguishable balls, indistinguishable boxes, surjective (exactly } k \text{ nonempty): } S(n,k)
Case 8

Worked Examples

  1. Each of the 3 balls independently chooses 1 of 2 boxes — this is Case 1 of the twelvefold way, k^n.

    23=82^3 = 8

Answer: 8 distributions.

Practice Problems

Difficulty 5/10

How many ways can 4 distinguishable balls be placed into 3 distinguishable boxes with no restriction?

Difficulty 6/10

How many nonnegative-integer-solution distributions are there of 5 indistinguishable balls into 3 distinguishable boxes (no restriction)?

Difficulty 8/10

A teacher distributes 4 distinguishable prizes to 3 distinguishable students so that every student gets at least one prize. How many ways, using S(4,3)=6?

Quiz

In the twelvefold way, distributing n distinguishable balls into k distinguishable boxes with no restriction is counted by:
Distributing n distinguishable balls into k indistinguishable boxes so every box is nonempty is counted by:
What organizing principle defines the twelvefold way's 3×4 table?

Summary

  • The twelvefold way organizes 12 classic counting problems — n balls into k boxes — into a 3×4 table by distinguishability and constraint type.
  • Distinguishable balls & boxes, no restriction: k^n. Injective: falling factorial k^(n). Surjective: k!·S(n,k).
  • Indistinguishable balls, distinguishable boxes reduces to stars-and-bars: C(n+k-1,k-1), or C(n-1,k-1) if every box must be nonempty.
  • Distinguishable balls, indistinguishable boxes, surjective (exactly k nonempty groups) is precisely the Stirling number of the second kind S(n,k).
  • Seeing all twelve cases together reveals that binomial coefficients, Stirling numbers, and partition numbers are all facets of one underlying distribution problem.

References

  1. BookStanley, R.P. Enumerative Combinatorics, Vol. 1, 2nd ed., Ch. 1.9 (Twelvefold Way).
  2. WebsiteWikipedia — Twelvefold way