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.
Reviewed by Manoj Kumar, Mathematics Educator
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.
References
Reviewed by Manoj Kumar, Mathematics Educator · Editorial policy