Recurrence Relation for Bell Numbers/Illustration

Illustration of Recurrence Relation for Bell Numbers

We have:

$B_{n + 1} = \ds \sum_{k \mathop = 0}^n \dbinom n k B_k$

Let $n = 3$.

Then:

\(\ds B_4\)

\(=\)

\(\ds \sum_{k \mathop = 0}^3 \dbinom 3 k B_k\)

\(\ds \)

\(=\)

\(\ds B_0 + 3 B_1 + 3 B_2 + B_3\)

\(\text {(1)}: \quad\)

\(\ds \)

\(=\)

\(\ds 1 + 3 + 6 + 5\)

Let $S = \set {a, b, c, d}$.

The $1$ in $(1)$ represents all of the elements combined ($B_0 = 1$):

$\set {a, b, c, d}$

The $3$ in $(1)$ represents the sets where element $d$ is part of a triplet ($3 B_1 = 3$):

$\set {\set a \set {b, c, d} }$

$\set {\set b \set {a, c, d} }$

$\set {\set c \set {a, b, d} }$

The $6$ in $(1)$ represents the sets where element $d$ is part of a couple ($3 B_2 = 6$):

$\set {\set {a, d} \set {b, c} }$

$\set {\set {a, d} \set b \set c}$

$\set {\set {b, d} \set {a, c} }$

$\set {\set {b, d} \set a \set c}$

$\set {\set {c, d} \set {a, b} }$

$\set {\set {c, d} \set a \set b}$

Finally, the $5$ in $(1)$ represents where element $d$ is by itself and the remaining $3$ elements are partitioned ($B_3 = 5$):

$\set {\set d, \set {a, b, c} }$

$\set {\set d, \set a, \set {b, c} }$

$\set {\set d, \set b, \set {a, c} }$

$\set {\set d, \set c, \set {a, b} }$

$\set {\set d, \set a, \set b, \set c}$