What are Stirling numbers of the second kind?
A Stirling number of the second kind, written \(S(n,k)\) (also shown as \(\{n \atop k\}\) or \(S2(n,k)\)), counts the number of ways to partition a set of n labeled (distinguishable) objects into exactly k non-empty, unlabeled subsets (called blocks). This calculator computes an entire row: for a fixed n it lists \(S(n,k)\) for \(k = 0, 1, 2, ..., n\) — every value in row n of the Stirling triangle. It is a pure-mathematics combinatorial quantity with no regional dependence.
How to use it
Enter a non-negative integer n (the number of elements in your set) and submit. The tool returns a table with two columns, k and \(S(n,k)\), plus the row sum, which is the Bell number \(B(n)\) — a handy sanity check. All values are computed with arbitrary-precision integers, so they stay exact even when they grow far beyond what a 64-bit number can hold (which happens around n = 20-25).
The formula explained
The most robust method is the recurrence $$S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1),$$ built up from the base case \(S(0,0) = 1\). Boundary values are \(S(n,0) = 0\) for \(n \ge 1\), \(S(n,n) = 1\), \(S(n,1) = 1\) for \(n \ge 1\), and \(S(n,k) = 0\) for \(k > n\). There is also an explicit closed form, $$S(n,k) = \frac{1}{k!} \cdot \sum (-1)^{k-j} C(k,j)\, j^n,$$ but in floating point it suffers large cancellation, so we use the recurrence with exact integers.
Worked example (n = 5)
Row 5 is: k=0 → 0, k=1 → 1, k=2 → 15, k=3 → 25, k=4 → 10, k=5 → 1. Check from row 4 = [0,1,7,6,1]: $$S(5,2) = 2\cdot 7 + 1 = 15,$$ $$S(5,3) = 3\cdot 6 + 7 = 25,$$ $$S(5,4) = 4\cdot 1 + 6 = 10.$$ The row sums to \(0+1+15+25+10+1 = 52\), which equals the Bell number \(B(5) = 52\).
Stirling Triangle of the Second Kind (Rows 0–8) and Bell Numbers
The Stirling number of the second kind \(S(n,k)\) counts the ways to partition a set of \(n\) distinct elements into exactly \(k\) non-empty, unlabeled subsets. Each entry follows the recurrence \(S(n,k) = k\,S(n-1,k) + S(n-1,k-1)\), with \(S(0,0)=1\) and \(S(n,0)=0\) for \(n\ge 1\). The row sum is the Bell number \(B(n)=\sum_{k=0}^{n} S(n,k)\), the total number of partitions of an \(n\)-element set.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 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 |
Empty cells are positions where \(k>n\), which are zero by definition.
How to read the table
- Worked check of the recurrence: \(S(8,3) = 3\cdot S(7,3) + S(7,2) = 3\cdot 301 + 63 = 903 + 63 = 966\).
- Another check: \(S(8,4) = 4\cdot S(7,4) + S(7,3) = 4\cdot 350 + 301 = 1400 + 301 = 1701\).
- Row sum check for \(n=5\): \(0+1+15+25+10+1 = 52 = B(5)\).
- Edges: \(S(n,1)=1\) and \(S(n,n)=1\); also \(S(n,2)=2^{n-1}-1\) (for example \(S(8,2)=127\)).
FAQ
Why is \(S(n,0) = 0\) for \(n \ge 1\)? You cannot partition a non-empty set into zero blocks; only the empty set has the empty partition, giving \(S(0,0) = 1\).
What is the row sum? Summing \(S(n,k)\) over all k gives the Bell number \(B(n)\), the total number of partitions of an n-element set.
How large can n be? This tool allows up to n = 200; values become enormous but remain exact thanks to big-integer arithmetic.