Many of the most useful techniques in probability and statistics are based on counting. This chapter presents techniques and shortcuts for counting that are particularly helpful when the number of things to be counted is large. These techniques form the basis of our study of probability and statistics throughout the rest of the book.
Suppose we want to know the number of ways a coin can land "heads" exactly twice in three tosses. Let "H" stand for "head" and "T" stand for "tail." The possible outcomes of tossing a coin three times are shown in
There are eight possible outcomes of tossing the coin three times, if we keep track of what happened on each toss separately. In three of those eight outcomes (the outcomes labeled 2, 3, and 5), there are exactly two heads.
This way of counting becomes overwhelming very quickly as the number of tosses increases. For example, how many ways are there to get exactly 5 heads in 10 tosses of a coin? There are 1,024 possible sequences of heads and tails in 10 tosses of a coin; 252 of them contain exactly 5 heads. I would not want to list them all—it would be both tedious and error prone.
When the number of things to be counted is large, it is essential to approach counting systematically: Enumerating all the possibilities becomes very difficult, and shortcuts and formulae become crucial. For example, 2^{n} different subsets can be formed from a collection of n elements, so a collection of 10 objects has 2^{10} = 1,024 subsets. Similarly, there are 2^{n} possible sequences of heads and tails in n tosses of a coin.
Counting large sets by listing all the possibilities is impractical—mathematical imagination offers advantages over enumeration. The most important fact in this chapter is the Fundamental Rule of Counting, which helps count the possible outcomes of a sequence of choices.
In the previous example of tossing a coin thrice, each toss results in one of two possible outcomes: heads or tails. For each possible outcome of the first toss, there are two possible outcomes of the second toss, so after the second toss, there are in all four possible outcomes (2 × 2 = 4). For each of the four possible outcomes of the first and second tosses, there are two possible outcomes of the third toss, so after the third toss, there are in all eight possible outcomes (2 × 2 × 2 = 8). Counting the total number of possibilities is like counting the leaves on the following upside-down tree:
There are eight leaves on the upside-down tree, corresponding to the eight possible sequences of heads and tails. Each path from the root to a leaf is a possible sequence of heads and tails. The red path, which terminates in the third leaf from the left, corresponds to getting heads on the first toss, tails on the second toss, and heads on the third toss. There is no particular reason to draw the tree upside-down: We could just as well have drawn it right-side-up, or sideways.
Suppose there is a group of seven statisticians, three male and four female. The group wants one man and one woman to represent them at a meeting of the American Statistical Association. How many possible pairs of one man and one woman from this group are there?
We could consider forming (male, female) pairs by first picking one of the three men, then picking one of the four women. Suppose the men are Erich, Jerzy, and Lucien, and the women are Betty, F.N., Grace, and Juliet. A sideways tree for choosing a pair of names, one male and one female, would look like this:
The fourth leaf from the top is the pair (Erich, Juliet); the fifth leaf from the top is (Jerzy, Betty); etc. There are twelve pairs in all: Each of the three men can each be matched with each of the four women—four possible choices of women for each of three possible choices of men. The total number of leaves is thus 3 × 4 = 12. Had there been five men and seven women, there would have been 5 × 7 = 35 possible male-female pairs. In general, if there are n_{1} males and n_{2} females, there are n_{1} × n_{2} possible male-female pairs. Note that if, for instance, Erich and Juliet refused to be on the committee together, the number cannot be found this way: The number of possible choices for women would depend on which man was chosen.
The Fundamental Rule of Counting generalizes the special cases we have just seen.
The Fundamental Rule of Counting
If a set of choices or trials, T_{1}, T_{2}, T_{3}, …, T_{k}, could result, respectively, in n_{1}, n_{2}, n_{3}, …, n_{k} possible outcomes, the entire set of k choices or trials has
n_{1} × n_{2} × n_{3} × … × n_{k}
possible outcomes.
(The numbers n_{1}, n_{2}, n_{3}, …, n_{k} cannot depend on which outcomes actually occur.)
The Fundamental Rule of Counting leads to very useful formulae for many familiar situations, as we shall see. The following exercises check your ability to use the Fundamental Rule of Counting.
The following exercise illustrates an important strategy for counting the elements of a set: partitioning. Divide the set into smaller subsets that do not overlap, but that together contain every element of the original set. Count the number of elements of the subsets separately, and then add those subtotals to find the number of elements in the original set.
Suppose we are given a collection of five distinct items. How many ways are there of ordering them? We can think of this as a sequence of five choices, each of which results in the selection of one of the remaining things. For the first choice there are five possible outcomes. For the second choice, there will be four possible outcomes because one item has already been chosen. We don't know what the possible outcomes are, because they depend on the outcome of the first selection, but regardless of which item was picked first, four items remain as possibilities for the second choice. Similarly, three items will remain as possible third choices, two as possible fourth choices, and only one item will remain to be the fifth.
By the Fundamental Rule of Counting, the total number of possible sequences of choices is 5 × 4 × 3 × 2 × 1 = 120 sequences. Each sequence is called a permutation of the five items. A permutation of items is an ordering of the items. More generally, by the Fundamental Rule of Counting, in ordering n things, there are n choices for the first, (n−1) choices for the second, etc., so the total number of ways of ordering a total of n things is
n × (n−1) × (n−2) × … × 1.
This product, n × (n−1) × (n−2) × … × 1, is written n!, which is pronounced "n factorial." By convention, 0! = 1.
The following example illustrates counting permutations.
More generally, suppose we wanted to arrange only k of n things in some order (without repeating anything). What is the number of orderings (permutations) of k of n things? There are n choices for the first item, (n−1) choices for the second item, and so on, down to (n−k+1) choices for the kth item. By the fundamental rule of counting, _{n}P_{k}, the total number of permutations (orderings) of k of n things, is
_{n}P_{k} = n × (n−1) × (n−2) × … × (n−k+1).
This product can be expressed in shorthand using factorials. If we multiplied _{n}P_{k} by
(n−k) × (n−k-1) × (n−k-2) × … × 1 = (n−k)!,
the product would be n!. That is,
_{n}P_{k} × (n−k)! = [ n × (n−1) × (n−2) × … × (n−k+1)] × [(n−k) × (n−k-1) × (n−k-2) × … × 1] = n × (n−1) × (n−2) × … × 1 = n!.
Therefore, _{n}P_{k} = n!/(n−k)!.
Permutations
The number of possible permutations (orderings) of k of n things is
_{n}P_{k} = n!/(n−k)!
(k must be at least 0 and no larger than n.)
The following exercises check your understanding of permutations.
Permutations, which we just discussed, are ways of ordering things. Suppose that instead we are just interested in sets of things, without regard to the order of the things in the set.
Suppose we wanted to play 4 of 11 songs on a CD. Before, we counted (track 1, track 2, track 3, track 4) as a different way of playing four songs than (track 2, track 1, track 3, track 4). However, the same set of four songs would be played in both cases.
There are 11 × 10 × 9 × 8 = 7,920 different ways to play four of the eleven songs. In a list of all 7,920 of these ways, each set of four songs would appear in 4! = 24 different orders. Thus the number of sets of four of the eleven songs is 7,920/24 = 330.
Similarly, consider how many pairs of students one could form from 20 students, without regard to the order in which a pair might be picked. That is, (Alice, Carlos), and (Carlos, Alice) constitute the same pair, {Alice, Carlos}. As discussed above, the fundamental rule of counting tells us that there are 20 × 19 = 380 ordered pairs of students. The ordered-pair calculation counts the set {Alice, Carlos} as two distinct ordered pairs. Each pair of people appears as two different ordered pairs among the 380. Therefore the number of sets of two of 20 students is 380/2 = 190. (This is also called the number of combinations of 20 students taken 2 at a time.)
Suppose that we were interested in triples of students rather than pairs. How many possible triples of students are there in a class of 20? Order does not matter, so {Jerzy, Ronald, Elizabeth} is the same triple no matter how we order them. There are 6,840 possible ordered triples taken from 20 students:
This ordered-triple calculation, _{20}P_{3} = 20!/(20-3)! = 20 × 19 × 18, counts the single set {Jerzy, Ronald, Elizabeth} as 3 × 2 × 1=6 distinct ordered triples, as shown in .
Similarly, every other distinct triple of people is also represented 6 times in the count of 6,840, because there are 3! = 6 ways of ordering each set of three people. Every combination (set) of three individuals thus appears as 6 permutations among the ordered triples. Therefore the number of combinations of 20 students taken 3 at a time (without regard to order) is 6,840/6 = 1,140.
The symbol used to denote the number of combinations of n things taken k at a time is _{n}C_{k}. The general rule is that the number of combinations of n things taken k at a time is the number of permutations of n things taken k at a time, divided by the number of permutations of k things (which is k!). Indeed, one can think of generating all permutations of k of n things by first selecting all subsets of k of n things, then permuting each of those sets of k things into all k! orderings:
_{n}C_{k} k! = _{n}P_{k},
so
We just calculated the special case
_{20}C_{3} = 20!/(3! × 17!) = 1,140.
Combinations
The number of possible combinations of n things taken k at a time (without regard to order) is
(k must be less than or equal to n.)
The derivation of the formula for _{n}C_{k} illustrates a useful strategy for counting: Sometimes, it is easier to find the number of elements in a set by counting each element several times, then dividing the count by the multiplicity—the number of times each element was counted—than it is to count each item once. (This approach requires that every element be counted the same number of times.) We derived the formula for _{n}C_{k} by counting each combination of k things k! times (which gave the number of permutations of k of n things), then dividing by k!.
The formula for counting combinations has special cases that are worth memorizing:
_{n}C_{0} = _{n}C_{n} = 1.
(There is only one way to pick no thing and only one way to pick all n things.)
_{n}C_{1} = _{n}C_{n−1} = n
(there are n ways to pick one thing or to leave one thing out)
_{n}C_{k} = _{n}C_{n−k}
(There are the same number of ways of picking k of n things as there are of leaving out k of n things)
The following applet is a calculator that includes buttons for factorials (!), combinations (_{n}C_{k}), and permutations (_{n}P_{k})
To find the factorial of a number, type in the number (or use the calculator's keypad to enter the number), then click !. To find the number of combinations of n things taken k at a time, type in the value of n, click _{n}C_{k}, type in the value of k (replacing the value of n), and then click =. This calculator is available from the menu bar on this page under "Tools", both as a pop-up and as a full page.
The following exercises check your ability to use factorials and combinations to count. The calculator might be helpful in solving the exercises.
Recall that a deck of cards consists of 52 cards, 13 "kinds" each of four suits (spades, hearts, diamonds, and clubs). The 13 kinds are Ace (A), 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack (J), Queen (Q), King (K). In many poker games, each player is dealt five cards from a well shuffled deck. The following callout lists the different poker hands. count the number of distinguishable ways some of those hands can occur.
Possible Poker Hands
Notes: Hands are counted as the best hands they can be. For instance, the hand {K of spades, K of hearts, K of diamonds, K of clubs, 3 of diamonds} is 4 of a kind. It is not counted as 3 of a kind, nor as two pair, nor as one pair, nor as King-high, even though it contains 3 of a kind, two pair and one pair and the highest card in the hand is a King. Similarly, a royal flush is not a straight, a flush, nor a straight flush; and a straight flush is neither a straight nor a flush. Straights cannot "wrap around": {Q, K, A, 2, 3} is not a straight.
How many ways are there to get one pair in a five card hand?
Solution. There are 13 possible choices for the kind of which to have a pair; for any kind that is chosen, there are _{4}C_{2} = 6 possible choices of two of the four cards of that kind (2 of the four suits). There are 12 kinds remaining from which to select the other three cards in the hand. We must insist that the kinds be different from each other and from the kind of which we have a pair, or we could end up with a second pair, three or four of a kind, or a full house; thus there are _{12}C_{3}=220 ways to pick the kinds of the remaining three cards. There are 4 choices for the suit of each of those three cards, a total of 4^{3} = 64 choices for the suits of all three. By the fundamental rule of counting, the number of "one pair" hands is therefore
13 × 6 × 220 × 64 = 1,098,240.
How many ways are there to get four of a kind in a five card hand?
Solution. There are 13 possible choices for the kind of which to have four, and 52-4=48 choices for the fifth card. Once the kind has been specified, the four are completely determined: you need all four cards of that kind. Thus there are 13 × 48=624 ways to get four of a kind.
How many ways are there to get 10-high in a five card hand, if Aces can be high or low?
Solution. To have 10-high, one of the cards must be a 10, and the other four cards must be of different kinds, less than ten. However, the cards cannot be consecutive in value, or the hand would be a straight, rather than 10-high, and the cards cannot all have the same suit, or the hand would be a flush. Moreover, if we allow aces to be high or low, then no one would count an ace low if it were the best thing in his hand, so the cards less than 10 are 2, 3, 4, 5, 6, 7, 8, 9. Therefore, there are _{8}C_{4} ways of picking four kinds less than 10. One of those, {6, 7, 8, 9}, would yield a straight {6, 7, 8, 9, 10}, so we need to subtract one from _{8}C_{4} to get just those choices that give 10-high. We still need to specify the suits of the cards. We have four choices of suit for each of the five cards, a total of 4^{5} possibilities. However, we need to exclude the possibilities in which all the cards have the same suit, because then the hand would be a flush, rather than 10-high. There are 4 such possibilities: all the cards are spades, all the cards are hearts, all are diamonds, and all are clubs. Thus the number of acceptable ways to pick the suits is 4^{5}-4. Combining that with the number of ways of picking the kinds of the other cards, we get
number of ways to get 10-high = (_{8}C_{4}-1) × (4^{5}-4).
This example illustrates another strategy that can be helpful in counting: Count the elements in a set larger than the one you seek to count, then subtract the number of extras. We used that trick twice in this example—in subtracting the number of combinations of kinds that would give a straight from the number of ways of picking four cards less than the 10, and in subtracting the four combinations of suits that would give a flush from the total number of combinations of suits of the five cards.
The following exercises check your ability to find the number of distinguishable ways some events can occur. You can use the calculator to compute combinations and factorials to solve the exercises.
Counting by enumeration is cumbersome, difficult, inefficient, and error prone when the number of items is large. The Fundamental Rule of Counting can make counting easier in many situations. Essentially, the Fundamental Rule of Counting says that the total number of leaves on a tree is the number of leaves per branch times the number of branches, provided every branch has the same number of leaves.
The factorial of an integer m > 0 is the product of all the positive integers less than or equal to m:
m! = m × (m-1) × . . . × 1.
By convention, 0! = 1. A permutation of k of n things is a listing of k of the n things in some order. A set or combination of k of n things is a collection of k of the n things without regard to their order. The Fundamental Rule of Counting leads to simple formulae for the number _{n}P_{k} of permutations of k of n things, and the number _{n}C_{k} of combinations of k of n things:
_{n}P_{k} = n!/(n−k)!, and
_{n}C_{k} = _{n}P_{k}/k! = n!/(k! × (n−k)!).
In addition to the Fundamental Rule of Counting, there are other strategies that can help in complicated counting problems:
Most of the mathematical results in this book in both statistics and probability are applications of these simple ideas.