∑

Stirling Numbers Calculator

First Kind · Second Kind · Bell Numbers · Triangular Tables

Compute S(n,k) (set partitions), s(n,k) (permutation cycles), and B(n) (Bell numbers) with full recurrence steps and triangular tables.

Quick Examples

n (total elements)

k (subsets / cycles)

S(n,k) — 2nd Kind

—

Set partitions into k non-empty subsets

s(n,k) — 1st Kind

—

Permutations with exactly k cycles

Bell B(n)

—

Total partitions of n-element set

Recurrence Relations Used

2nd Kind
S(n,k) = k·S(n-1,k) + S(n-1,k-1)
S(0,0)=1 S(n,0)=0 S(0,k)=0

1st Kind
s(n,k) = (n-1)·s(n-1,k) + s(n-1,k-1)
s(0,0)=1 s(n,0)=0 s(0,k)=0

2nd KindStep-by-Step Recurrence for S(n,k)

n \ k	k cols

1st KindStep-by-Step Recurrence for s(n,k)

n \ k	k cols

Max n (0–20)

B(0)

Empty set has 1 partition

B(5)

Partitions of 5-element set

B(10)

115975

Partitions of 10-element set

B(15)

1382958545

Partitions of 15-element set

BellBell Numbers B(0) through B(n)

n	B(n)	= Sum S(n,k)	Meaning

