What is the Stirling Number of the Second Kind?
The Stirling number of the second kind, written \(S(n,k)\), counts the number of ways to partition a set of n distinct (labeled) elements into exactly k non-empty, unlabeled subsets. It is a fundamental quantity in combinatorics and appears in problems involving set partitions, surjections, and the Bell numbers. This is a pure-mathematics tool that works the same way everywhere.
How to Use This Calculator
Enter the set size n and the number of subsets k. Both must be non-negative integers. Press calculate to get \(S(n,k)\), the exact count of partitions. If k is greater than n, the result is 0, because you cannot fill more non-empty subsets than there are elements.
The Formula Explained
The explicit form is $$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}\, j^{n}$$ where \(\binom{k}{j}\) is the binomial coefficient. An equivalent and numerically safer way is the recurrence $$S(n,k) = k\, S(n-1,k) + S(n-1,k-1)$$ with base cases \(S(0,0)=1\), \(S(n,0)=0\) for \(n>0\), and \(S(0,k)=0\) for \(k>0\). This calculator uses the recurrence to avoid floating-point cancellation. Useful special cases: \(S(n,1)=1\), \(S(n,n)=1\), and \(S(n,2)=2^{n-1}-1\).
Worked Example
For \(n=5\) and \(k=2\): using the special case $$S(5,2)=2^{5-1}-1=16-1=15$$ The recurrence confirms this: $$S(5,2)=2\cdot S(4,2)+S(4,1)=2\cdot 7+1=15$$ So there are 15 ways to split a 5-element set into two non-empty groups.
Table of Stirling Numbers of the Second Kind S(n,k) for n = 0 to 10
Each entry is the number of ways to partition a set of n labeled elements into exactly k non-empty, unlabeled blocks. The table is built from the recurrence \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\), with \(S(0,0)=1\) and \(S(n,0)=S(0,n)=0\) for \(n\ge 1\). Blank cells are \(k>n\), where S(n,k)=0. The last column is the row sum, which is the Bell number B(n). For example, S(10,4) = 34105.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Row sum B(n) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | ||||||||||
| 1 | 0 | 1 | 1 | |||||||||
| 2 | 0 | 1 | 1 | 2 | ||||||||
| 3 | 0 | 1 | 3 | 1 | 5 | |||||||
| 4 | 0 | 1 | 7 | 6 | 1 | 15 | ||||||
| 5 | 0 | 1 | 15 | 25 | 10 | 1 | 52 | |||||
| 6 | 0 | 1 | 31 | 90 | 65 | 15 | 1 | 203 | ||||
| 7 | 0 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | 877 | |||
| 8 | 0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 | 4140 | ||
| 9 | 0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 | 21147 | |
| 10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 | 115975 |
Check of one entry with the recurrence: \(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\). Always \(S(n,1)=1\), \(S(n,2)=2^{n-1}-1\), \(S(n,n-1)=\binom{n}{2}\) and \(S(n,n)=1\).
Key Terms and Notation
- Set partition
- A way of splitting a set into non-empty, pairwise disjoint subsets (blocks) whose union is the whole set. Order of blocks and order within a block do not matter.
- Labeled vs. unlabeled
- The n elements are labeled (distinguishable, e.g. 1, 2, …, n). The k subsets are unlabeled: swapping two blocks gives the same partition. If the blocks were labeled, the count would be k!·S(n,k) instead.
- Non-empty block
- Every one of the k subsets must contain at least one element. This is why S(n,0)=0 for n ≥ 1 and S(n,k)=0 when k > n.
- Notation S(n,k)
- The Stirling number of the second kind, also written \(\left\{ n \atop k \right\}\). It is computed by \(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\).
- Bell number B(n)
- The total number of partitions of an n-element set into any number of blocks: \(B(n)=\sum_{k=0}^{n}S(n,k)\). The first values are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975.
- Binomial coefficient
- \(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\), the number of ways to choose j items from k. It appears in the inclusion–exclusion formula above.
- Surjection
- A function from an n-set onto a k-set in which every element of the k-set is hit at least once. The number of such functions is \(k!\cdot S(n,k)\): partition the domain into k blocks, then assign the blocks to the k targets in k! ways.
Second kind vs. first kind. Stirling numbers of the second kind count partitions of a set into k blocks. Stirling numbers of the first kind, written \(c(n,k)\) or \(\left[ n \atop k \right]\) (unsigned), count permutations of n elements with exactly k cycles. They obey a different recurrence, \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\), and are related to the second kind by being inverse matrices of each other (with signs).
FAQ
Why is \(S(0,0)=1\)? By convention, the empty set has exactly one partition into zero parts: the empty partition.
What happens when \(k > n\)? The result is 0, since every subset must be non-empty and you have too few elements.
How does this relate to Bell numbers? Summing \(S(n,k)\) over all k from 0 to n gives the Bell number \(B(n)\), the total number of partitions of an n-element set.