2  Techniques for Counting

To compute probabilities, we need to be able to count the number of outcomes in different sample spaces and events. For most of the examples in Chapter 1, this counting could be done by listing all the possible outcomes (e.g., see Figure 1.7). However, problems like Cardano’s (Example 1.1), involve larger sample spaces and are less straightforward. To tackle these more difficult problems, we’ll need tools from combinatorics, the branch of mathematics concerned with counting.

Like probability, combinatorics is a tricky subject that can be daunting and counterintuitive at first. But, with a principled approach and some practice, solving combinatorics problems becomes a routine and even fun endeavor!

2.1 The Fundamental Principle of Counting

We illustrate the central idea behind counting with a simple example.

Example 2.1 (Counting outfits) Suppose we are picking our outfit for the day. An outfit is composed of three clothing items: shoes, pants, and a shirt. For shoes, we have tennis shoes, boots, and flip-flops. For pants, we have jeans and sweatpants. And for shirts we have a t-shirt, a button-down shirt, a long-sleeve shirt, and a tank-top. Assuming any combination of shoes, pants, and a shirt make a wearable outfit, how many different outfits can we make?

Each of the \(3\) pairs of shoes can be matched with \(2\) possible pairs of pants, making \(2 \times 3 = 6\) shoe and pant combinations. For each of these \(6\) shoe and pant combinations, there are \(4\) different shirts we can wear, making for a total of \(2 \times 3 \times 4 = 6 \times 4 = 24\) outfits. Figure 2.1 both clearly illustrates this line of reasoning and enumerates all the possible outfits.

Figure 2.1: Visual enumeration of all possible outfits.

Our solution in Example 2.1 is an example application of the fundamental principle of counting.

Theorem 2.1 (The fundamental principle of counting) Suppose you need to perform \(n\) consecutive actions and, regardless of the previously taken actions, there are always \(k_i\) distinct ways to perform the \(i\)th action. Then, there are \[ \prod_{i=1}^{n} k_i = k_1 \times \dots \times k_n\] unique ways to perform all \(n\) actions.

In Example 2.1, we made outfits by performing three actions: choosing a pair of shoes, choosing a pair of pants, and choosing a shirt. Each way of performing the actions results in a unique outfit, and each possible outfit results from a unique way of peforming the actions. Thus, the number of different outfits is the same as the number of unique ways we can perform these actions. Since there are \(3\) ways to perform the first action, then always \(2\) ways to perform the second, and then always \(4\) ways to perform the third, Theorem 2.1 tells us that there are \(2 \times 3 \times 4 = 24\) unique ways of doing so. Note if we imagined picking our shoes, pants, and shirt in a different order (e.g., first pick the pants, then shirt, then shoes), we would’ve arrived upon the same answer.

Correctly applying Theorem 2.1

Theorem 2.1 allows us to count the number of ways we can take some actions. To use it to count the number of items in a set, we need to verify that there a one-to-one correspondence between ways of taking the actions and items in the set (i.e., each way of taking actions corresponds to a unique item in the set, and vice-versa). We won’t always explicity verify this in the text, but you should as you read along. Verifying one-to-one correspondences is the key to doing combinatorics correctly.

2.2 Selecting Items from a Collection

When solving combinatorics problems, we often need to know the number of ways we can select \(k\) items from a collection of \(n\) unique items. In this section, we discuss four classic variations of this problem. These variations arise from (1) whether we care about the order of selection or not and (2) whether we perform selection with or without replacement.

2.2.1 With Replacement, Order Matters

In our first variation, we’ll suppose that the order of selection matters (i.e., selecting item 1 and then item 2 is not the same as selecting item 2 and then item 1) and that we select items with replacement, meaning items can be selected multiple times.

As an illustrative example, suppose we want to select \(k = 2\) animals from the following collection of \(n=4\) animals:

We’ll record our selections as entries in an ordered tuple. To start, we select one of the four animals as our first animal:

Then, because we are selecting with replacement, we can still select any of the four to be our second animal, including possibly selecting the same animal again:

In total, we see that there are \(4 \times 4 = 16\) different ways to select the two animals.

