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/