Stirling Numbers Calculator
Calculate Stirling numbers of the first and second kind - fundamental combinatorial numbers
Enter non-negative integers where k ≤ n (max n = 100)
What are Stirling Numbers?
Stirling numbers are fundamental combinatorial numbers that appear in many areas of mathematics. There are two kinds, each counting different combinatorial structures.
Stirling Numbers of the Second Kind - S(n, k)
S(n, k) counts the number of ways to partition a set of n elements into exactly k non-empty subsets. The order of subsets does not matter, but the elements within each subset are grouped together.
Example: For n=4, k=2, we partition {1,2,3,4} into 2 subsets. One partition is {1} and {2,3,4}. There are S(4,2) = 7 such partitions.
S(n, k) = k · S(n-1, k) + S(n-1, k-1)
Stirling Numbers of the First Kind - c(n, k)
c(n, k) (unsigned) counts the number of permutations of n elements with exactly k cycles. A cycle in a permutation is a subset of elements that map to each other in a circular fashion.
Example: The permutation (1 3)(2 4) of {1,2,3,4} has 2 cycles: 1→3→1 and 2→4→2. There are c(4,2) = 11 permutations of 4 elements with exactly 2 cycles.
c(n, k) = (n-1) · c(n-1, k) + c(n-1, k-1)
Reference Values
Second Kind S(n,k):
- S(4, 2) = 7
- S(5, 2) = 15
- S(5, 3) = 25
- S(6, 3) = 90
- S(10, 5) = 42,525
First Kind c(n,k):
- c(4, 2) = 11
- c(5, 2) = 50
- c(5, 3) = 35
- c(6, 3) = 225
- c(10, 5) = 269,325
Relationship to Other Numbers
- Sum of S(n, k) over all k equals the Bell number B(n)
- Sum of c(n, k) over all k equals n! (factorial)
- S(n, 2) = 2^(n-1) - 1
- c(n, 1) = (n-1)! (derangement-related)
Applications: Combinatorics, probability theory, polynomial interpolation, analysis of algorithms, and statistical mechanics.
What is the difference between Stirling numbers of the first and second kind?
Stirling numbers of the second kind S(n,k) count ways to partition n elements into k non-empty subsets (groupings where order doesn't matter). Stirling numbers of the first kind c(n,k) count permutations of n elements with exactly k cycles. Despite similar recurrence relations, they count fundamentally different structures.
How do Stirling numbers relate to Bell numbers?
Bell numbers B(n) count the total number of ways to partition a set of n elements. They equal the sum of all Stirling numbers of the second kind: B(n) = S(n,0) + S(n,1) + ... + S(n,n). For example, B(4) = 15 because S(4,1) + S(4,2) + S(4,3) + S(4,4) = 1 + 7 + 6 + 1 = 15.
Why are Stirling numbers of the first kind called 'unsigned'?
The signed Stirling numbers of the first kind alternate in sign: s(n,k) = (-1)^(n-k) * c(n,k). These signed versions appear naturally in expanding falling factorials as polynomials. The unsigned version c(n,k) is more intuitive for counting permutations by cycles and is what this calculator computes.
Where are Stirling numbers used in practice?
Stirling numbers appear in probability theory (occupancy problems), combinatorics (set partitions), calculus (converting between ordinary and falling factorial powers), and computer science (analyzing algorithms like hashing). S(n,k) specifically counts surjective functions from an n-set to a k-set, divided by k!.