The Twelvefold Way

The Twelvefold Way is a systematic classification of twelve closely related counting problems in combinatorics. It shows that many familiar formulas (permutations, combinations, Stirling numbers, partitions) are all instances of the same underlying question:

How many essentially different ways are there to distribute n balls into k urns?

The twelve cases arise from three simple choices: whether balls are distinguishable or identical, whether urns are distinguishable or identical, and whether there are restrictions on how many balls each urn can hold.

Based on John D. Cook's summary of the framework originally systematized by Gian-Carlo Rota.

The Twelvefold Way — Click a cell to select

	Labeled UrnsL. Urns			Unlabeled UrnsU. Urns
	Any	≥1	≤1	Any	≥1	≤1
Labeled BallsL. Balls	$k^n$	$k! \cdot S(n,k)$	$(k)_n$	$\sum_{i=1}^{k} S(n,i)$	$S(n,k)$	$[n \leq k]$
Unlabeled BallsU. Balls	$\binom{n+k-1}{n}$	$\binom{n-1}{k-1}$	$\binom{k}{n}$	$\sum_{i=1}^{k} p(n,i)$	$p(n,k)$	$[n \leq k]$

The number of ways to placeballs intourns

such that there isis5.

Partitions ≤k

\sum_{i=1}^{k} p(n,i)

Σ p(n,i) for i=1..k

Partition integer 4 into at most 4 parts.

•Integer partitions of n=4 into ≤k=4 parts
•Writing n=4 as sum of ≤k=4 positive integers (order doesn't matter)
•Ferrers/Young diagrams with ≤k=4 rows summing to n=4
•Ways to break n=4 into at most k=4 chunks

Enumerated Configurations

View as:

Shows groups of balls (size only matters)

All 5 configurations:

●●●●

●●●

●

●●

●