Combinations of Objects in Boxes

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, M₁I₁S₁S₂I₂S₃S₄I₃P₁P₂I₄, 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, M₁I₁SSI₂SSI₃P₁P₂I₄, 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.

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 n₁ the number of indistinguishable objects of type 1, n₂ indistinguishable objects of type 2, ... and n_k the number of indistinguishable objects of type k, then the number of different permutations of these objects is

n! / (n₁! n₂! ... n_k!)

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

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 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 n₁ objects go in the first box, n₂ in the second, ... and n_k go in the k^th box is:

n! / (n₁! n₂! ... n_k!)

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:

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)

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

Another fascinating recurrence relation is this:

Let part(0)=1

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

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 n^th ball into a new box or else you can start with any of the B(n-1,k) combinations, and put the n^th 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).

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

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 n^th "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 is the number of partitions of n.
Sloan's A000110 is the n^th "Bell Number".

Xingde Jia, Lecture Notes: Chapter 6: Basic Counting Principles and Chapter 6: Basic Counting Principles 

Related Pages in this Website

Go back to Counting 

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]