Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Counting > Objects In Boxes

Combinations of Objects in Boxes

Introduction

To count the number of ways to place objects in boxes, we need to be very clear regarding our ability to distinguish among the objects and among the boxes.  If two objects are indistinguishable, then interchanging them doesn't result in a new way of placing the objects in boxes.  Similarly, if two boxes are indistinguishable, then moving all the objects from one box to another box doesn't result in a new way of placing the objects in boxes.  So we need to consider all the cases of whether the objects and whether the boxes are distinguishable.

Sometimes boxes are called "urns"

Sometimes "distinguishable" and "indistinguishable" are called "labeled" or "unlabeled"

When we speak of permutations of a string, we're really talking about putting objects in labeled boxes.  The boxes are the positions of the objects in the string.  For example, there are six permutations of the string ABC, which are ABC, ACB, BAC, BCA, CAB, and CBA.  The three boxes, here, are the place for the first letter, the place for the second letter, and the place for the third letter.  So permutations fall into the category of putting things (which may or may not be labeled) into labeled boxes, but with the restriction that exactly one object must be put into each box.

  labeled urns unlabeled urns
labeled objects Placing particular numbers (n1, n2, ..., nk) of labeled balls into labeled urns: n! / (n1! n2! ... nk!)

 

Placing n labeled balls into exactly k non-empty unlabeled urns: B(n,k) = B(n-1,k-1) + k B(n-1,k)
unlabeled objects MISSISSIPPI: Permutations of sets with some indistinguishable objects

Placing n unlabeled balls into k labeled boxes: C(n+k-1,k-1)

Placing n unlabeled balls into k unlabeled boxes:
Part(n,k) is the number of k-element partitions of n.

Permutations of sets with some indistinguishable objects 

Consider the word MISSISSIPPI.  It has 1 M, 4 I's, 2 P's, and 4 S's.

If each of the letters were distinct, say, M1I1S1S2I2S3S4I3P1P2I4, then there would be 11! ways to arrange them.  But if we couldn't tell the S's apart, then we would reduce the number of possible ways to arrange the new word, M1I1SSI2SSI3P1P2I4, by a factor of 4!, which is the number of different permutations of the S's, all other things being equal.  Similarly, if we couldn't tell the I's apart, we would reduce the number of permutations by another factor of 4!, and if we couldn't tell the P's apart, we would reduce the number by yet another factor of 2! this time.

So the number of distinct permutations of MISSISSIPPI is 11! / (4! 4! 2!)

There's another way to figure this out.  Imagine there were 11 spaces in which to write the letters that make up the word MISSISSIPPI.

  __     __     __     __     __     __     __     __     __     __     __  
1 2 3 4 5 6 7 8 9 10 11

To find the number of permutations, consider placing the letters into these 11 spaces.  There are C(11,1) ways to place the M.  Having placed it, there are C(10,4) ways to place the I's.  Having placed them, there are C(6,2) ways to place the P's, and then C(4,4) ways to place the S's.

So the number of distinct permutations of MISSISSIPPI is

C(11,1) C(10,4) C(6,2) C(4,4)

which can be written as

11!/(10! 1!)  10!/(6! 4!)  6!/(4! 2!)  4!/(4! 0!)

after canceling common factors, this becomes

11! / (1! 4! 2! 4!)

In general, if you have n total objects and k unique objects, call n1 the number of indistinguishable objects of type 1, n2 indistinguishable objects of type 2, ... and nk the number of indistinguishable objects of type k, then the number of different permutations of these objects is

n! / (n1! n2! ... nk!)

One more example, that might look different at first glance: Consider the word FACETIOUS.  How may ways can it be rearranged, leaving the vowels in order A,E,I,O,U?

The trick is to realize that this is the same as the number of ways to rearrange FACATAAAS, which is the same word except I use the letter "A" to represent every vowel.  The reason this is the same is that for any arrangement of the letters FACATAAAS, you can reconstruct the letters of FACETIOUS with the vowels in order -- just change the second "A" to "E", change the third "A" to "O", etc.

So the answer is 9! / 1! 1! 1! 1! 5!  =  9! / 5!  =  9*8*7*6  =  3024

Placing particular numbers of distinguishable objects (labeled balls) in distinguishable boxes (labeled urns).

That is, placing n1 objects into the first box, n2 objects into the second box, etc., and nk into the kth box.

Surprisingly, the problem of counting the ways to put particular numbers of n labeled balls in k labeled urns is the same as that of counting the ways to permute sets of n objects with k types of indistinguishable objects, with a particular number of each type of object.

I say surprisingly, because at first these appear to be different problems.  But if you think back to the MISSISSIPPI problem, and consider not permuting not the M's, I's, S's, and P's, but rather assigning the eleven letter positions to labeled urns, then the problem becomes "How many ways can the numbers 1 through 11 be placed in four urns such that one number be placed in urn 'M', 4 numbers be placed in urn 'I', 2 numbers be placed in urn 'P', and 4 numbers be placed in urn 'S'"?  For each way of permuting the letters in MISSISSIPPI, there is a corresponding way of assigning the given quantities of the 11 letter positions to the four urns.

So the formula for the number of ways to place n distinguishable objects into k distinguishable boxes, such that n1 objects go in the first box, n2 in the second, ... and nk go in the kth box is:

n! / (n1! n2! ... nk!)

Indistinguishable Objects to Distinguishable Boxes

The number of different ways to distribute n indistinguishable balls into k distinguishable boxes is C(n+k-1,k-1).

