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 for accuracy by Manoj Kumar, Mathematics Educator
Stirling Number Calculator
Calculator
Adjust values & calculateEnter your values below. Every result is computed in your browser — no data is sent to any server.
Formula: S(n, k) = k * S(n-1, k) + S(n-1, k-1)
Worked example — S(5, 3) = 25 ways to partition 5 elements into 3 subsets
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. Using the recurrence: S(5, 3) = 3 * S(4, 3) + S(4, 2) S(4, 3) = 6, S(4, 2) = 7 S(5, 3) = 3 * 6 + 7 = 18 + 7 = 25 So 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. Using the recurrence: |s(4, 2)| = 3 * |s(3, 2)| + |s(3, 1)| |s(3, 2)| = 3, |s(3, 1)| = 2 |s(4, 2)| = 3 * 3 + 2 = 9 + 2 = 11 So 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)|.
How do Stirling numbers connect to polynomial conversion?
Stirling numbers provide the conversion coefficients between ordinary powers x^n and falling factorials x^(n) = x(x-1)(x-2)...(x-n+1). Specifically, x^n = sum of S(n, k) * x^(k) where S(n, k) are Stirling numbers of the second kind, and x^(n) = sum of s(n, k) * x^k where s(n, k) are signed Stirling numbers of the first kind. This makes them essential in finite calculus, where falling factorials play the role that ordinary powers play in standard calculus. These conversion formulas are used extensively in combinatorial identities, generating function manipulations, and the calculus of finite differences.
How fast do Stirling numbers grow?
Stirling numbers grow extremely rapidly with increasing n and k. For the second kind, the maximum value in row n occurs near k = n / ln(n), and these maximal values grow super-exponentially. For example, S(10, 5) = 42,525 while S(20, 10) = 5,842,527,603,927. The first kind grows similarly fast. The unsigned Stirling numbers of the first kind in row n sum to n factorial, which itself grows super-exponentially by Stirling approximation (pun intended since the approximation formula is named after a different Stirling). Due to this rapid growth, practical computation is limited to roughly n = 20-25 with standard integer arithmetic, beyond which big integer libraries become necessary.
What is the connection between Stirling numbers and surjective functions?
The number of surjective (onto) functions from a set of n elements to a set of k elements is exactly k! times S(n, k), where S(n, k) is the Stirling number of the second kind. This is because S(n, k) counts the ways to partition n elements into k non-empty subsets, and then k! assigns each subset to a distinct target element. For example, the number of onto functions from a 4-element set to a 3-element set is 3! times S(4, 3) = 6 times 6 = 36. This connection makes Stirling numbers crucial in enumerative combinatorics and has applications in coding theory, particularly in the study of error-correcting codes and data compression schemes.
How are Stirling numbers used in combinatorial identities?
Stirling numbers appear in many classical combinatorial identities. The orthogonality relation states that the matrices of Stirling numbers of the first and second kind are inverses of each other (with appropriate signs). The identity sum of |s(n, k)| for k = 1 to n equals n! connects first kind Stirling numbers to factorials. Worpitzky identity expresses x^n using Stirling numbers and binomial coefficients. The Dobinski formula for Bell numbers uses Stirling numbers of the second kind with exponential terms. These identities are not merely theoretical curiosities; they provide computational shortcuts, prove other results by algebraic manipulation, and connect seemingly unrelated combinatorial objects.
References
Reviewed for accuracy by Manoj Kumar, Mathematics Educator · Editorial policy
Related Calculators
🧮Sum of a Linear Number Sequence Calculator
Calculate sum of alinear number sequence with inputs, formulas, and instant results.
🧮Complex Number Calculator
Calculate complex number with inputs, formulas, and instant results.
🧮Prime Number Calculator
Calculate prime number with inputs, formulas, and instant results.
🧮Abundant Number Checker
Calculate abundant number checker with inputs, formulas, and instant results.
🧮Deficient Number Checker
Calculate deficient number checker with inputs, formulas, and instant results.
🧮Improper Fraction to Mixed Number Calculator
Calculate improper fraction to mixed number with inputs, formulas, and instant results.
🧮Mixed Number Calculator
Calculate mixed number with inputs, formulas, and instant results.
🧮Mixed Number to Improper Fraction Calculator
Calculate mixed number to improper fraction with inputs, formulas, and instant results.