Stirling numbers (2nd kind)

O(n²)

The Stirling numbers of the second kind form a triangle where S(0,0)=1, S(n,0)=0 for n>0, S(n,n)=1 (only one way to put n items into n singletons), and the recurrence S(n,k) = k·S(n-1,k) + S(n-1,k-1). The k·S(n-1,k) term counts putting the new element into one of the k existing blocks; S(n-1,k-1) counts forming a new singleton block. The row sums are the Bell numbers.

Number triangle
Press ▶ to run
Edit the input and press Play

How it works

  1. Seed S(0,0) = 1; all S(n,0) = 0 for n > 0
  2. Diagonal S(n,n) = 1 for all n
  3. Interior: S(n,k) = k·S(n-1,k) + S(n-1,k-1)
  4. Row sums give the Bell numbers

Pseudocode

1stirling2(n):                       # O(n²)2  rows = []3  for r in 0..n-1:4    rows[r] = array of r+1 nulls5    rows[r][0] = (r == 0) ? 1 : 0  # S(0,0)=1; S(n,0)=06    rows[r][r] = 1                  # S(n,n)=17    for c in 1..r-1:8      rows[r][c] = c * rows[r-1][c] + rows[r-1][c-1]9  # row sums = Bell numbers