Partitioning Sets into All Possible Subsets

Date: 05/19/2003 at 18:09:38
From: Jeff
Subject: Partitioning sets into all possible subsets

I am trying to determine how to partition a set into all possible 
subsets, using all items in the set in each combination of subsets.

In other words, if I have 3 items (apple, orange, banana) and 3 boxes, 
how many ways can I arrange the 3 items in the boxes, using all 3 
items each time? How about with 10 items and 10 boxes?

Several of your articles were helpful, including 

   Calculating Number of Possible Subsets of a Set
   http://mathforum.org/library/drmath/view/60881.html  

but did not get me all the way there.

Date: 05/19/2003 at 18:24:57
From: Doctor Anthony
Subject: Re: Partitioning sets into all possible subsets

To reduce the labour let us look at the number of ways that 10 
distinct objects can be distributed in 4 distinct boxes.

The number of ways that the 10 objects could be distributed is 
modelled as the number of different ways of placing 10 numbered balls 
into 4 numbered boxes. This is denoted by T(10,4).

T(10,4) is given by the coefficient of x^10/10! in the expansion of 
the generating function  [e^x - 1]^4

 [e^x - 1]^4 = [x + x^2/2! + x^3/3! + ..]^4  

If the 4 balls are represented by the letters A, B, C and D the -1 
ensures that we MUST have an A, B, C and D somewhere in each 
arrangement.

 [e^x-1]^4 = e^(4x) - 4e^(3x) + 6e^(2x) - 4e^x + 1

from which we pick out term in x^10.

= (4x)^10/10! - 4.(3x)^10/10! + 6.(2x)^10/10! - 4.x^10/10!

 = [4^10 - 4.(3^10) + 6.(2^10) - 4].(x^10/10!)

and the term in square brackets is the coefficient of x^10/10!

So  T(10,4) = [4^10 - 4.(3^10) + 6.(2^10) - 4]  =  818520

which corresponds to the formula

           m
 T(n,m) = SUM[(-1)^k.C(m,k).(m-k)^n]   with n=10 and m=4
          k=0

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 05/19/2003 at 18:39:49
From: Doctor Schwa
Subject: Re: Partitioning sets into all possible subsets

Hi Jeff,

I think what you're dealing with here is called "Stirling numbers of 
the second kind", or more precisely, the part(n,k) is usually called 
S2(n,k) and the sum of all of them, which I think is what you really 
want, is called B(n) or the nth Bell number.

You can find more about them by searching the Dr. Math archives using 
the Dr. Math searcher at

   http://mathforum.org/library/drmath/mathgrepform.html 

to look for the words

   Stirling second kind

and you'll find entries like

   Stirling Numbers of the Second Kind, Bernoulli Numbers
   http://mathforum.org/library/drmath/view/51610.html 

   Stirling Numbers
   http://mathforum.org/library/drmath/view/51550.html 

or search for the words

   Bell number

and you'll find some more good examples like

   Bell Numbers Formula
   http://mathforum.org/library/drmath/view/52206.html 

   Bell Number
   http://mathforum.org/library/drmath/view/56244.html 

   Bell Numbers
   http://mathforum.org/library/drmath/view/52270.html 

I also found a huge set of references starting at

   http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/
eisA.cgi?Anum=A000110

in the Encyclopedia of Integer Sequences.

Let me know if you would like even more information about
these really cool numbers!

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/