bell numbers

**Sampras** · September 28th 2009, 07:51 AM

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?

**Plato** · September 28th 2009, 08:20 AM

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.

**Sampras** · September 28th 2009, 09:32 AM

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?

**Plato** · September 28th 2009, 09:50 AM

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.

Math Help - bell numbers

LinkBack

Thread Tools

Display

bell numbers

Similar Math Help Forum Discussions

Bell Curves

Bell numbers

Equation for bell-shaped curve

bell curve

Alexander Graham Bell Problem

Search Tags