Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Bell Numbers


Date: 08/29/2001 at 02:16:52
From: Ben
Subject: Combination to split a group

Hi,

I am looking for the formula for the number of different groups we can 
split a group of n different items into - order does not matter. 

E.g. to split a,b there are 2 possibilities: a alone b alone, and a+b 
in the same group.

To split 3 items a,b,c there are 5 possibilities: a alone b alone c 
alone, a+b while c alone, a+c while b alone, b+c while a alone, and 
all three a+b+c.

Hope the question is clear.
Regards and thanks.
Ben


Date: 08/29/2001 at 10:45:18
From: Doctor Rob
Subject: Re: Combination to split a group

Thanks for writing to Ask Dr. Math, Ben.

These numbers are famous, and even have a name.  They are called the
Bell Numbers.  They begin

   1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597,
   27644437, 190899322, 1382958545, 10480142147, 82864869804,
   682076806159, 5832742205057, 51724158235372, 474869816156751,
   4506715738447323, ...

One remarkable formula for the Bell Numbers b(n) is

                infinity
   b(n) = (1/e)*  SUM   r^n/r!,  n >= 1.
                  r=1

This does not lend itself to computation, however.  Better is to know
that the exponential generating function B(x) for the Bell Numbers is

                      infinity
   B(x) = e^(e^x-1) =   SUM   b(n)*x^n/n!,
                        n=0

so b(n) is the nth derivative of e^(e^x-1) evaluated at x = 0.

Even better for computation is the following recurrence relation:

   b(0) = 1,

             n
   b(n+1) = SUM C(n,k)*b(k),  n >= 0,
            k=0

where C(n,k) = n!/(k!*[n-k]!) are the binomial coefficients.

These are very complicated numbers, so the above formulas are not
very simple.  Sorry, but that's just the way it is.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/   
    
Associated Topics:
College Discrete Math
High School Discrete Mathematics
High School Permutations and Combinations

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-2013 The Math Forum
http://mathforum.org/dr.math/