3 Counting rules
$$
$$
In Chapter 1 we considered several examples of statistical experiments. Some of these had sample spaces with a finite number of outcomes, while others had sample spaces with an infinite number of outcomes. If a sample space has a finite number of outcomes, we will call it a finite sample space.
For any set \(A\), denote by \(|A|\) the cardinality of a set, which is the number of elements it contains. Thus a sample space \(S\) is finite if \(|S| < \infty\).
The following result helps us to compute probabilities of events in experiments in which every possible outcome in a finite sample space is equally likely.
Proposition 3.1 (Computing probabilities when all outcomes are equally likely) If all outcomes in a finite sample space \(S\) are equally likely, then for any event \(A \subset S\), we have \[ P(A) = \frac{|A|}{|S|}. \]
The above follows from the fact that, if each outcome in \(S\) is equally likely, each outcome must have probability \(1/|S|\). Since individual outcomes are mutually exclusive, the probability of a set of outcomes \(A\) is the sum of the probabilities of the individual outcomes belonging to \(A\), leading to \(P(A) = |A| / |S|\).
Example 3.1 (Sum of rolls of two dice) Consider rolling two dice and let \(A\) be the event that the sum of the rolls is \(8\). Referring to Example 1.5 we may write \[ A = \{(6,2),(5,3),(4,4),(3,5),(2,6) \}, \] by which we can see that there are \(5\) ways to roll two dice such that the sum is \(8\). There are \(|S| = 36\) possible outcomes in the sample space, each occurring with equal probability. Thus we have \(P(A) = 5/36\).
For many experiments it is impractical to write down all the possible outcomes in the sample space \(S\) or in an event of interest \(A\). For such cases we can use some rules to help us count numbers of outcomes in an event. All the rules follow from this one fundamental rule:
Proposition 3.2 (Fundamental theorem of counting) If a job consists of \(K\) tasks such that the tasks may be completed in \(n_1,\dots,n_K\) ways, respectively, then there are \[ \prod_{k=1}^K n_k = n_1 \times n_2 \times \dots \times n_K \] ways to do the job.
Example 3.11 (Video game avatars) You can customize your video game avatar by selecting from \(6\) choices of pants, \(4\) choices of shirt, \(3\) choices of backpack, \(4\) choices of skin tone, and \(4\) choices of hairstyle, and by choosing between sunglasses and no sunglasses. What is the number of possible avatars? 1
Example 3.2 (Combination lock) A combination lock opens when four wheels engraved with the digits 0–9 are turned to display a certain sequence of four numbers. How many sequences of four-digit numbers can the lock display?2
The next rule is for a permutation:
Proposition 3.3 (Permutation) The number of ways to draw \(r\) elements from \(N\) elements without replacement and arrange them in some order is \[ N(N-1) \cdots (N - r + 1) = \frac{N!}{(N-r)!}. \]
To understand the above rule, imagine a bag marbles, in which each marble is unique, and suppose you are going to draw marbles from the bag one at a time, placing the drawn marbles in a row. The phrase “without replacement” means that once you draw a marble, you will not put it back in the bag before drawing the next one. By placing the drawn marbles in a row, we keep track of the order in which they were drawn from the bag.
Example 3.3 (Javelin throwers) Seventeen javelin throwers will compete for gold, silver, and bronze medals such that the thrower throwing the furthest, second furthest, and third furthest will be awarded the gold, silver, and bronze medal, respectively. In how many ways can the medals be awarded?3
Example 3.4 (Bleacher seating) You and four friends will next to each other in a single row of the bleachers. In how many ways can you arrange yourselves? 4
The next rule is for a partition. It is presented in the language of probabilists of old, who spent lots of time putting balls into urns.
Proposition 3.4 (Partition) The number of ways to place \(N\) balls into \(K\) urns such that the \(K\) urns receive \(n_1,\dots,n_K\) balls, where \(N = n_1 + \dots + n_K\), is \[ \frac{N!}{n_1!n_2!\cdots n_K!}. \]
Example 3.5 (Making teams) Suppose you have nineteen people and you want to split them into two teams of six and one team of seven. In how many ways can you do this?5
Next rule is for a combination, which is just a partition with only two “urns”.
Proposition 3.5 (Combination) The number of ways to draw \(r\) elements from \(N\) without replacement and without regard to their order is \[ \left. N \choose r \right. = \frac{N!}{r!(N-r)!}. \]
To understand the combination, imagine again a bag of marbles, in which each marble is unique. Suppose you draw marbles one at a time from the bag and place the drawn marbles in a new bag. In the end you have two bags of marbles, and you are interested in which marbles were drawn and placed in the new bag—but you are not interested in the order in which the marbles were drawn (you have not placed the drawn marbles in a row, as in the case of a permutation).
Example 3.6 (Weekend visits) Your parents insist you come home on three weekends during the semester, of which there are sixteen weekends to choose from. In how many ways can you choose the three weekends during which you will visit your parents?6
Example 3.7 (Poker hand) Suppose you are dealt a five-card hand from a standard fifty-two-card deck. How many five-card hands are possible? 7
Having learned some counting rules, we now consider applying them to compute some probabilities of the form \(P(A) = |A| / |S|\) given in Proposition 3.1.
Example 3.10 (Queen of Spades in 5-card hand) Suppose you are dealt a five-card hand from a standard fifty-two-card deck. What is the probability your hand has the Queen of Spades? To answer this let \(A\) be the event that your hand has the queen of spades. Then the probability will be given by \(P(A) = |A| / |S|\), where the number of possible five-card hands \(|S|\) was found in Example 3.7. To find \(|A|\), we must think a little. All counting problems can be broken down into a sequence of tasks so that the fundamental theorem of counting can be used. To count the number of five-card hands with the Queen of Spades, consider the tasks needed in the construction of such a hand. The first task is to put into the hand the Queen of Spades; this can be done in only one way, as there is only one Queen of Spades. Then next task is to choose the other four cards which will make up the hand. This entails selecting four cards from the fifty-one cards remaining in the deck after the removal of the Queen of Spades. This can be done in \({51 \choose 4}\) ways. So we have \(|A| = 1 \times {51 \choose 4}\) from the fundamental theorem of counting. Putting this together with \(|S| = {52 \choose 5}\), we obtain \[ P(A) = \frac{{51 \choose 4}}{52 \choose 5} = \frac{5}{52} = 0.0961538. \]
Example 3.8 (All cards of one suit in 5-card hand) Suppose you are dealt a five-card hand from a standard fifty-two-card deck. What is the probability you are dealt cards of only one suit? Let \(A\) be the number of five-card hands with cards of only one suit. To find \(|A|\), we break down the construction of a single-suited hand into tasks. The first task is to choose a suit: there are four choices. After choosing a suit, we must draw five cards from that suit. There are thirteen cards of each suit, so for each suit there are \({13 \choose 5}\) five-card hands having all cards of that suit. Putting the tasks in sequence, the fundamental theorem of counting gives \(|A| = 4\times {13 \choose 5}\). Putting this together with \(|S| = {52 \choose 5 }\) gives \[ P(A) = \frac{4\times {13 \choose 5}}{52 \choose 5 } = 0.0019808. \]
Example 3.9 (At least one ace) Suppose you are dealt a five-card hand from a standard fifty-two-card deck. What is the probability you are dealt at least one ace?8
According to the fundamental theorem of counting, the total number of possible avatars is \(6 \times 4\times 3\times 4\times 4\times 2 = 2304\).↩︎
According to the fundemental theorem of counting, the number of possible sequences is \(10\times 10 \times 10 \times 10 = 10000\).↩︎
This is a permutation. The answer is \(17 \times 16 \times 15 = 4080\).↩︎
This is a permutation. It can be done in \(5 \times 4 \times 3 \times 2 \times 1 = 120\) ways.↩︎
This is a partition. It can be done in \(\frac{19!}{6!6!7!}=46558512\) ways↩︎
This is a combination (or really a partition with two urns—put weekends into a “go-home” bin and a “do-not-go-home” bin). There are \(\frac{16!}{3!(16-3)!} = \frac{16 \times 15 \times 14}{ 3 \times 2} = 16 \times 5 \times 7 = 80 \times 7 = 560\) ways.↩︎
This is a combination. There are \({52 \choose 5} = \frac{52!}{5!47!} = \frac{52 \times 51 \times 50\times 49\times 48}{5\times 4\times 3\times 2 \times 1} = 2.59896\times 10^{6}\) possible hands.↩︎
Whenever we see the words “at least”, we should instinctively think of the complement event, which in this case would be getting dealt a hand with no aces. If we compute this we can subtract the result from one to get the answer. The other route is computing the probability of getting exactly one ace, exactly two aces, exactly three, and so on, which would require much more work. So, let \(A\) be the event that your are dealt a five-card hand with no aces. In how many ways can we construct such a hand? Well, four of the fifty-two cards are aces, so we just need to choose five cards from the forty-eight cards which are not aces. This can be done in \(48 \choose 5\) ways. So we have \(P(A) = \frac{48 \choose 5}{52 \choose 5}\). The event of interest is \(A^c\), for which \(P(A^c) = 1 - \frac{48 \choose 5}{52 \choose 5} = 0.341158\).↩︎