3.4 - Distinguishable Permutations

Example 3-13 Section

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

Answer

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\times 2\times 2\times 2\times 2\times 2\times 2\times 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 \(n-r=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 \(\dfrac{56}{256}=0.22\).

Let's formalize our work here!

Distinguishable permutations of \(n\) objects
Given \(n\) objects with:
  • \(r\) of one type, and
  • \(n-r\) of another type

there are:

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

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

Example 3-14 Section

the word Mississippi on the side of a building

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

Answer

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.

number of distinguishable permutations of \(n\) objects
  • \(n_1\) are of one type
  • \(n_2\) are of a second type
  • ... and ...
  • \(n_k\) are of the last type

and \(n=n_1+n_2+\ldots +n_k\)is 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 3-15 Section

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

Answer

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

Example 3-16 Section

group of pigs

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?

Answer

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!