What if we wanted to select a third animal? For each of these two-animal selections, there would still be \(4\) choices for the third animal, making for a total of \(4 \times 4 \times 4 = 64\) ways to select \(k=3\) animals.

The same reasoning applies when we want to make an ordered selection of \(k\) items from a size-\(n\) collection with replacement. There are \(n\) ways to select the first item, then again \(n\) ways to select the second item, and so on, until \(k\) items have been selected. Therefore, Theorem 2.1 tells us that there are \(n^k\) ways to select the \(k\) items.

Corollary 2.1 (With replacement, order matters) If order matters and we select with replacement, there are \(n^k\) ways to select \(k\) items from a collection of \(n\) unique items.

Corollary 2.1 enables us to count the number of different possible outcomes an experiment that involves repeating a smaller experiment many times can have.

Example 2.2 (Repeated die rolls) Consider the experiment of rolling a six-sided die \(n\) times. This experiment’s sample space consists of tuples \((x_1, \dots, x_n)\) where each \(x_i\), the result of the \(i\)th die roll, takes an integer value from \(1\) to \(6\) (inclusive). These tuples, however, correspond exactly to the different ways of making an ordered selection of \(n\) items from the set \(\{1, 2, 3, 4, 5, 6\}\) with replacement. Therefore, Corollary 2.1 tells us there are exactly \(6^n\) outcomes.

2.2.2 Without Replacement, Order Matters

We’ll now consider making an ordered selection of items without replacement, meaning that each item can only be selected once.

Again, suppose that we want to select \(k = 2\) animals from the following collection of \(n=4\) animals:

We select one of the four animals to be our first animal:

But now, because we are selecting without replacement, we cannot select the same animal again. For each of our first selections, there are only three animals we can select to be our second animal:

In total, we see that there are \(4 \times 3 = 12\) different ways to select the two animals.

What if we want to select a third animal? The third animal must be different from the previously two selected animals. Thus, for each of these two-animal selections, there are only \(2\) possible choices for the third animal, making for a total of \(4 \times 3 \times 2 = 24\) ways to select \(k=3\) animals .

Again, the same reasoning applies to the general case. Suppose we want to make an ordered selection of \(k\) items from a size-\(n\) collection without replacement. There are \(n\) ways to select the first item, then \(n-1\) ways to select the second item (because it must differ from the first item), then \(n-2\) ways to select the third item (because it must differ from the first two items), and so on, until \(k\) items have been selected. Therefore, Theorem 2.1 tells us there are \(n \times (n-1) \times \dots (n - k + 1)\) ways to select the \(k\) items.

Prior to formally stating the result, we recall that \(n!\) (pronounced “\(n\) factorial”) is defined to be
\[n! = n \times (n-1) \times \dots \times 1 \] when \(n\) is a positive integer, and \(0!\) is defined to be \(1\).

Corollary 2.2 (Without replacement, order matters) If order matters and we select without replacement, there are \[\frac{n!}{(n-k)!} = n \times (n-1) \times \dots \times (n-k+1) \] ways to select \(k \leq n\) items from a collection of \(n\) unique items.

Corollary 2.2 enables us to count the number of ways we can order \(n\) objects. A particular arrangement or ordering of objects is referred to as a permutation of the objects.

Example 2.3 (Counting permutations) How many ways are there to order \(n\) objects? Ordering the objects correpsonds exactly to selecting \(n\) objects (from the total collection of \(n\) objects) without replacement and in some particular order. Corollary 2.2 tells us that there are \(n!/(n-n)! = n!/0! = n!\) ways of doing so.

The result from Example 2.3 informs us of how many outcomes there would be in a more general version of the random babies experiment from Example 1.6.

Example 2.4 (Returning random babies) Consider the random babies example (Example 1.6) from Chapter 1, but now imagine that there are \(n\) babies and \(n\) corresponding sets of parents. How many different ways are there to return the babies to the parents? If we fix some ordering of the parents, then returning the babies amounts to ordering them: the first baby in the ordering goes to the first couple, the second baby to the second, so on and so forth. Each baby ordering corresponds to a unique way of returning the babies, and vice-versa. Example 2.3 tells us there are \(n!\) possible orderings, so there must be \(n!\) ways of returning the babies.

