How this calculation works
The recurrence either inserts the last item into one of k existing groups or makes it a singleton group.
S(n,k) = k S(n−1,k) + S(n−1,k−1)A worked example
Five distinct items can be split into three nonempty groups in 25 ways.
Good to know
Groups have no order.
Reference: NIST DLMF, Functions of Number Theory (opens in a new tab) ↗
Put distinct items into unlabelled nonempty groups
For five distinct items and three groups, the Stirling number of the second kind is S(5,3) = 25. One possible partition is {A,B}, {C,D}, {E}. Reordering these three groups does not create a new partition, and reordering A and B inside their group also changes nothing.
The recurrence S(n,k) = kS(n − 1,k) + S(n − 1,k − 1) follows by considering the last item. Either add it to one of k existing groups, or give it its own singleton group. For the default case, 3S(4,3) + S(4,2) = 3 × 6 + 7 = 25.
Keep labels on items separate from labels on groups
The items are distinct but the groups are unlabelled. If three destination boxes have fixed names, each partition can be assigned to those boxes in 3! ways. Surjections from five distinct items onto three labelled destinations therefore number 3! × 25 = 150. Allowing empty destinations would change the count again.
The Stars and bars distribution calculator treats the items as identical and the boxes as labelled, almost reversing the distinctions used here. S(n,k) is zero when k exceeds n because nonempty groups require at least one item each. It equals one when k = n, with every item alone, and when k = 1 for a positive item count.
Read more: NIST DLMF Stirling numbers of the second kind (opens in a new tab) ↗
A few questions, answered
What does S(0,0) equal?
It is one, representing the single empty partition of an empty set.
What happens for positive n and zero groups?
The result is zero because positive numbers of items cannot be placed into no groups.