we will derive some results from combinatorial mathematics.
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.
Related Topics
TH 2019 - 2023 pharmacy180.com; Developed by Therithal info.