2.2.3 Without Replacement, Order Doesn’t Matter

Perhaps the most useful variation of our problem is when we make an unordered selection of items without replacement.

Again, we’ll consider the collection of \(n=4\) animals

but now we’ll consider making an unordered selection of \(k=3\) animals without replacement. We can make this selection by specifying a size-\(3\) subset of the animals, each possible one resulting from choosing an animal to leave out:

The approach of leaving out an animal only works when \(k=n-1\), and we’ll need a more general approach to tackle other cases. Recall from earlier that there are \(24\) different ways of making an ordered selection of \(k=3\) animals without replacement. Because there are \(3! = 6\) ways of ordering \(k = 3\) animals (see Example 2.3), we can partition the ordered selections into size-\(6\) groups that select the same animals (just in different orders). Each group corresponds naturally to one way of selecting \(k=3\) animals without order:

We see that there are \(6\) times as many different ordered selections as unordered selections, and therefore \(24/6 = 4\) different unordered selections of \(k=3\) animals.

What if we want to make \(k=2\) unordered selections? We know from before that there are \(12\) different ordered selections of two animals. Example 2.3 tells us that there are \(2!=2\) ways to order any two animals, and we can thus partition these ordered selections into size-\(2\) groups that share the same animals. Each group corresponds to a unique way of selecting \(k=2\) animals without order, and vice-versa. Therefore, there should be \(12/2 = 6\) unordered ways of selecting the \(k=2\) animals. We list them here:

This approach generalizes easily to any \(n\) and \(k\). Corollary 2.2 tells us that there are \(n!/(n-k)!\) ways to make an ordered selection of \(k\) items from a size-\(n\) collection without replacement. Because there are \(k!\) ways to order \(k\) animals (see Example 2.3), we can partition these ordered selections into size-\(k!\) groups that share the same animals. Each group corresponds to one unique way of making an unordered selection of \(k\) animals without replacement, and vice-versa. Therefore, there must be \(n!/((n-k)!k!)\) different ways of making an unordered selection of \(k\) items without replacement.

Prior to formally stating the result, we recall that, for two non-negative integers \(n \geq k\), \[{n \choose k} = \frac{n!}{(n-k)!k!}\] We refer to \(n \choose k\) as “\(n\) choose \(k\)” because making an unordered selection of \(k\) items without replacement from a size-\(n\) collection can be viewed as “choosing” \(k\) of the items.

Corollary 2.3 (Without replacement, order doesn’t matter) If order doesn’t matter and we select without replacement, there are \({n \choose k}= \frac{n!}{(n-k)! k!}\) ways to select \(k \leq n\) items from a collection of \(n\) unique items.

Selecting items without replacement and without regard for ordering is a crucial step in many counting problems.

Example 2.5 (Exactly four sixes in six rolls) Consider the experiment of rolling a six-sided die six times. How many outcomes have exactly four sixes? Let’s write each outcome as a tuple \((x_1, x_2, x_3, x_4, x_5, x_6)\), where \(x_i\) is the value of the \(i\)th die roll. We can take three actions to construct the tuples with exacty four sixes: (1) select four of the \(x_i\) to be \(6\), (2) set the left-most remaining \(x_i\) to be an integer between \(1\) and \(5\) (inclusive), and (3) set the final remaining \(x_i\) to be an integer between \(1\) and \(5\) (inclusive). Each way of taking these actions corresponds to a unique tuple with exactly four sixes, and vice-versa. The first action amounts to choosing four of the six slots, so Corollary 2.3 tells us there are \({6 \choose 4} = 15\) ways to perform it. There are then \(5\) ways of performing the second action, and also \(5\) of performing the third. Therefore, by Theorem 2.1, there are \(15 \times 5 \times 5 = 375\) ways of taking the three actions and, correspondingly, \(375\) outcomes with exactly four sixes.

2.2.4 With Replacement, Order Doesn’t Matter

Finally, we consider the case where we select items with replacement and the order of selection doesn’t matter. Such selections are characterized by the number of times we select each item. For example, the \(10\) different ways to select \(k=2\) of the \(n=4\) animals

with replacement but without regard for order are given by the tables:

