Stirling Number Calculator
Calculate Stirling numbers of the first and second kind for combinatorial problems. Enter values for instant results with step-by-step formulas.
Formula
S(n, k) = k * S(n-1, k) + S(n-1, k-1)
Where S(n, k) is the Stirling number of the second kind counting the number of partitions of an n-element set into k non-empty subsets. For the first kind, |s(n, k)| = (n-1) * |s(n-1, k)| + |s(n-1, k-1)| counts permutations with k cycles.
Worked Examples
Example 1: Partitioning Students into Study Groups
Problem: In how many ways can 5 students be divided into exactly 3 non-empty study groups?
Solution: We need S(5, 3), the Stirling number of the second kind.\nUsing the recurrence: S(5, 3) = 3 * S(4, 3) + S(4, 2)\nS(4, 3) = 6, S(4, 2) = 7\nS(5, 3) = 3 * 6 + 7 = 18 + 7 = 25\nSo there are 25 ways to partition 5 students into 3 non-empty groups.
Result: S(5, 3) = 25 ways to partition 5 elements into 3 subsets
Example 2: Counting Permutations by Cycle Structure
Problem: How many permutations of 4 elements have exactly 2 cycles?
Solution: We need |s(4, 2)|, the unsigned Stirling number of the first kind.\nUsing the recurrence: |s(4, 2)| = 3 * |s(3, 2)| + |s(3, 1)|\n|s(3, 2)| = 3, |s(3, 1)| = 2\n|s(4, 2)| = 3 * 3 + 2 = 9 + 2 = 11\nSo there are 11 permutations of {1, 2, 3, 4} with exactly 2 disjoint cycles.
Result: |s(4, 2)| = 11 permutations with exactly 2 cycles
Frequently Asked Questions
What are Stirling numbers and why are they important?
Stirling numbers are fundamental combinatorial quantities that appear in many areas of mathematics including combinatorics, number theory, and analysis. There are two kinds of Stirling numbers. Stirling numbers of the second kind S(n, k) count the number of ways to partition a set of n elements into exactly k non-empty subsets. Stirling numbers of the first kind s(n, k) (unsigned) count the number of permutations of n elements with exactly k disjoint cycles. Both kinds satisfy useful recurrence relations and appear in formulas for converting between ordinary and factorial powers of polynomials.
What is the difference between Stirling numbers of the first and second kind?
Stirling numbers of the second kind, denoted S(n, k), count set partitions. For example, S(4, 2) = 7 means there are 7 ways to split the set {1, 2, 3, 4} into exactly 2 non-empty groups. Stirling numbers of the first kind, denoted |s(n, k)| when unsigned, count permutations by cycle structure. For instance, |s(4, 2)| = 11 means there are 11 permutations of 4 elements that decompose into exactly 2 cycles. While both are triangular arrays like Pascal triangle, they serve different combinatorial purposes and satisfy different recurrences: S(n, k) = k * S(n-1, k) + S(n-1, k-1), while |s(n, k)| = (n-1) * |s(n-1, k)| + |s(n-1, k-1)|.
How do you calculate Stirling numbers of the second kind?
Stirling numbers of the second kind can be calculated using the recurrence relation S(n, k) = k * S(n-1, k) + S(n-1, k-1), with base cases S(0, 0) = 1 and S(n, 0) = S(0, k) = 0 for n, k greater than 0. The intuition behind the recurrence is that element n either joins an existing partition (k choices, giving k * S(n-1, k)) or forms its own singleton partition (giving S(n-1, k-1)). There is also an explicit formula using inclusion-exclusion: S(n, k) = (1/k!) times the sum from j = 0 to k of (-1)^j times C(k, j) times (k - j)^n. Dynamic programming with a table is the most efficient approach for computing multiple values.
How are Stirling numbers related to Bell numbers?
Bell numbers are the row sums of the Stirling numbers of the second kind. The nth Bell number B(n) equals the sum of S(n, k) for k from 0 to n, representing the total number of ways to partition a set of n elements into any number of non-empty subsets. For example, B(4) = S(4,1) + S(4,2) + S(4,3) + S(4,4) = 1 + 7 + 6 + 1 = 15. Bell numbers grow very rapidly: B(10) = 115,975 and B(15) = 1,382,958,545. They can also be computed using the Bell triangle, a construction similar to Pascal triangle, and have applications in set theory, combinatorics, and computer science.
What are practical applications of Stirling numbers?
Stirling numbers appear in numerous practical applications across mathematics and computer science. In statistics, they are used for computing moments of distributions and in the theory of cumulants. In computer science, Stirling numbers of the second kind model the number of ways to distribute n distinct objects into k identical containers (like hash table analysis). They appear in the analysis of algorithms, particularly sorting and searching algorithms. In numerical analysis, they connect forward differences to derivatives. In combinatorial chemistry, they help count molecular configurations. They also appear in coding theory and in the enumeration of surjective functions between finite sets.
What is the recurrence relation for Stirling numbers of the first kind?
The unsigned Stirling numbers of the first kind satisfy the recurrence |s(n, k)| = (n - 1) * |s(n-1, k)| + |s(n-1, k-1)|, with base cases |s(0, 0)| = 1 and |s(n, 0)| = |s(0, k)| = 0 for positive n and k. The combinatorial interpretation is clear: when inserting element n into a permutation of {1, ..., n-1}, it either gets inserted into one of the existing cycles (n - 1 positions, one before each existing element) keeping the cycle count the same, or it forms a new fixed-point cycle by itself, increasing the cycle count by one. Signed Stirling numbers of the first kind include an alternating sign factor: s(n, k) = (-1)^(n-k) * |s(n, k)|.