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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.