In general, it turns out that there are \({n + k - 1 \choose n-1}\) ways to make an unordered selection of \(k\) items from a size-\(n\) collection with replacement.

Corollary 2.4 (With replacement, order doesn’t matter) If order doesn’t matter and we select with replacement, there are \({n + k - 1 \choose n-1}\) ways to select \(k\) items from a collection of \(n\) unique items.

Corollary 2.4 tends to come up less in practice, but the “stars and bars” method used to prove it is itself instructive.

Proof of Corollary 2.4

Imagine there are \(n\) distinguishable buckets and \(k\) indistinguishable balls, and we want to know the number of different ways we can put the balls in the \(n\) buckets. We’re indifferent to the order that we put the balls in the buckets. All that matters is the number of balls that end up in each bucket at the end. Taking the number of balls in the \(i\)th bucket to be the number of times we select the \(i\)th item, each way of putting balls in buckets corresponds to a unique way of making an unordered selection of \(k\) items from a size-\(n\) collection with replacement, and vice-versa.

We can represent the \(k\) balls with stars. If \(k = 10\), then we have \(10\) balls: \[\huge\star\star\star\star\star\star\star\star\star\star\huge\] To decide which balls go in which buckets, we can place \(n-1\) bars anywhere along sequence of stars. For example, when \(n=5\), the placement \[\huge\star\mid\star\star\star\star\star\mid\mid\star\star\star\mid\star\huge\] corresponds to putting \(1\) ball in the first bucket, \(5\) in the second, \(0\) in the third, \(3\) in the fourth, and \(1\) in the fifth. Each way of placing the \(n-1\) bars corresponds to a unique way of putting balls in buckets, and vice-versa. For general \(n\) and \(k\), the full sequence of stars and bars has \(n + k - 1\) entries (\(k\) stars and \(n - 1\) bars). Placing the bars amounts to choosing \(n-1\) of these entries to be bars. Corollary 2.3 tells us there \({n+k-1 \choose n-1}\) ways of doing so.

2.2.5 Summary

Table 2.1 summarizes the results from this section and will serve as a nice reference for when you’re solving combinatorics problems.

Table 2.1: Number of ways to select \(k\) items from a collection of \(n\) unique items

	Order Matters	Order Doesn’t Matter
Without Replacement	\(\frac{n!}{(n-k)!}\)	\(n \choose k\)
With Replacement	\(n^k\)	\(n + k -1 \choose n-1\)

2.3 Examples

With our new tools for counting, we can compute some interesting and non-trivial probabilities. To start, we give a correct solution to Cardano’s problem (Example 1.1) from Chapter 1.

Example 2.6 (Solving Cardano’s problem) Cardano asked how many rolls of a (fair, six-sided) die are needed for the probability of seeing at least one six to be 50%. To answer his question, we count the number of total possible outcomes, as well as the number of outcomes with at least one six.

How many possible outcomes are there?

Rolling a die \(k\) times is like making an ordered selection of \(k\) items from \(\{ 1, 2, \dots 6\}\) with replacement. Corollary 2.1 tells us that there are \(6^k\) such outcomes.

How many outcomes are there with at least one six?

It is easier to count the number of outcomes with no sixes. The outcomes with no sixes correspond exactly to the different ways of making an ordered selection of \(k\) items from \(\{1, 2, 3, 4, 5\}\) with replacement, so Corollary 2.1 tells us there are \(5^k\) of them. Since this the number of outcomes with no sixes, the remaining \(6^k - 5^k\) outcomes have least one six.

Finally, to calculate the probability, we divide one count by the other: \[ P(\{\text{at least one six}\}) = \frac{6^k - 5^k}{6^k} = 1 - \left(\frac{5}{6}\right)^k. \]

Now, we can answer Cardano’s question by trying different values of \(k\):

• When \(k=3\), \(P(\{\text{at least one six} \}) \approx 0.421\).
• When \(k=4\), \(P(\{\text{at least one six} \}) \approx 0.518\).

This verifies our claim in Example 1.1.

Next, we examine a classic brainteaser: what is the probability that two people in a room share a birthday? The answer may be surprising!

