Thread: bell numbers

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

Is there a combinatorial interpretation of this?

Originally Posted by Sampras

So the bell numbers satisfy the following recurrence: $\displaystyle b(n) = \sum_{k} \binom{n-1}{k} b(k) $, $\displaystyle n \geq 1 $, $\displaystyle b(0) = 1 $.
Is there a combinatorial interpretation of this?

In point of fact, the Bell numbers are given by $\displaystyle B(n) = \sum\limits_{k = 0}^n {S_2 (n,k)} $ .
Now $\displaystyle {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: $\displaystyle {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.

Originally Posted by Plato

In point of fact, the Bell numbers are given by $\displaystyle B(n) = \sum\limits_{k = 0}^n {S_2 (n,k)} $ .
Now $\displaystyle {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: $\displaystyle {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?

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.