Bell NumberDate: 02/24/2002 at 16:37:12 From: William Subject: Bell Number I am trying to figure out how many different groups 50 people can be partitioned into. Please reply with help. Thanks, Will Date: 02/24/2002 at 17:36:43 From: Doctor Anthony Subject: Re: Bell Number 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 Note that these treat the individuals as distinct and the total will be astronomically large. I suspect that you wish to know how many ways we can partition 50 people without treating them as distinct. The number of partitions of 50 is the coefficient of 50 in the expansion of 1 ------------------------------- (1-x)(1-x^2(1-x^3)......(1-x^50) With a maths package this can be obtained, but in practice you need a recurrence relation. The recursion formula for p(n), the TOTAL number of partitions of n is given by p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - p(n-22) -.. Note that the signs follow the pattern ++ -- ++ -- ++ -- and so on. The numbers 1, 2, 5, 7, 12, 15, 22, 26, .... inside the brackets are of the form (m/2)(3m-1) and (m/2)(3m+1) It is useful to have a table showing how these values go. m 1 2 3 4 5 6 7 8 ------------------------------------------------------------------- (m/2)(3m-1) 1 5 12 22 35 51 70 92 (m/2)(3m+1) 2 7 15 26 40 57 77 100 Take p(0) = 1 and p(1) = 1 p(2) = p(1) + p(0) = 2 p(3) = p(2) + p(1) = 3 p(4) = p(3) + p(2) = 5 p(5) = p(4) + p(3) - p(0) = 3+5-1 = 7 p(6) = p(5) + p(4) - p(1) = 7+5-1 = 11 p(7) = p(6) + p(5) - p(2) - p(0) = 11+7-2-1 = 15 p(8) = p(7) + p(6) - p(3) - p(1) = 15+11-3-1 = 22 and so on. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ Date: 02/24/2002 at 21:22:12 From: William Subject: Bell Number My question is, if you have 50 people how many different ways can you partition those people off. I have worked the formulas and keep getting a couple of different answers. It would be very beneficial to me if you could e-mail me the correct answer. None of my peers has knowledge of how to calculate a Bell number, so your help would be greatly appreciated. Thanks, Will Date: 02/24/2002 at 22:45:40 From: Doctor Paul Subject: Re: Bell number the 50th bell number is: 185724268771078270438257767181908917499221852770 I hope this helps. Please write back if you'd like to talk about this more. - Doctor Paul, 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/