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