Permutations and Combinations

PERMUTATIONS AND COMBINATIONS

In this section, we will derive some results from combinatorial mathematics. These results will be useful in obtaining shortcut calculations of probabilities of events linked to specific probability distributions to be discussed in Sections 5.6 and 5.7.

In the previous sections, we presented a common method for calculating proba-bilities: We calculated the probability of an event by counting the number of possi-ble ways that the event can occur and dividing the resulting number by the total number of equally likely elementary outcomes. Because we used simple examples, with 36 possibilities at most, we had no difficulty applying this formula.

However, in many applied situations the number of ways that an event can occur is so large that complete enumeration is tedious or impractical. The combinatorial methods discussed in this section will facilitate the computation of the numerator and denominator for the probability of interest.

Let us again consider the experiment where we toss dice. On any roll of a die, there are six elementary outcomes. Suppose we roll the die three times so that each roll is independent of the other rolls. We want to know how many ways we can roll a 4 or less on all three rolls of the die without repeating a number.

We could do direct enumeration, but there are a total of 6 × 6 × 6 = 216 possible outcomes. In addition, the number of successful outcomes may not be obvious. There is a shortcut solution that becomes even more important as the space of possible out-comes, and possible successful outcomes, becomes even larger than in this example.

Thus far, our problem is not well defined. First we must specify whether or not the order of the distinct numbers matters. When order matters we are dealing with permutations. When order does not matter we are dealing with combinations.

Let us consider first the case in which order is important; therefore, we will be determining the number of permutations. If order matters, then the triple {4, 3, 2} is a successful outcome but differs from the triple {4, 2, 3} because order matters. In fact, the triples {4, 3, 2}, {4, 2, 3}, {3, 4, 2}, {3, 2, 4}, {2, 4, 3}, and {2, 3, 4} are six distinct outcomes when order matters but count only as one outcome when order does not matter, because they all correspond to an outcome in which the three num-bers 2, 3, and 4 each occur once.

Suppose the numbers 4 or lower comprise a successful outcome. In this case we have four objects—the numbers 1, 2, 3, and 4—to choose from because a choice of 5 or 6 on any trial leads to a failed outcome. Since there are only three rolls of the die, and a successful roll requires a different number on each trial, we are interested in the number of ways of selecting three objects out of four when order matters. This type of selection is called the number of possible permutations for selecting three objects out of four.

Let us think of the problem of selecting the objects as filling slots. We will count the number of ways we can fill the first slot and then, given that the first slot is filled, we consider how many ways are left to fill the second slot. Finally, given that we have filled the first two slots, we consider how many ways remain to fill the third slot. We then multiply these three numbers together to get the number of per-mutations of three objects taken out of a set of four objects.

Why do we multiply these numbers together? This procedure is based on a sim-ple rule of counting. To illustrate, let us consider a slightly different case that in-volves two trials. We want to observe an even number on the first trial (call that event A) and an even number on the second trial. However, the number on the sec-ond trial must differ from the one chosen on the first (call that event B).

On the first trial, we could get a 2, 4, or 6. So there are three possible ways for A to occur. On the second trial, we also can get a 2, 4, or 6, but we can’t repeat the re-sult of the first trial. So if 2 occurred for A, then 4 and 6 are the only possible out-comes for B. Similarly, if 4 occurred for A, then 2 and 6 are the only possible out-comes for B.

Finally, if the third possible outcome for A occurred, namely 6, then only 2 and 4 are possible outcomes for B. Note that regardless of what number occurs for A, there are always two ways for B to occur. Since A does not depend on B, there are always three ways for A to occur.

According to the multiplication rule, the number of ways A and B can occur to-gether is the product of the individual number of ways that they can occur. In this example, 3 × 2 = 6 ways. Let us enumerate these pairs to see that 6 is in fact the right number.

We have {2, 4}, {2, 6}, {4, 2}, {4, 6}, {6, 2}, and {6, 4}. This set consists of the number of permutations of two objects taken out of three, as we have two slots to fill with three distinct even numbers: 2, 4, and 6.

