Distinguishable Permutations

Printer-friendly versionPrinter-friendly version

gold dollar coinExample

Suppose we toss a gold dollar coin 8 times. What is the probability that the sequence of 8 tosses yields 3 heads (H) and 5 tails (T)?

Solution. Two such sequences, for example, might look like this:

H H H T T T T T    or this    H T H T H T T T

Assuming the coin is fair, and thus that the outcomes of tossing either a head or tail are equally likely, we can use the classical approach to assigning the probability. The Multiplication Principle tells us that there are:

2 × 2 × 2 × 2 × 2 × 2 × 2 × 2

or 256 possible outcomes in the sample space of 8 tosses. (Can you imagine enumerating all 256 possible outcomes?) Now, when counting the number of sequences of 3 heads and 5 tosses, we need to recognize that we are dealing with arrangements or permutations of the letters, since order matters, but in this case not all of the objects are distinct. We can think of choosing (note that choice of word!) r = 3 positions for the heads (H) out of the n = 8 possible tosses. That would, of course, leave then nr = 8 − 3 = 5 positions for the tails (T). Using the formula for a combination of n objects taken r at a time, there are therefore:

\(\dbinom{8}{3}=\dfrac{8!}{3!5!}=56\)

distinguishable permutations of 3 heads (H) and 5 tails (T). The probability of tossing 3 heads (H) and 5 tails (T) is thus 56/256 = 0.22.

Let's formalize our work here!

Definition. Given n objects with:

  • r of one type, and
  • nr of another type

there are:

\(_nC_r=\binom{n}{r}=\dfrac{n!}{r!(n-r)!}\)

distinguishable permutations of the n objects.

Let's take a look at another example that involves counting distinguishable permutations of objects of two types.

Example

Suppose Dr. DoesBadThings conducts research which involves infecting 20 people with the swine flu virus. He is interested in studying how many actually end up ill (I) and how many remain healthy (H).

How many arrangements are there of the 20 people that involve 0 people ill?

Solution. In this case, we can readily determine that there is just 1 way. The sequence would look like this:

HHHHHHHHHHHHHHHHHHHH

Alternatively, we could use the formula for counting distinguishable permutations. The formula yields:

\(\dbinom{20}{0}=\dfrac{20!}{0!20!}=1\)

How many arrangements are there of the 20 people that involve 1 person ill?

Solution. I think we can readily convince ourselves that there are 20 ways. The first possible sequence might look like this:

I H H H H H H H H H H H H H H H H H H H

The second possible sequence might look like this:

H I H H H H H H H H H H H H H H H H H H

And, the last possible sequence might look like this:

H H H H H H H H H H H H H H H H H H H I

That must mean that there are 20 possible positions for the one I.  Alternatively, we could use the formula for counting distinguishable permutations. The formula yields:

\(\dbinom{20}{1}=\dfrac{20!}{1!19!}=20\)

How may arrangements are there of the 20 people that involve 2 people ill?

Solution. I'm going to leave it to you to decide if you want to try to count this one out by hand! I can tell you that the first possible sequence might look like this:

I I H H H H H H H H H H H H H H H H H H

The formula for counting distinguishable permutations yields:

\(\dbinom{20}{2}=\dfrac{20!}{2!18!}=190\)

possible arrangements.

MississippiExample

How many ordered arrangements are there of the letters in MISSISSIPPI?

Solution. Well, there are 11 letters in total:

1 M, 4 I, 4 S and 2 P

We are again dealing with arranging objects that are not all distinguishable. We couldn't distinguish among the 4 I's in any one arrangement, for example. In this case, however, we don't have just two, but rather four, different types of objects. In trying to solve this problem, let's see if we can come up with some kind of a general formula for the number of distinguishable permutations of n objects when there are more than two different types of objects.

Let's formalize our work.

Definition. The number of distinguishable permutations of n objects, of which:

  • n1 are of one type
  • n2 are of a second type
  • ... and ...
  • nk are of the last type

and nn1 n2 + ... + nis given by:

\(\dbinom{n}{n_1n_2n_3\ldots n_k}=\dfrac{n!}{n_1!n_2!n_3! \ldots n_k!}\)

Let's take a look at a few more examples involving distinguishable permutations of objects of more than two types.

Example

How many ordered arrangements are there of the letters in the word PHILIPPINES?

Solution. The number of ordered arrangements of the letters in the word PHILIPPINES is:

\(\dfrac{11!}{3!1!3!1!1!1!1!}=1,108,800\)

pigsExample

Fifteen (15) pigs are available to use in a study to compare three (3) different diets.  Each of the diets (let's say, A, B, C) is to be used on five randomly selected pigs. In how many ways can the diets be assigned to the pigs? 

Solution. Well, one possible assignment of the diets to the pigs would be for the first five pigs to be placed on diet A, the second five pigs to be placed on diet B, and the last 5 pigs to be placed on diet C. That is:

A  A  A  A  A  B  B  B  B  B  C  C  C  C  C

Another possible assignment might look like this:

A  B  C  A  B  C  A  B  C  A  B  C  A  B  C

Upon studying these possible assignments, we see that we need to count the number of distinguishable permutations of 15 objects of which 5 are of type A, 5 are of type B, and 5 are of type C.  Using the formula, we see that there are:

\(\dfrac{15!}{5!5!5!}=756756\)

ways in which 15 pigs can be assigned to the 3 diets. That's a lot of ways!