Bell Numbers FormulaDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/