Bell Number

Date: 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/