Stirling Numbers and the Twelvefold Way

Partitions, surjections, and cycles in the twelvefold way.

The idea

The twelvefold way organizes the problems of counting the ways to place $n$ balls into $k$ boxes. The count depends on which placements we treat as the same. If the balls carry names, moving ball $3$ to a different box produces a new placement; if they do not, only the number of balls in each box matters. If the boxes carry labels, exchanging the contents of box $1$ and box $2$ is a change; if they do not, it is the same placement seen twice. Adding the option of forbidding empty boxes gives twelve genuinely different questions.

Several of the twelve require one new count: the number of ways to partition an $n$-element set into exactly $k$ nonempty blocks when the blocks themselves carry no names, so that listing the same grouping in a different order does not produce a second partition. This count is the Stirling number of the second kind $S(n, k)$.

It has no simple closed form, but it obeys a recurrence, found by asking what the last element does: it either joins one of the $k$ blocks already present, or opens a new block of its own, $S(n, k) = k\,S(n-1, k) + S(n-1, k-1).$

Attaching labels to the boxes is a separate choice, made after the partition, and it is what connects $S(n, k)$ to the other entries of the twelvefold way.

Ways to work on it

• Walkthrough. Count the ways to partition a set into blocks, and use the count to count surjections.
• Practice. Evaluate a small Stirling number of the second kind.
• Hardest. Count surjections, then permutations with a prescribed number of cycles.

Not sure where to start? Take the ten-question placement test.