Associated Topics || Dr. Math Home || Search Dr. Math

### 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?

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.

these really cool numbers!

- Doctor Schwa, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search