Example 2.7 (Birthday Problem) Imagine a room of \(k\) people. What is the probability that at least two people share a birthday?

First, we make two assumptions:

1. There are 365 days of the year (with apologies to people born on Feburary 29!).

2. All configurations of the \(k\) people’s birthdays are equally likely. (This would be violated, for example, if there were twins in the room, who must have the same birthday.)

How many possible outcomes are there?

If we label the days of the year as \(\{ 1, 2, \dots, 365 \}\), then the number of possible configurations of the \(k\) birthdays is the number of ordered ways to select \(k\) items from \(n=365\) with replacement, or \(365^k\).

How many outcomes are there where at least two people share a birthday?

Perhaps it is easier to first count the number of configurations where nobody shares the same birthday. This is the number of ordered ways to select \(k\) items from \(n=365\) without replacement, or \(\frac{365!}{(365 - k)!}\). We can subtract this from the total number of configurations, \(365^k\), to obtain the number of configurations where at least two people share the same birthday.

Putting the two pieces together, the probability of a shared birthday is: \[ P(\{\text{shared birthday} \}) = \frac{365^k - 365!/(365 - k)!}{365^k} = 1 - \frac{365!}{365^k (365 - k)!}. \]

This is difficult to evaluate by hand, but easy in R. For a room of \(k=30\) people, this probability is:

In fact, it only takes \(k=23\) people to have better-than-even odds of having a shared birthday! Verify this for yourself by editing the R code above.

Our last example comes from the poker, one of the world’s most popular gambling card games. We provide a brief introduction to poker for those who are unfamiliar with the game.

A brief overview of poker

Figure 2.2: An example of each possible poker hand

Poker is a gambling card game that combines elements of luck and skill. Players gauge the strength of their hand relative to their opposition and then strategically make bets to either compel their opponents to fold or continue wagering. The winner is either the last player standing or the player holding the best hand after the final round of betting.

We will focus on five-card draw, a variant of poker in which each player always has five cards in their hand. In what follows, we list out the possible hands from best to worst. An example of each hand is given in Figure 2.2.

1. Royal Flush: Ace, king, queen, jack, and ten all of the same suit.

2. Straight Flush: Five consecutive cards of the same suit, but not a royal flush.

3. Four of a Kind (Quads): All four cards of some rank along with any other card.

4. Full House: Three cards with the same rank and two cards that share some other rank.

5. Flush: Five cards of the same suit, but not a royal flush or straight flush.

6. Straight: Five consecutive cards, but not a royal flush or straight flush.

7. Three of a Kind (Trips or Set): Three cards of the same rank and two other cards, but not a full house or four of a kind.

8. Two Pair: Two sets of two cards of the same rank and one other card, but not a three of a kind, full house, or four of a kind.

9. One Pair: Two cards of the same rank and three other cards, but not a two pair, three of a kind, full house, or four of a kind.

10. High Card: When none of the above qualifications are met, the card with the highest rank is used.
    

Example 2.8 (Probability of a full house) Supposing that all five-card hands are equally likely, what’s the probability of getting dealt a full house in five-card draw?

How many possible outcomes are there?

The number of five-card hands, ignoring the order in which the cards were dealt, is the number of unordered ways to choose \(k=5\) from \(n=52\) without replacement. Corollary 2.3 tells us that there are \(52 \choose 5\) such hands.

How many outcomes are a full house?

A full house is any hand where

1. three cards (the “set”) are of one rank and

2. two cards (the “pair”) are of another rank.

Here is how to construct a full house hand, disregarding the order of the cards in the hand:

1. select the rank of the set (\(13\) ways)

2. select the three cards in the set (\(4 \choose 3\) ways)

3. select the rank of the pair (\(12\) ways)

4. select the two cards in the pair (\(4 \choose 2\) ways)

By Theorem 2.1, the number of distinct full house hands is \[13 \times {4 \choose 3} \times 12 \times {4 \choose 2} = 3744. \]

The probability of a full house is therefore: \[P(\{\text{full house}\}) = \frac{3744}{52 \choose 5} \approx 0.0014. \]

2.4 Exercises

Exercise 2.1 (Galileo’s Problem) Coming soon!