The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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


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.


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 

   Bell Number Diagrams   

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

   Bell Numbers   

   Stirling Numbers (both kinds)   

   Stirling Numbers of the First Kind   

   Stirling Numbers of the Second Kind   

If you still have questions, please write back.

- Doctor Jeremiah, The Math Forum   

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

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

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

We define B(0) = 1.

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


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   
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.