Maths & numbers

Stirling set partition count calculator

Count ways to split labeled items into exactly k unlabeled nonempty groups.

Your numbers

Calculated on your device. Your inputs aren’t sent to us.

Your result

Ready when you are

Enter your inputs and select Calculate.

Report an issue

Behind the numbers

How this calculation works

The recurrence either inserts the last item into one of k existing groups or makes it a singleton group.

THE FORMULAS(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.

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.

One partition of five distinct letters into three nonempty unlabelled groups is AB, CD and EA BC DE3 × S(4,3) + S(4,2)3 × 6 + 7 = 25
This is one of S(5,3) = 25 partitions. Exchanging the three displayed groups does not produce a different partition.

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.

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.

Find your calculator

Start typing to explore the library.