What Is a Set Partition? Stirling and Bell Numbers
Counting the ways to split a set of objects into groups uses Stirling numbers of the second kind and Bell numbers. Here's what they mean, with worked examples.
Try the set partitions calculatorPut these numbers to workOpen →A set partition is a way of splitting a group of distinct objects into non-empty groups, where every object belongs to exactly one group. Counting how many partitions are possible is a classic combinatorics question — for example, how many ways can you sort 11 different books into 4 packets? The answer comes from Stirling numbers of the second kind.
How partitions differ from combinations
Combinations (nCr) count how many ways to choose one subset of items from a larger set. A partition is different: it splits the whole set into several groups at once, with nothing left over. So combinations answer "which items to pick", while partitions answer "how to divide everyone up".
Stirling numbers of the second kind
S(n, k) is the number of ways to partition n distinct objects into exactly k non-empty, unlabeled groups. It follows the recurrence S(n, k) = k · S(n−1, k) + S(n−1, k−1), with S(n, n) = 1 and S(n, 1) = 1. Each new object either joins one of the k existing groups (k ways) or starts a fresh group.
Labeled vs unlabeled groups
- •If the groups are interchangeable (identical boxes), use S(n, k) directly.
- •If the groups are distinguishable (numbered boxes, or different people), multiply by k! because each partition can be handed to the labeled groups in k! ways.
- •That labeled count, k!·S(n, k), also equals the number of ways to assign n objects onto k groups with none left empty (surjections).
Bell numbers: any number of groups
If you don't fix the number of groups, the total number of partitions of n objects is the Bell number B(n) — simply the sum of S(n, k) over every k from 1 to n. B(3) = 5, B(4) = 15, and the numbers grow very quickly after that.