Now let us go back to our original, more complicated, problem of selecting three (since we are filling three slots) from four objects: 1, 2, 3, and 4. By using mathe-matical induction, we can show that the multiplication law extends to any number of slots. Let us accept this assertion as a fact. We see that our solution to the prob-lem involves taking the number of permutations for selecting three objects out of four; the multiplication rule tells us that this solution is 4 × 3 × 2 = 24.

The following list enumerates these 24 cases: {4, 3, 2}, {4, 3, 1}, {4, 2, 3}, {4, 2, 1}, {4, 1, 3}, {4, 1, 2}, {3, 4, 2}, {3, 4, 1}, {3, 2, 4}, {3, 1, 4}, {2, 4, 3}, {2, 4, 1}, {2, 3, 4}, {2, 1, 4}, {1, 4, 3}, {1, 4, 2}, {1, 3, 4}, {1, 2, 4}, {3, 2, 1} {3, 1, 2}, {2, 3, 1}, {2, 1, 3}, {1, 3, 2}, and {1, 2, 3}. Note that a systematic method of enumeration is important; otherwise, it is easy to miss some cases or to acciden-tally count cases twice.

Our system is to start with the highest available number in the first slot; once the first slot is chosen, we select the next highest available number for the second slot, and then the remaining highest available number for the third slot. This process is repeated until all cases with 4 in the first slot are exhausted. Then we consider the cases with 3 in the first slot, the highest available remaining number for the second slot, and then the highest available remaining number for the third slot. After the 3s are exhausted, we repeat the procedure with 2 in the first slot, and finally with 1 in the first slot.

In general, let r be the number of objects to choose and n the number of objects available. We then denote by P(n, r) the number of permutations of r objects chosen out of n. As an example of permutations, we denote the quantity 3 × 2 = 3 × 2 × 1 as 3!, where the symbol “!” represents the function called the factorial. In our notation and formulae, 0! exists and is equal to 1. Formula 5.7 shows the permutations of r objects taken from n objects:

P(n, r) = n!/(n – r)!                               (5.7)

From Formula 5.7, we see that when n = 3 and r = 2, P(3, 2) = 3!/(3 – 2)! = 3!/1! = 3! = 6. This result agrees with our enumeration of distinct even numbers on two rolls of the die. Also, P(4, 3) = 4!/(4 – 3)! = 4!/1! = 4! = 24. This number agrees with the result we obtained for three independent rolls less than 5.

Now we will examine combinations. For combinations, we consider only distinct subsets but not their order. In the example of distinct outcomes of three rolls of the die where success means three distinct numbers less than 5 without regard to or der, the triplets {2, 3, 4}, {2, 4, 3}, {3, 2, 4}, {3, 4, 2}, {4, 3, 2}, and {4, 2, 3} differ only in order and not in the objects included.

Notice that for each different set of three distinct numbers, the common number of permutations is always 6. For example, the set 1, 2, and 3 contains the six triplets {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3, 2, 1}. Notice that the num-ber six occurs because it is equal to P(3, 3) = 3!/0! = 3! = 6.

Because for every distinct combination of r objects selected out of n there are P(r, r) orders for these objects, we have P(n, r) = C(n, r)P(r, r) where C(n, r) de-notes the number of combinations for choosing r objects out of n. Therefore, we ar-rive at the following equation for combinations, with the far-right-hand side of the chain of equalities obtained by substitution, since P(r, r) = r! C(n, r) = P(n, r)/ P(r, r) = n!/[(n – r)! P(r, r)] = n!/[(n – r)! r!]. Formula 5.8 shows the formula for combinations of r objects taken out of n:

C(n, r) = n!/[(n – r)! r!]                               (5.8)

In our example of three rolls of the die leading to three distinct numbers less than 5, we obtain the number of combinations for choosing 3 objects out of 4 as C(4, 3) = 4!/[1! 3!] = 4. These four distinct combinations are enumerated as follows: (1) 1, 2 and 3; (2) 1, 2 and 4; (3) 1, 3 and 4; and (4) 2, 3 and 4.