Stirling Number Calculator (Second Kind)

Stirling numbers of the second kind, written S(n,k) or {n choose k} in curly braces, count the number of ways to partition a set of n distinct elements into exactly k non-empty, non-ordered subsets. For example, S(4,2) = 7 because a 4-element set can be split into exactly 2 non-empty subsets in 7 ways.

The Stirling numbers of the second kind satisfy 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 factor k comes from placing element n into one of the existing k subsets; the term S(n-1,k-1) comes from starting a new subset containing only element n.

Stirling numbers of the second kind S(n,k) count set partitions into k non-empty subsets. Stirling numbers of the first kind s(n,k) count permutations of n elements with exactly k disjoint cycles. This calculator computes only the second kind.

S(n,1) = 1 for all n greater than 0 (only one way to put everything in one subset). S(n,n) = 1 for all n (only one way to put each element in its own subset). S(n,2) = 2^(n-1) - 1. S(n,n-1) = n*(n-1)/2 (choose which two elements share a subset).

The sum of S(n,k) for k from 0 to n equals the nth Bell number B(n), which counts all partitions of an n-element set. Also, x^n = sum of S(n,k) * x(x-1)(x-2)...(x-k+1) for k from 0 to n, expressing powers of x as falling factorial polynomials.