Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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?

Several of your articles were helpful, including 

   Calculating Number of Possible Subsets of a Set

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 

 [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

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

- Doctor Anthony, The Math Forum

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


to look for the words

   Stirling second kind

and you'll find entries like

   Stirling Numbers of the Second Kind, Bernoulli Numbers

   Stirling Numbers

or search for the words

   Bell number

and you'll find some more good examples like

   Bell Numbers Formula

   Bell Number

   Bell Numbers

I also found a huge set of references starting at


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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994-2015 The Math Forum