Associated Topics || Dr. Math Home || Search Dr. Math

### Bell Numbers Formula

```
Date: 02/13/2001 at 14:55:10
From: Tanya
Subject: Formula for Bell Numbers

Hi,

I have a question about the Bell numbers formula:

B(n) = (n-1 0)B(0) + (n-1 1)B(1) + ... + (n-1 n-1)B(n-1)

We have covered this material partially in my class, but since I am
majoring in math I wanted to understand why and how this formula was
derived. I have tried to derive the formula from the Stirling numbers
formula but without success. I would appreciate if you could help.

Thank you.

Sincerely,
Tanya
```

```
Date: 02/13/2001 at 16:32:20
From: Doctor Jeremiah
Subject: Re: Formula for Bell Numbers

Hi Tanya,

I can't explain how to prove that Bell Numbers can be derived from
Stirling Numbers of the Second Kind. But this page does give a
relationship:

Bell Number Diagrams
http://www-history.mcs.st-and.ac.uk/history/Miscellaneous/StirlingBell/bell.html

Take a look and see if that helps.
Here are a couple other pages that may help:

Bell Numbers
http://www.mathforum.org/dr.math/problems/leonardi10.15.98.html

Stirling Numbers (both kinds)
http://www.mathforum.org/dr.math/problems/john05.26.99.html

Stirling Numbers of the First Kind
http://www-history.mcs.st-and.ac.uk/history/Miscellaneous/StirlingBell/stirling1.html

Stirling Numbers of the Second Kind
http://www-history.mcs.st-and.ac.uk/history/Miscellaneous/StirlingBell/stirling2.html

If you still have questions, please write back.

- Doctor Jeremiah, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 02/14/2001 at 07:49:54
From: Doctor Anthony
Subject: Re: Formula for Bell Numbers

Stirling numbers of the second kind give the number of ways of
distributing n distinct objects into m identical cells with no empty
cells, and Bell numbers are the number of ways of distributing the
objects into 1, 2, 3,.....n cells. It follows that

n
B(n) = SUM[S(n,m)]
m=1

If we start at the simplest situation we can build up the recurrence
relation.

We define B(0) = 1.

Say we have one cell and one object, a. Then we have the following
distribution of objects in cells.

(a)

Clearly B(1) = 1.

If we add a second object (call it b) and a second cell, we have the
following possible distributions

(a b) + (ab 0)

B(2) = C(1,0)B(0) + C(1,1)B(1) = 2

= Put 1 object + Add b to a in
in each cell   each cell in B(1)

If we add a third object, c, and increase the number of cells to 3,
we have the following possibilities

[(a b c)] + [(ab c 0) + (ac b 0)] + [(a bc 0) + (abc 0 0)]

B(3) = C(2,0)B(0) + C(2,1)B(1) + C(2,2)B(2) = 5

= Put 1 object + Add b and c to a  + Add c to b in
in each cell   each cell in B(1)   each cell in B(2)

Continuing in this fashion we obtain the recurrence relation:

B(n)= C(n-1,0)B(0) + C(n-1,1)B(1) +
C(n-1,2)B(2) + ... + C(n-1,n-1)B(n-1)

- Doctor Anthony, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Probability
College Statistics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search