\[
\newcommand{\or}{\textrm{ or }}
\newcommand{\and}{\textrm{ and }}
\newcommand{\not}{\textrm{not }}
\newcommand{\Pois}{\textrm{Poisson}}
\newcommand{\E}{\textrm{E}}
\newcommand{\var}{\textrm{Var}}
\]
2Techniques for Counting
\[
\def\n{\textcolor{red}{50}}
\]
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, we did this by explicitly listing out the relevant 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
Our first example illustrates the core idea behind counting. It also outlines a standardized approach for computing probabilities when outcomes are equally likely.
Example 2.1 (Random outfits) Suppose our outfit for the day is composed of three clothing items: shoes, pants, and a shirt. We have three pairs of shoes, two pairs of pants, and four different colored shirts. If we pick an outfit at random, what’s the probability that we will wear our green shirt? Since our green shirt is one of four shirts that we may pick, we may intuitively expect the answer to be \(1/4\). Let’s verify this carefully using the tools we developed in Chapter 1.
We’ll think of picking an outfit as an “experiment”, where the equally likely outcomes in our sample space \(\Omega\) are the different outfits we can make. We want to know the probability of \(A\), the event of making an outfit with a green shirt. Once we
count the number of outcomes in \(\Omega\),
count the number of outcomes \(A\),
we can apply the naive definition of probability (Definition 1.4) to compute \(P(A)\).
How many outcomes are in \(\Omega\)?
We’ll assume that any combination of shoes, pants, and a shirt make a wearable outfit. 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 in our sample space. Figure 2.1 both clearly illustrates this line of reasoning and enumerates all the different outfits.
Figure 2.1: Visual enumeration of all the possible outfits.
How many outcomes are in the \(A\)?
We can apply the same reasoning to count the number of outfits that have green shirt. To make an outfit with a green shirt, we just need to pick our pants and shoes. Each of the \(3\) pairs of shoes can be matched with \(2\) possible pairs of pants, making for \(2 \times 3 = 6\) green shirt outfits. Figure 2.1 affirms this fact.
Applying the naive definition of probability
Combining these facts, we can apply the naive definition of probability (Definition 1.4) to compute \(P(A)\):
\[
P(A) = |A|/|\Omega| = 6/24 = 1/4.
\]
Our solution to the problem in Example 2.1 uses 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
\tag{2.1}\]
unique ways to perform the \(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 equal to 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 performing the actions. Even 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.
Theorem 2.1 allows us to count the unique 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 or not we care about the order of selection 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 outcomes in an experiment that involves repeating a smaller experiment many times.
Example 2.2 (Repeated die rolls) If you roll a fair six-sided die \(n\) times, what’s the probability that you roll all sixes?
How many possible outcomes are there?
Imagine making an ordered selection of \(n\) items from the set \(\{1, 2, 3, 4, 5, 6\}\) with replacement, e.g., \[
\underbrace{3,\hspace{5pt} 1,\hspace{5pt} 3,\hspace{5pt} 2,\hspace{5pt} 5,\hspace{5pt} 6, \hspace{5pt} \dots, 2}_{n \text{ numbers }}.
\] Each way of doing so corresponds uniquely to one of the equally likely outcomes we may see after rolling a fair six-sided die \(n\) times, and vice-versa (think of the first selection as the result of the first die roll, the second as the result of the second, so on and so forth). Therefore, Corollary 2.1 tells us there are \(6^n\) possible outcomes.
How many outcomes have all sixes?
There’s only one outcome that has all sixes: \[
\underbrace{1,\hspace{5pt} 1,\hspace{5pt} 1,\hspace{5pt} 1,\hspace{5pt} 1,\hspace{5pt} 1,\hspace{5pt} \dots 1}_{n \text{ numbers }}.
\]
Applying the naive definition of probability
Putting these facts together, we can apply the naive definition of probability (Definition 1.4) to see that \[
P(\text{all sixes}) = 1/6^n.
\]
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 \(n\) objects corresponds exactly to selecting \(n\) of the 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 allows us to analyze a more general version of the random babies experiment from Example 1.6.
Example 2.4 (Returning the \(k\) eldest 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. We’ll refer to the babies as baby one, baby two, etc. If we then randomly return the babies, what’s the probability that babies one through \(k\) (inclusive) are returned to their biological parents?
How many ways are there to return the babies?
We can return the babies by ordering the parents: baby one goes to the first couple in the ordering, baby two to the second, so on and so forth. Each way of ordering the parents corresponds to a unique way of returning the babies, and vice-versa. Example 2.3 tells us there are \(n!\) possible parent orderings and there are therefore \(n!\) equally likely outcomes in our sample space.
In how many of these ways are the eldest \(k\) babies returned correctly?
If we restrict ourselves to cases where the first \(k\) babies are returned correctly, then the number of ways we can return the babies is exactly the number of ways we can return the remaining \(n-k\) babies to the remaining \(n-k\) parents. Our earlier reasoning tells us there are \((n-k)!\) ways of doing so.
Applying the naive definition of probability
Putting these facts together, we can apply the naive definition of probability (Definition 1.4) to see that \[
P(\text{correctly return first } k \text{ babies}) = (n-k)!/n!.
\]
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. Our next example demonstrates how it comes up when we solve a harder version of the problem from Example 2.2.
Example 2.5 (Exactly one-sixth of the rolls are six) Suppose we roll a fair six-sided die \(6n\) times. What’s the probability that exactly one-sixth of these roll are sixes?
To make the problem more concrete we’ll suppose that \(n=\n\), so we want to know the probability of seeing \(\n\) sixes in \(6\cdot \n = 300\) rolls
How many possible outcomes are there?
Example 2.2 tells us that there are \(6^{(6 \cdot \n)}\) equally likely outcomes in our sample space.
In how many of these outcomes are exactly \(1/6\)th of the rolls sixes?
We want to count the number of outcomes that have exactly \(\n\) sixes. Each way of taking the following two consecutive actions corresponds to a unique such outcome, and vice-versa:
Choose \(\n\) of the \(6 \cdot \n\) die rolls to be sixes. Corollary 2.3 tells us that there are \({{6 \cdot \n} \choose {\n}}\) ways of doing this.
Set the remaining die \(5 \cdot \n\) rolls to be numbers between \(1\) and \(5\) (inclusive). Following the reasoning of Example 2.2, the number of ways we can do this is the same as the number of ways we can make \(5 \cdot \n\) ordered selections from the set \(\{1, \dots, 5\}\) with replacement. Corollary 2.4 tells us that there are \(5^{(5 \cdot \n)}\) ways to do so.
By Theorem 2.1, there are therefore \(5^{(5 \cdot \n)}\cdot {{6 \cdot \n} \choose {\n}}\) outcomes with exactly \(\n\) sixes.
Applying the naive definition of probability
Applying the naive definition of probability (Definition 1.4), we find that
This result may come as a bit of a surprise. Since the probability of rolling a six is \(1/6\), the proportion of sixes we observe as we repeatedly roll the die should be \(\approx 1/6\). Then, why is the probability of seeing \(n= \n\) sixes in \(6 \cdot \n = 300\) rolls so low?
The gap in our reasoning becomes even more glaring if we throw the die more times. As the plot generated by the below code snippet shows, the probability of seeing \(n\) sixes in \(6n\) throws tends to zero as we increase \(n\).
So why is this happening? It is true that if we roll the die many times we’ll see roughly\(n\) sixes in \(6n\) rolls. But, if we roll many times, there will also be increased variability in the number of sixes we see. Simply put, when we roll the die a large number of times, e.g, \(6 \cdot \n = 300\) times, there are lots of different numbers of sixes that might come up (we may see \(0\), \(1\), \(2\), \(\dots\) all the way up to \(300\) sixes). As a result, the probability that we see exactly\(100\) sixes (or any specific number of sixes, for that matter) will be small, even though the probability that we see around\(100\) sixes will still be large.
In Exercise 2.2 we ask you to show that the probability of seeing exactly \(k\) sixes in \(6 \cdot \n = 600\) throws is
\[
P(\text{exactly } k \text{ sixes}) = {{6 \cdot \n}\choose{k}} \left(\frac{1}{6}\right)^{k} \left(\frac{5}{6}\right)^{6 \cdot \n - k}
\] The below code snippet plots this probability for every \(k\) between \(0\) and \(2 \cdot \n = 100\). The plot shows that:
Out of all the numbers, you are most likely to see \(\n\) sixes.
It is very likely that you’ll observe some number of sixes that is close to \(\n\).
Still, the probability of observing exactly any specific number of sixes is small.
As you change \(n\) from \(n = \n\) to larger values, you’ll see that our earlier claims become more pronounced. The number of sixes we’re likely to observe become more tightly concentrated around \(n\), which is one-sixth the number of total throws, and the probability of observing some specific number of sixes continues to shrink. We’ll revisit this example and study it more precisely in Chapter 11 once we cover the variance of random variables.
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. This result comes up less in practice, but the “stars and bars” method used to prove it is itself a good example application of Corollary 2.3. We’ve provided the proof as optional reading below.
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.
Proof
Imagine there are \(n\) distinguishable buckets and \(k\) indistinguishable balls, and we want to know the number of different ways we can put the \(k\) balls into the \(n\) buckets. All we care about is the number of balls that end up in each bucket; the order in which they arrive is irrelevant. 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 can 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 Combinatorial Identities
In this section, we present a few well known combinatorial identities. These identities will come in handy later on when we discuss discrete random variables, and their proofs will reinforce ideas from the previous section.
Proposition 2.1 (Choosing the complement) For nonnegative integers \(n\) and \(k\) with \(k \leq n\),
Imagine we want to choose \(k\) people from a group of \(n\) people to form a sports team. Corollary 2.3 tells us there are \({n}\choose{k}\) ways of doing so.
Alternatively, Corollary 2.3 tells us that there are \({n}\choose{n-k}\) ways to choose the \(n-k\) people who will not be on the team. Since choosing who’s not on the team is exactly the same as choosing who is on the team, \({n}\choose{k}\) and \({n}\choose{n-k}\) must be equal.
Of course, this identity is easy to prove using basic algebra: \[ {{n} \choose {n-k}} = \frac{n!}{(n - k)! (n - (n - k))!} = \frac{n!}{(n-k)! k!} = {{n} \choose k}. \] However, the counting proof is more memorable and insightful.
Proposition 2.2 (Choosing a captain) For positive integers \(n\) and \(k\) with \(k \leq n\),
Imagine we want to both (1) choose \(k\) people from a group of \(n\) people to form a sports team and (2) designate one of the people as team captain. We can do this by first designating a captain and then picking the remaining members of the team:
Choose one person from the collection of \(n\) to be team captain. Corollary 2.3 tells us there are \({{n}\choose{1}} = n\) ways to do this.
Choose \(k-1\) people from the remaining \(n-1\) people to form the remainder of the team. Corollary 2.3 tells us there are \({{n-1}\choose{k-1}}\) ways to do this.
Theorem 2.1 therefore tells us that there are \(n {{n-1}\choose{k-1}}\) ways to put together our team and pick a captain.
Alternatively, we could’ve first formed the team and then designated one of the team members to be captain:
Choosing \(k\) people from the collection of \(n\) to be on the team. Corollary 2.3 tells us there are \({{n}\choose{k}}\) ways of doing this.
Choosing one person from the \(k\) people on the team to be team captain. Corollary 2.3 tells us there are \({{k}\choose{1}} = k\) ways of doing this.
Therefore, by Theorem 2.1, \(k {{n}\choose{k}}\) is also the number of ways we can form our team and pick a captain. This is sufficient to imply the result.
Unlike the previous two identities, giving an algebraic proof of this next identity is very challenging. Giving a combinatorial proof of it, however, is manageable, and we ask you do so as part of Exercise 2.3.
Proposition 2.3 (Vandermonde’s identity) For nonnegative integers \(m, n,\) and \(k\) with \(k \leq n + m\),
We close out the chapter by using our new tools to 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’ll find the probability of seeing at least one six when we roll a fair six-sided die \(n\) times.
How many possible outcomes are there?
When rolling a fair six-sided die \(n\) times, Example 2.2 tells us that there are \(6^n\) possible equally likely outcomes.
How many outcomes have at least one six?
It is easier to count the number of outcomes with no sixes. Following the same reasoning from Example 2.2, the outcomes with no sixes correspond exactly to the different ways of making an ordered selection of \(n\) items from \(\{1, 2, 3, 4, 5\}\) with replacement, so Corollary 2.1 tells us there are \(5^n\) of them. The remaining \(6^n - 5^n\) outcomes have least one six.
Applying the naive definition of probability
Applying the naive definition of probability (Definition 1.4), we find that \[
P(\{\text{at least one six}\}) = \frac{6^n - 5^n}{6^n} = 1 - \left(\frac{5}{6}\right)^n.
\]
Now, we can answer Cardano’s question by trying different values of \(n\):
When \(n=3\), \(P(\{\text{at least one six} \}) \approx 0.421\).
When \(n=4\), \(P(\{\text{at least one six} \}) \approx 0.518\).
Since \(P(\{\text{at least one six} \})\) increases as \(n\) increases, the above computations imply that we we need to roll the die at least four times for the chance of seeing a six to be at least \(0.5\), verifying our claim from Chapter 1.
Next, we examine a classic brainteaser: what is the probability that two people in a room share a birthday? The answer is surprising!
Example 2.7 (Birthday Problem) In a room of \(2 \leq n \leq 365\) randomly selected people, what is the probability that at least two people share a birthday?
First, we make two assumptions:
We only select people born during the standard \(365\) day calendar year (with apologies to people born on \(\text{Feburary 29th}\)!).
All configurations of the \(n\) people’s birthdays are equally likely.
How many possible outcomes are there?
Imagine ordering the selected people by name (and break ties however you’d like). The number of different birthday configurations is the number of ordered ways we can select \(n\) items from the \(365\) item set \(\{\text{Jan 1}, \text{Jan 2}, \dots, \text{Dec 31}\}\)with replacement. The first selection is the birthday of the first person in the ordering, the second selection is the birthday of the second person, so on and so forth. Corollary 2.1, tells us that there are \(365^n\) ways to perform this selection.
How many outcomes are there where at least two people share a birthday?
It is easier to count the number of configurations where nobody shares the same birthday. It’s the same as the number of ordered ways we can select \(n\) items from \(\{\text{Jan 1}, \text{Jan 2}, \dots, \text{Dec 31}\}\)without replacement. Selecting without replacement ensures that no two people share the same birthday. Corollary 2.2 tells us there are \(365!/(365 - n)!\) such selections. In the remaining \(365^n - \frac{365!}{(365 - n)!}\) configurations, at least two people share the same birthday.
Applying the naive definition of probability
Applying the naive definition of probability (Definition 1.4), we find that the probability of a shared birthday is \[
P(\{\text{shared birthday} \}) = \frac{365^n - 365!/(365 - n)!}{365^n} = 1 - \frac{365!}{365^n (365 - n)!}.
\]
This is difficult for us to evaluate by hand, but easy for a computer. For a room of \(n=30\) people, this probability is:
In fact, it only takes \(n=23\) people to have better-than-even odds of having a shared birthday! Verify this for yourself by editing code above.
To help you better understand how this probability varies as a function of the number of people in the room, the below code snippet plots \(P(\{\text{shared birthday}\})\) for \(n\) ranging from \(2\) to \(80\).
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.
Royal Flush: Ace, king, queen, jack, and ten all of the same suit.
Straight Flush: Five consecutive cards of the same suit, but not a royal flush.
Four of a Kind (Quads): All four cards of some rank along with any other card.
Full House: Three cards with the same rank and two cards that share some other rank.
Flush: Five cards of the same suit, but not a royal flush or straight flush.
Straight: Five consecutive cards, but not a royal flush or straight flush.
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.
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.
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.
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 different five-card hands are there?
In poker, a hand is the same regardless of the order the cards are dealt. Therefore the number of five-card hands is exactly the number of unordered ways we can choose \(k=5\) cards from the \(n=52\) card deck without replacement. Corollary 2.3 therefore tells us that there are \(52 \choose 5\) five-card hands.
How full houses are there?
A full house is any hand composed of
three cards of one rank (a set),
two cards of another rank (a pair).
Each way of taking the following four consecutive actions corresponds to a unique full house, and vice-versa:
From the \(13\) different ranks, choose the rank of the set. Corollary 2.3 tells us that there are \({13 \choose 1} = 13\) ways to do this.
From the \(4\) different suits, choose \(3\) for the cards in our set. Corollary 2.3 tells us that there are \({4 \choose 3} = 4\) ways to do this.
From the \(12\) remaining unselected ranks, choose the rank of the pair. Corollary 2.3 tells us that there are \({12 \choose 1} = 12\) ways to do this.
From the \(4\) possible suits, choose \(2\) suits for the cards in our pair. Corollary 2.3 tells us that there are \({4 \choose 2} = 6\) ways to do this.
By Theorem 2.1, the number of distinct full house hands is therefore \[{13 \choose 1} \cdot {4 \choose 3} \cdot {12 \choose 1} \cdot {4 \choose 2} = 13 \cdot 4 \cdot 12 \cdot 6 = 3744. \]
Applying the naive definition of probability
Applying the naive definition of probability (Definition 1.4), we find that the probability of being dealt a full house is \[P(\{\text{full house}\}) = 3744/{{52}\choose{5}} \approx 0.0014. \] The chance of getting a full house is barely higher than a tenth of a percent!
2.5 Exercises
Exercise 2.1 (Galileo’s problem) Coming soon!
Exercise 2.2 (Binomial probability) Coming soon!
Exercise 2.3 (Vandermonde’s identity)
Exercise 2.4 (Hockey stick identity) Prove the hockey stick identity using a counting argument:
