# Math Help - bell numbers

1. ## bell numbers

So the bell numbers satisfy the following recurrence: $b(n) = \sum_{k} \binom{n-1}{k} b(k)$, $n \geq 1$, $b(0) = 1$.

Is there a combinatorial interpretation of this?

2. Originally Posted by Sampras
So the bell numbers satisfy the following recurrence: $b(n) = \sum_{k} \binom{n-1}{k} b(k)$, $n \geq 1$, $b(0) = 1$.
Is there a combinatorial interpretation of this?
In point of fact, the Bell numbers are given by $B(n) = \sum\limits_{k = 0}^n {S_2 (n,k)}$ .
Now ${S_2 (n,k)}$ are the Stirling numbers of the second kind.
That is the number of ways to partition a set of n elements into k nonempty subsets.
To calculate: ${S_2 (n,k)}= \frac{1}{{k!}}\left[ {\sum\limits_{k = 0}^n {\left( { - 1} \right)^j \binom{k}{j}\left( {k - j} \right)^n } } \right]$.

So the Bell numbers count the total number of ways to partition a set.

3. Originally Posted by Plato
In point of fact, the Bell numbers are given by $B(n) = \sum\limits_{k = 0}^n {S_2 (n,k)}$ .
Now ${S_2 (n,k)}$ are the Stirling numbers of the second kind.
That is the number of ways to partition a set of n elements into k nonempty subsets.
To calculate: ${S_2 (n,k)}= \frac{1}{{k!}}\left[ {\sum\limits_{k = 0}^n {\left( { - 1} \right)^j \binom{k}{j}\left( {k - j} \right)^n } } \right]$.

So the Bell numbers count the total number of ways to partition a set.
Yes but that is the generating function combinatorial interpretation. But can we also interpret the recurrence relation solely? In other words can generating function combinatorial interpretations be interpreted in combinatorially in recurrence form?

4. Originally Posted by Sampras
Yes but that is the generating function combinatorial interpretation. But can we also interpret the recurrence relation solely? In other words can generating function combinatorial interpretations be interpreted in combinatorially in recurrence form?
I posted an attached PDF file in this thread.
That may be what you are asking.