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.
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.
