Permutations and Combinations

Patrick McAtee, Tom Rice, and Jesse Whidden

Indistinguishable Objects and Objects in Boxes

Initially, it seems that the concepts of "permutations of sets with indistinguishable objects" and "distributing objects into boxes" aren't similar at all.

However, due to the metaphysical funkiness of discrete mathematics, we'll see that the formulas for each of these cases are identical!! In this part of the tutorial, we'll work out an example of each type to derive the formulas and then try to figure out why they're exactly the same.


Indistinguishable Objects

To pose a riddle, how many different strings can be made from the word 'connundrum'?

Permutations will still be used to solve this question. However, there are some letters we don't want to count more than once. For example, the letter n is used three times but we can't tell the difference between each one. As far as we're concerned, the first n, the second n, and the third n all look like "n" when the order of the letters is changed.

The first step in solving a problem like this is to identify all the unique items there are. For 'connundrum', thare are a total of 7 unique objects and 10 total spaces for all the objects:

  • (1) c
  • (1) o
  • (3) n
  • (2) u
  • (1) d
  • (1) r
  • (1) m

Additionally, let's remove all the letters from 'connundrum,' so that there are only the empty spot where the letters can go:

_ _ _ _ _ _ _ _ _ _

Now, let's place the letters back in the empty slots. First, there's one 'c' which can be put in any of ten spots. Next, the 'o' can be placed among the remaining nine locations. Here is gets interesting: we have 3 'n's which can be put into any of the eight open blanks. Additionally, the 2 'u's can be placed in any of the 5 remaining, open slots. The problem is finished in the same manner.

The expression described above can be written as follows:

C(10,1)C(9,1)C(8,3)C(5,2)C(3,1)C(2,1)C(1,1)

= 10!

9!1!
* 9!

8!1!
* 8!

5!3!
* 5!

3!2!
* 3!

2!1!
* 2!

1!1!
* 1!

1!0!

= 10!

3!2!1!1!1!

= 302,400

Theorem

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 is

= n!

n1! n2! ··· nk!


Objects in Boxes

A similar type of problem occurs when we want to determine how many ways we can put distinguishable objects into distinguishable boxes. This simply means that we can tell the difference between each item that we have and it matters where each item goes.

For example, pretend you're playing 5-card stud poker with three of your friends. Aces are high, stakes are low, the pretzel bowl is empty, and you're waiting for your buddy to finish shuffling the deck. As he starts to deal, you wonder how many different ways there are to deal the hands. That is,

How many ways are there to distribute hands of 5 cards to each of four players from the standard deck of 52 cards?

Initially there are 52 total cards, and 5 of those will be dealt to the first player. Thus, there are C(52, 5) possibilites for the first person. Next, player two will be dealt 5 cards from a total of 47. The number of possibilites for that individual event is C(47, 5). Similarly, there are C(42, 5) possibilities for the third person, and C(37, 5) for the fourth player. Therefore, the total number of possibilities is

C(52,5)C(47,5)C(42,5)C(37,5)

= 52!

47!5!
* 47!

42!5!
* 42!

37!5!
* 37!

32!5!

= 52!

5!5!5!5!32!

= 1.478 x 1024

Theorem
The number of ways to put n distinguishable objects into k distinguishable boxes, where ni is the number of distinguishable objects in box i (i = 1, 2, ..., k) equals

= n!

n1! n2! ··· nk!

(In the poker game, it is important to note that there are actually five boxes - the four players' hands and the deck. So, the first four boxes - the players' hands - each have 5 items; the fifth box - the deck - has 32 items.)


Conclusion

As you can see, these two types of problems are very similar and their formulas are identical. This is possible once you think of the cards as indistinguishable objects, and the boxes are indistinguishable types. Once we do this, we can apply the conditions of the first example to our card problem.