For example, 5 balls into 3 boxes can be done in these C(7,2) = 21 ways:

 Box 1  Box 2  Box 3 
 aaaaa     
 aaaa  a   
 aaaa    a 
 aaa  aa   
 aaa  a  a 
 aaa    aa 
 aa  aaa   
 aa  aa  a 
 aa  a  aa 
 aa    aaa 
 a  aaaa   
 a  aaa  a 
 a  aa  aa 
 a  a  aaa 
 a    aaaa 
   aaaaa   
   aaaa  a 
   aaa  aa 
   aa  aaa 
   a  aaaa 
     aaaaa 

The easiest way to understand this formula is to consider the permutations of the string XXaaaaa -- in each permutation, the 2 X's divide the a's into one of three boxes.  From the first section, on permutations of sets with some indistinguishable objects, we know that the number of distinct permutations of XXaaaaa is C(7,2).  In general, the number of permutations of a string of n a's and k-1 X's is C(n+k-1,k-1), and each of these permutations corresponds to one of the ways you can place n indistinguishable objects into k labeled boxes.

If you're told that the boxes can't be empty, then this is the same as putting one ball in each of k boxes first (that part is forced, so there's one way to do it), and then it's the number of ways to distribute n-k identical balls into k labeled boxes, or C(n-1,k-1)

Indistinguishable Objects to Indistinguishable Boxes

The number of different ways to distribute n indistinguishable balls into exactly k indistinguishable non-empty boxes is the number of k-element partitions of n.

For example, 7 can be partitioned into exactly 3 non-empty boxes these four ways:

1+1+5
1+2+4
1+3+3
2+2+3

The function, part, is defined this way.  Part(n,k) is the number of k-element partitions of n.  So part(7,3)=4.

A recurrence relation is

part(n,k) = part(n-1,k-1) + part(n-k,k)          (proof)

I define part(n) (Sloan's A000041) to be the sum from k=1 to n of part(n,k) (Sloan's A008284).

 n \ k  1  2  3  4  5  6  7  8  9  10  part(n) 
 0  1                    1 
 1  1                    1 
 2  1  1                  2 
 3  1  1  1                3 
 4  1  2  1  1              5 
 5  1  2  2  1  1            7 
 6  1  3  3  2  1  1          11 
 7  1  3  4  3  2  1  1        15 
 8  1  4  5  5  3  2  1  1      22 
 9  1  4  7  6  5  3  2  1  1    30 
 10  1  5  8  9  7  5  3  2  1  1  42 

Another fascinating recurrence relation is this:

Let part(0)=1

Stop the following process when the index of a term becomes less than zero.

part(n) = part(n-1) + part(n-2) (m=1)
-part(n-5) - part(n-7) (m=2)
+part(n-12) + part(n-15) (m=3)
- ................  
+- part(n-m(3m-1)/2) +- part(n-m(3m+1)/2) (m >= 1)

The last line is the general form for the pairs of terms.
When m is odd, add the two terms, and when m is even, subtract them.

For example:
part(10)= part(9) + part(8) - part(5) - part(3)
= 30 + 22 - 7 - 3 = 42

Distinguishable Objects to Indistinguishable Boxes

The number of different ways to distribute n labeled balls into exactly k indistinguishable non-empty boxes, which I will call B(n,k), is given by the recurrence relation,

B(n,k) = B(n-1,k-1) + k B(n-1,k)

The reason this recurrence relation works can be illustrated recursively.

B(1,1)=1 because there is just one way to put one labeled ball into one unlabeled box.

Now suppose you know the number of ways to put  n-1 labeled balls into k unlabeled boxes (and you also know the number of ways to put n-1 labeled balls into k-1 unlabeled boxes), and you want to add one more ball and use k boxes.  You can either start with any of the B(n-1,k-1) combinations, and put the nth ball into a new box or else you can start with any of the B(n-1,k) combinations, and put the nth ball into a non-empty box.

For each of the B(n-1,k-1) combinations, there is just one way to add the new ball to a new box.

For each of the B(n-1,k) combinations, there are k ways to add the new ball to a non-empty box.

Thus the number of combinations B(n,k) is the sum of B(n-1,k-1) and k times B(n-1,k).

B(n,k) are known as Stirling numbers of 2nd kind, sometimes S2(n,k) (Sloan's A008277)

This table shows the number of ways of putting n labeled balls in n bins that use k of the n bins.

 n \ k  1  2  3  4  5  6  7  8  9  10  Sum 
 1  1                    1 
 2  1  1                  2 
 3  1  3  1                5 
 4  1  7  6  1              15 
 5  1  15  25  10  1            52 
 6  1  31  90  65  15  1          203 
 7  1  63  301  350  140  21  1        877 
 8  1  127  966  1701  1050  266  28  1      4140 
 9  1  255  3025  7770  6951  2646  462  36  1    21147 
 10  1  511  9330  34105  42525  22827  5880  750  45  1  115975 

Table Showing Recurrence relation B(n,k) = B(n-1,k-1) + k B(n-1,k)

If you need to find the number of ways to put n labeled balls into k boxes, and the boxes can be empty, then just sum B(n,j), for j=1 to k.

By the way, the nth "Bell Number" is B(n,n), and this is Sloan's A000110.

Internet references

Partitioning Integers , from Bob's Positive Integer Pages (fascinating reading!)

Sloan's A000041: the number of partitions of n.
Sloan's A000110: the nth "Bell Number".
Sloan's A008277: Stirling numbers of 2nd kind, sometimes S2(n,k)
Sloan's A008284: part(n,k), the number of partitions of n into exactly k parts, and also (by conjugate partitions) the number of partitions of n whose largest part is k.

Related pages in this website

Partition Recurrence Relation -- calculating the number of k-element partitions of n using part(n,k) = part(n-1,k-1) + part(n-k,k).  Conjugate partitions.

"hyper-binary" partition

Combination identities

 

The webmaster and author of this Math Help site is Graeme McRae.