Guichard-Combinatorics-Graph-Theory · Problem 1.4.4

Fundamentals

Mathematics — Probability · stirling-numbers

Problem

Another way to express the Bell numbers for

n > 0

B_n = \sum_{k=1}^{n} S(n,k),

where

S(n,k)

is the number of partitions of

\{1,2,\ldots,n\}

into exactly

k

parts,

1 \leq k \leq n

. The

S(n,k)

are the Stirling numbers of the second kind. Find a recurrence relation for

S(n,k)

. Your recurrence should allow a fairly simple triangle construction containing the values

S(n,k)

, and then the Bell numbers may be computed by summing the rows of this triangle. Show the first five rows of the triangle,

n \in \{1,2,\ldots,5\}