Bell Triangle (Aitken's Array)

Each row starts with the last element of the previous row. Each subsequent element is the sum of the element to its left and the element directly above that left element. The first element of each row is a Bell number.

Bell Number Formulas

B(n) = ∑_k=0ⁿ S(n,k) (sum over 2nd kind)
B(n+1) = ∑_k=0ⁿ C(n,k) · B(k) (recurrence via binomial)
B(0)=1, B(1)=1, B(2)=2, B(3)=5, B(4)=15, B(5)=52, B(6)=203

What Are Stirling Numbers?

Stirling numbers are two families of integers introduced by the Scottish mathematician James Stirling (1692–1770) in his 1730 work Methodus Differentialis. They arise naturally in combinatorics, probability, and analysis, and appear in formulas connecting ordinary powers to falling factorials and vice versa. Today, Stirling numbers are fundamental objects in enumerative combinatorics and appear in the study of permutations, set partitions, generating functions, and probability distributions.

Stirling Numbers of the Second Kind — S(n, k)

The Stirling number of the second kind S(n, k) (also written {n choose k} with curly braces, or sometimes denoted S(n,k)) counts the number of ways to partition a set of n distinct elements into k non-empty, unordered subsets. These subsets are unordered, meaning the partition {1,2},{3,4} is the same as {3,4},{1,2}.

The key recurrence is:

S(n,k) = k · S(n-1,k) + S(n-1,k-1)

The combinatorial proof: given the n-th element, it either joins one of the k existing blocks (k choices — hence k·S(n-1,k)) or forms its own new singleton block (S(n-1,k-1)). Base cases are S(0,0)=1 and S(n,0)=S(0,k)=0 for n,k > 0.

Small Values of S(n,k)

n \ k	0	1	2	3	4	5
0	1	0	0	0	0	0
1	0	1	0	0	0	0
2	0	1	1	0	0	0
3	0	1	3	1	0	0
4	0	1	7	6	1	0
5	0	1	15	25	10	1

Stirling Numbers of the First Kind — s(n, k)

The unsigned Stirling number of the first kind s(n, k) counts the number of permutations of n elements that have exactly k disjoint cycles. For example, the permutation (1 2 3)(4 5) of {1,2,3,4,5} has 2 cycles, so it is counted in s(5,2).

The recurrence is:

s(n,k) = (n-1) · s(n-1,k) + s(n-1,k-1)

Here, the n-th element either extends one of the (n-1) existing elements in a cycle by inserting itself after it ((n-1)·s(n-1,k) ways), or forms its own new 1-cycle (s(n-1,k-1) ways). The signed Stirling numbers of the first kind are ⌊n k⌋ = (-1)^(n-k) · s(n,k) and appear in the expansion of falling factorials.

Bell Numbers — B(n)

Bell numbers B(n) count the total number of partitions of an n-element set, summing across all possible numbers of blocks:

B(n) = S(n,0) + S(n,1) + ··· + S(n,n)

Bell numbers grow super-exponentially. The sequence begins: B(0)=1, B(1)=1, B(2)=2, B(3)=5, B(4)=15, B(5)=52, B(6)=203, B(7)=877, B(8)=4140, B(9)=21147, B(10)=115975. They satisfy the recurrence B(n+1) = ∑_k=0ⁿ C(n,k)·B(k).

Connections to Falling Factorials and Binomial Coefficients

One of the most elegant relationships in combinatorics is the connection between ordinary powers and falling factorials via Stirling numbers:

2nd kind: xⁿ = ∑_k=0ⁿ S(n,k) · x^(k), where x^(k) = x(x-1)···(x-k+1) is the falling factorial.
1st kind: x⁽ⁿ⁾ = ∑_k=0ⁿ s(n,k) · x^k (unsigned, with appropriate signs for the signed version).
S(n,k) relates to binomial coefficients via: S(n,k) = (1/k!) ∑_j=0^k (-1)^k-j C(k,j) jⁿ.

Applications in Probability and Combinatorics

Set Partitions: S(n,k) directly counts the number of ways to cluster n objects into k groups — a problem appearing in machine learning, chemistry (molecular bond configurations), and database theory.
Moments and Cumulants: The moments of a Poisson distribution with parameter λ are expressed via Bell polynomials built from Stirling numbers.
Occupancy Problems: The probability that n randomly thrown balls fill exactly k of m urns involves S(n,k) in its formula.
Permutation Statistics: s(n,k) counts permutations by cycle structure, directly relevant to random permutation theory and card shuffle analysis.
Generating Functions: The ordinary generating function for S(n,k) in n is x^k/((1-x)(1-2x)···(1-kx)). Bell numbers have the exponential generating function e^(e^x - 1).

James Stirling — Historical Background

James Stirling was born in Garden, Stirlingshire, Scotland in 1692. He studied at Oxford and later worked in Venice before returning to Scotland. His masterwork Methodus Differentialis (1730) systematically studied differences and series of factorial form, where the Stirling numbers first appeared explicitly. Stirling is also famous for Stirling's approximation: n! ≈ √(2πn) · (n/e)ⁿ, which provides an accurate estimate of factorial growth and is used throughout probability, statistical mechanics, and information theory.

Frequently Asked Questions

What are Stirling numbers of the second kind?

S(n,k) counts the number of ways to partition a set of n distinct elements into exactly k non-empty, unordered subsets. The recurrence S(n,k) = k·S(n-1,k) + S(n-1,k-1) has a simple interpretation: element n either joins one of the k existing blocks or starts a new singleton block.

What are Stirling numbers of the first kind?

The unsigned Stirling number of the first kind s(n,k) counts permutations of n elements having exactly k cycles. The recurrence s(n,k) = (n-1)·s(n-1,k) + s(n-1,k-1) comes from inserting element n either into an existing cycle at one of (n-1) positions or as a new 1-cycle.

What are Bell numbers?

B(n) is the total number of partitions of an n-element set, regardless of how many blocks. It equals the row sum of the Stirling triangle: B(n) = S(n,0)+S(n,1)+···+S(n,n). The sequence grows rapidly: 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, ...

What is the combinatorial interpretation of S(n,k)?

S(n,k) counts set partitions of {1,2,...,n} into k non-empty blocks. For example, S(3,2)=3 because {1,2},{3} and {1,3},{2} and {1},{2,3} are the three ways to split {1,2,3} into 2 blocks. The blocks are unordered sets with no ordering between them.

How are Stirling numbers related to falling factorials?

Stirling numbers of the 2nd kind express ordinary powers as sums of falling factorials: x^n = ∑S(n,k)·x^(k). Conversely, unsigned Stirling numbers of the 1st kind express falling factorials as ordinary polynomials: x^(n) = x(x-1)···(x-n+1) = ∑s(n,k)·x^k. These are inverse transforms of each other.

What is the difference between signed and unsigned Stirling numbers of the first kind?

Unsigned Stirling numbers of the first kind c(n,k) are always non-negative and count permutations by cycle count. Signed Stirling numbers of the first kind are ⌊n k⌋ = (-1)^(n-k)·c(n,k). The signed version appears in the expansion x(x-1)···(x-n+1) = ∑⌊n k⌋ x^k. This calculator computes the unsigned version.

What is James Stirling's contribution to combinatorics?

James Stirling (1692–1770) introduced these numbers in his 1730 work Methodus Differentialis while studying interpolation and difference series. He is also famous for Stirling's approximation n! ≈ √(2πn)·(n/e)^n, which describes the growth rate of factorials. His work bridged analysis and combinatorics in ways that remain influential today.