Stirling numbers of the second kind count ways to divide distinct objects into exactly nonempty, unlabelled groups. The Bell number counts all such divisions, allowing any number of groups. They quantify the size of a grouping search space: for example, how many different clusterings of a fixed set of research signals could be considered before any data or clustering criterion is introduced.
The objects retain their identities; the groups have no names or order. Every object belongs to exactly one group. Thus and are the same partition of the set, while is different. Groups may have different sizes. These are the set partitions in NIST's definitions.
See every possibility for four signals
Take four distinct signal labels . Count partitions by their number of groups:
| Groups | Second-kind count | What is being counted |
|---|---|---|
| 1 | 1 | All four labels together |
| 2 | 7 | Four singleton–triple splits and three pair–pair splits |
| 3 | 6 | Choose the one pair; the other two labels are singletons |
| 4 | 1 | Every label on its own |
For three groups, the binomial coefficient chooses that pair. For two groups, a direct check is to put each label in one of two temporarily named boxes. There are assignments, but two leave a box empty. Removing those and forgetting the box names gives .
Every row is a different grouping. Swapping the order in which its blocks are written does not create another one.
The Bell total adds the counts across all possible group numbers:
The empty set has one partition with zero blocks, so . For , ; also when .
Add one object, rather than list everything
The recurrence relation is
Look at the block containing the last object. If that object is alone, remove its singleton block: the remaining objects have blocks. Otherwise remove just the object: there are still blocks, and any one could receive it again. These disjoint cases give the two terms in NIST's recurrence.
For the two-group count above,
This builds a table of exact counts without explicitly constructing every partition.
A change in labels changes the answer
If the groups have distinct names, every unlabelled -block partition can be assigned those names in ways, where denotes factorial. Thus there are assignments to named groups when every group must be used. Hulpke's Twelvefold Way discussion makes this distinction explicit.
For the four labels and two named groups, that count is . Allowing empty groups instead gives . Neither is the unlabelled count of seven. Prescribing particular group sizes imposes another restriction; Counting and Combinatorics develops the multinomial count for named groups with specified sizes. Its public preview is available; the full lesson requires membership.
Counts alone also supply no probability model. Fifteen possible partitions need not be equally likely under a random assignment procedure, and a clustering algorithm does not necessarily search all fifteen or treat them equally.
Two other uses of “Stirling”
Unsigned Stirling numbers of the first kind, often written , count permutations with exactly cycles. Cyclic arrangement within a block matters there: a set partition records only membership. For example, , whereas . A signed convention uses ; check the convention before reading a table. NIST defines both kinds together.
Stirling approximation concerns the size of a factorial. It is a separate result from these exact partition counts.
Sources
- NIST Digital Library of Mathematical Functions, §26.8 — first- and second-kind definitions, Tables 26.8.1–2, and recurrence 26.8.22.
- NIST Digital Library of Mathematical Functions, §26.7 — Bell-number definition, empty-set convention and sum over second-kind counts.
- Alexander Hulpke, Colorado State University, Combinatorics course notes — The Twelvefold Way and Chapter 2's Stirling-number discussion distinguish named and unlabelled blocks.