8.1 Equally Likely Outcomes and Counting Rules

In the case of a finite sample space $\Omega$ with equally likely outcomes, the probability of any event $A\subseteq\Omega$ is \[ \textrm{P}(A) = \frac{|A|}{|\Omega|} = \frac{\text{number of outcomes in $A$}}{\text{number of outcomes in $\Omega$}} \qquad{\text{when outcomes are equally likely}} \] Computing probabilities in the equally likely case reduces to just counting outcomes. In previous sections we often counted outcomes by enumerating them in a list. Of course, listing all the outcomes is unfeasible unless the sample space is very small. In this section we will see some formulas for counting in a few common situations.

Example 8.1 I’m serving ice cream to my kids. They can choose to have a bowl or a cone with a single scoop from one of four different flavors.

How many different ways could I serve the ice cream? (For example, peppermint in a cone, birthday cake in a bowl, etc)
Now suppose they can either add rainbow or chocolate sprinkles¹³³ or not. How many different ways could I serve the ice cream? (For example, peppermint in a cone with chocolate sprinkles, birthday cake in a bowl with rainbow sprinkles, etc.)
Now suppose the kids who requested bowls could choose whether to have whipped cream on top. Is the number of different ways I could serve the ice cream equal to the answer to the previous part multiplied by two?

Solution. to Example 8.1

Show/hide solution

Each flavor can be served in 2 ways, cone or bowl. Since there are 4 flavors, the number of ways to serve is $4\times 2 = 8$.
Each of the 8 pairs from the previous part can be served in 3 ways, with rainbow sprinkles, with chocolate sprinkles, or without sprinkles. So the number of ways to serve is now $4\times 2 \times 3 = 24$.
No. Only the bowls can get whipped cream so we can’t just multiply 24 by 2. Of the 24 possibilities from the previous part, 12 are in bowls. So these 12 can be served with or without whipped cream, but the other 12 in cones can only be served without whipped cream. The number of possibilities is now $12\times 2 + 12 = 36$.

All of the counting rules we will see are based on multiplying like in the previous example.

Multiplication principle for counting. Suppose that stage 1 of a process can be completed in any one of $n_1$ ways. Further, suppose that for each way of completing the stage 1, stage 2 can be completed in any one of $n_2$ ways. Then the two-stage process can be completed in any one of $n_1\times n_2$ ways. This rule extends naturally to a $\ell$-stage process, which can then be completed in any one of $n_1\times n_2\times n_3\times\cdots\times n_\ell$ ways.

In the multiplication principle it is not important whether there is a “first” or “second” stage. What is important is that there are distinct stages, each with its own number of “choices”. In Example 8.1, there was a bowl/cone stage, an ice cream flavor stage, and a sprinkle stage.

The multiplication principle confirms the number of outcomes in a few situations we enumerated previously.

Roll a four-sided die twice and record the rolls in sequence; then there are $4\times 4 = 16$ possible outcomes. If a six-sided die is rolled twice then there are $6^2=36$ possible outcomes.
Flip a coin three times and record the results in sequence; then there are $2\times2\times2 = 8$ possible outcomes. If the coin is flipped four times there are $2^4=16$ possible outcomes.

Example 8.2 Suppose the board of directors of a corporation has identified 5 candidates — Ariana, Beyonce, Cardi, Drake, Elvis — for three executive positions: chief executive officer (CEO), chief financial officer (CFO), and chief operating officer (COO). In the interest of fairness, the board assigns 3 of the 5 candidates to the positions completely at random. No individual can hold more than one of the positions.

When calculating probabilities below, consider the sample space of all possible executive teams.

How many executive teams are possible?
What is the probability that Ariana is CEO, Beyonce is CFO, and Cardi is COO?
What is the probability that Ariana is CEO, Cardi is CFO, and Beyonce is COO?
What is the probability that Ariana is CEO and Beyonce is CFO?
What is the probability that Ariana is CEO?
What is the probability that Ariana is an executive?

Solution. to Example 8.2

Show/hide solution

There are 5 choices for CEO, then 4 choices for CFO, then 3 choices for COO. So there are $5\times 4 \times 3 = 60$ possible teams. The sample space consists of 60 possible outcomes. The order in which we make the choices doesn’t matter. We could have picked the CFO first then COO then CEO, still resulting in $5\times 4\times3$ possible outcomes. What is important is that there are 3 distinct stages. Choosing Ariana as CEO is not the same as choosing Ariana as CFO.
If the selections are made uniformly at random, each of the 60 possible teams is equally likely. So the probability of any particular team, like this one, is 1/60.
The probability of any particular team is 1/60. But note that Ariana as CEO, Beyonce as CFO, and Cardi as COO is a different outcome than Ariana as CEO, Cardi as CFO, and Beyonce as COO
To construct a team with Ariana as CEO and Beyonce as CFO, there is one possible choice for CEO (Ariana), one possible choice for CFO (Beyonce) and three possible choices for COO, resulting in $1\times 1\times 3$ teams that have Ariana as CEO and Beyonce as CFO. Since the outcomes are equally likely, the probability is 3/60.
To construct a team with Ariana as CEO, there is one possible choice for CEO (Ariana), four possible choicea for CFO, and three possible choices for COO, resulting in $1\times 4\times 3=12$ teams that have Ariana as CEO. Since the outcomes are equally likely, the probability is 12/60=1/5. This makes sense because any of the five people is equally likely to be CEO.
The probability that Ariana is CEO is 12/60, similarly for CFO and COO. Since Ariana can’t hold more than one positive, these events are disjoint, so the probability that Ariana is CEO or CFO or COO is $3(12/60) = 3/5$.

In the previous example, the “stage” at which the person was chosen was important: there was a CEO stage, a CFO stage, and a COO stage. Choosing Ariana at the CEO stage, Beyonce at the CFO stage, and Cardi at the COO stage was a different outcome than choosing Ariana at the CEO stage, Cardi at the CFO stage, and Beyonce at the COO stage. When what happens at each stage matters, an outcome is often called an “ordered” arrangement. Again, “order” is perhaps a misnomer; it’s not that there’s a “first” and “second” and “third” stage, but rather that there are three distinct stages — CEO, CFO, COO.

The multiplication principle applies directly to situations which involve “ordered” or stage-wise counting, like the executive example. We employed the multiplication principle to find that there are $5\times 4\times 3=60$ possible executive teams. The following formula generalizes this result.

Number of ordered arrangements. The number of ordered arrangements of $k$ items, selected without replacement from a set of $n$ distinct items is \[ n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!} \]

Recall the factorial notation: $m!=m(m-1)(m-2)\cdots (3)(2)(1)$. For example, $5!=5\times4\times3\times2\times1=120$. By definition, 0!=1.

Example 8.3 Your boss is forming a committee of 3 people for a new project team, and 5 people — Ariana, Beyonce, Cardi, Drake, Elvis— have volunteered to be on the committee. In the interest of fairness, 3 of the 5 people will be selected uniformly at random to form the committee.

How is this situation different from the executive team example?
How many possible committees consist of Ariana, Beyonce, Cardi? How many executive teams consisted of Ariana, Beyonce, Cardi?
How many different possible committees of 3 people can be formed from the 5 volunteers?

Solution. to Example 8.3

Show/hide solution

There were distinct stages in the executive team example; selecting Ariana as CEO, Beyonce as CFO, and Cardi as COO was counted as a different outcome than selecting Ariana as CEO, Cardi as CFO, and Beyonce as COO. But when forming the committee we only need to know which three people were selected, not which stage or “order” they were selected in.
There is only one committee that consists of Ariana, Beyonce, Cardi. But there were 6 executive teams that consisted of Ariana, Beyonce, Cardi. To have a team with these three people, there are 3 choices for who is CEO, then 2 choices for COO, then 1 choice for COO, for a total of $3\times2\times1=6$ possible teams consisting of Ariana, Beyonce, Cardi.
There were 60 possible “ordered” outcomes, but counting in an “ordered” way overcounts the number of committees by a factor of 6. Counting in an “ordered” way we would count 6 teams consisting of Ariana, Beyonce, Cardi, but we only want to count the possible committee once. Therefore, the total number of committees is 60/6 = 10.

The following is the relationship between “ordered” and “unordered” counting.

{ \[\begin{align*} \left(\text{number of \emph{ordered} selections of $k$ from $n$}\right) & = \left(\text{number of \emph{unordered} selections of $k$ from $n$}\right)\\ &\quad \times\left(\text{number of ways of arranging the $k$ items in order}\right). \end{align*}\] }

We have seen how to compute the number of “ordered” arrangements. How many ways are there of arranging $k$ items in order?

Number of permutations. The number of ways of arranging $k$ items in order is \[ k\times (k-1)\times (k-2)\times\cdots\times 3\times 2\times1 = k! \] This can be seen as an application of the multiplication rule, or as a special case of the number of “ordered” arrangements rule with $n=k$. Permutation is another word for an ordering of $k$ items.

We now have what we need to count the number of ordered arrangements. We know that the number of ordered arrangements is $n!/(n-k)!$, that the number of ways of arranging the $k$ items is $k!$ and so using the relationship noted above, we must have that the number of unordered arrangements is $(n!/(n-k)!)/k!$. More precisely,

Number of combinations. The number of ways to choose $k$ items without replacement from a group of $n$ distinct items where order does not matter, denoted $\binom{n}{k}$, is \[ \binom{n}{k} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!} \]

The quantity on the right is just a compact way of representing the quantity in the middle. But since factorials can be very large, it’s best to use the quantity in the middle to compute. In R: choose(n, k). In Python: scipy.special.comb(n, k)

An unordered selection of $k$ items from a group of $n$ is sometimes called a combination, so $\binom{n}{k}$ is sometimes called the number of combinations. The symbol $\binom{n}{k}$ is by definition equal to the quantity in the middle above. It is read as “$n$ choose $k$” and is referred to as a binomial coefficient. For example, there are “5 choose 3” committees in the previous example

\[ \binom{5}{3} = \frac{5!}{3!(5-3)!} = \frac{(5)(4)(3)}{3!} = \frac{60}{6} = 10. \]

Example 8.4 Your boss is forming a committee of 3 people for a new project team, and 5 people — Ariana, Beyonce, Cardi, Drake, Elvis— have volunteered to be on the committee. In the interest of fairness, 3 of the 5 people will be selected uniformly at random to form the committee.

Find the probability that the committee consists of Ariana, Beyonce, and Cardi.
Find the probability that Ariana and Beyonce are on the committee.
Find the probability that Ariana is on the committee.

Solution. to Example 8.4

Show/hide solution

If the selections are made uniformly at random each of the $\binom{5}{3} = 10$ possible committees is equally likely. So the probability of any particular committee, like this one, is 1/10.
Split the five people into two groups: group 1 with Ariana and Beyonce and group 2 with the other three. In order to have a committee with Ariana and Beyonce, we need to choose 2 people from group 1 and 1 person from group 2. There is only way to choose the 2 people from group 1, and there are three possibilities for the person selected from group 2. Each of these three people can be partnered with Ariana and Beyonce to form the committee. Therefore, the probability is 3/10. Written another way \[ \frac{\binom{2}{2}\binom{3}{1}}{\binom{5}{3}} = \frac{(1)(3)}{10} \]
Intuitively, this should be 3/5, the same as the probability that Ariana was an executive. Split the five people into two groups: group 1 with Ariana and group 2 with the other four. In order to have a committee with Ariana, we need to choose Ariana from group 1 and 2 people from group 2. There is only way to choose the Ariana from group 1, and there are $\binom{4}{2}=6$ possibilities for the two people selected from group 2. Each of these pairs can be partnered with Ariana to form a committee with Ariana on it. Therefore, the probability is 6/10. Written another way \[ \frac{\binom{1}{1}\binom{4}{2}}{\binom{5}{3}} = \frac{(1)(6)}{10} \]

The strategy of partitioning is often useful in problems involving “unordered” sampling without replacement. Notice that in each of the problems above the denominator had one binomial coefficient, corresponding to the total number of selections. Then the totals were partitioned into some number of groups, determined by the event of interest. The numerator of the probability will have one binomial coefficient for each group; the sums of the “tops” of the binomial coefficients in the numerator will equal the top of the binomial coefficient in the denominator, and the the sums of the “bottoms” of the binomial coefficients in the numerator will equal the bottom of the binomial coefficient in the denominator.

Example 8.5 In the Powerball lottery, a player picks five different whole numbers between 1 and 69, and another whole number between 1 and 26 that is called the Powerball. In the drawing, the 5 numbers are drawn without replacement from a “hopper” with balls labeled 1 through 69, but the Powerball is drawn from a separate hopper with balls labeled 1 through 26. The player wins the jackpot if both the first 5 numbers match those drawn, in any order, and the Powerball is a match.

How many different possible winning draws are there?
What is the probability the next winning number is 6-7-16-23-26, plus the Powerball number, 4.
What is the probability the next winning number is 1-2-3-4-5, plus the Powerball number, 6.
The Powerball drawing happens twice a week. Suppose you play the same Powerball number, twice a week, every week for over 50 years. Let’s say you purchase a ticket for 6000 drawings in total. What is the probability that you win at least once?
Instead of playing for 50 years, you decide only to play one lottery, but you buy 6000 tickets, each with a different Powerball number. What is the probability that at least one of your tickets wins? How does this compare to the previous part? Why?
Each ticket costs 2 dollars, but the jackpot changes from drawing to drawing. Suppose you buy 6000 tickets for a single drawing. How large does the jackpot need to be for your expected profit to be positive? To be $100,000? (We’re ignoring inflation, taxes, and any changes in the rules.)

Solution. to Example 8.5

Show/hide solution

There are $\binom{69}{5}$ ways of choosing the 5 numbers from the 69, and each of these can be paired with one of the 26 possible Powerballs. Therefore, there are $\binom{69}{5}(26) = 292,201,338$ possible winning numbers.
Each of the possible winning numbers is equally likely, so the probability is $1/292,201,338\approx 3\times 10^{-9}$. See Example 1.14 and the discussion following it.
Each of the possible winning numbers is equally likely. Remember, don’t confuse a general event with a specific outcome; see Example 1.13.
The drawings are independent. The probability that you win at least once is $1 - (1-1/292201338)^{6000}\approx 0.00002$. If many people each play 6000 drawings, about 2 in every 100,000 people win will at least once.
If you play 6000 different numbers, the events that each different number wins are disjoint. So the probability you win at least once is $6000/292201338\approx 0.00002$. This is about the same as the probability in the previous part. When you play 6000 different independent drawings, there is a possibility that you win multiple times, so the events of winning in each different drawing are not disjoint. But the probability of winning multiple lotteries is so small that it’s negligible. The probability of winning any single drawing is about 1 in 300 million. The probability of winning any two drawings is about 1 in 85 quadrillion.
You pay $12,000 in total. Let $w$ be the value of the jackpot. Then your expected profit is $w(6000/292201338)-12000$. So we must have $w>584,402,676$ for the expected profit to be positive. Sometimes, but not often, the jackpot does get this high; even so, this just guarantees that your expected profit is positive. In order for your expected profit to be greater than just $100,000, the jackpot must be over 5 billion dollars, and the largest jackpot ever was 1.6 billion. The moral: there are better things to do with $12,000 dollars.

Example 8.6 To get some intuition behind binomial coefficients, answer the following without using any formulas or doing any calculations.

What is $\binom{n}{n}$?
What is $\binom{n}{0}$?
What is $\binom{n}{1}$?
What is the relationship between $\binom{n}{k}$ and $\binom{n}{n-k}$?
Explain why \[\begin{equation*} \binom{m+n}{k} = \sum_{j=0}^k \binom{m}{j} \binom{n}{k-j} \end{equation*}\]
Explain why \[\begin{equation} 2^n = \sum_{k=0}^n\binom{n}{k} \end{equation}\]

Solution. to Example 8.6

Show/hide solution

$\binom{n}{n}=1$. There is only one way to select all $n$ items.
$\binom{n}{0}=1$. There is only one way to select none of the $n$ items.
$\binom{n}{1}=n$. If you are just selecting 1 of $n$ items, then are $n$ ways to do it, one for each of the $n$ items.
$\binom{n}{k}=\binom{n}{n-k}$. Suppose you are selecting a committee of size $k$ from $n$ peoeple. The number of ways to choose $k$ of the $n$ people to include on the committee is equivalent to the number of ways to choose $n-k$ of the $n$ people to exclude from the committee.
Suppose you are choosing a committee of size $k$ from a group consisting of $m$ faculty and $n$ students. The left side $\binom{m+n}{k}$ is the number of possible committees. There can be anywhere from 0 to $k$ faculty on the committee. If there are $j$ faculty there must be $k-j$ students, so $\binom{m}{j} \binom{n}{k-j}$ is the number of ways to select a committee with exactly $j$ faculty. The right side sums the number of committees of each faculty/student breakdown to find the number of committees overall.
Suppose you are forming a subset from $n$ items. There are $2^n$ possible subsets, including the empty set. This follows from the multiplication principle since each of the $n$ items can either be included or excluded in the subset. (Label the items 1 to $n$; at the “include item 1 in the subset?” stage there are two possible choices, etc, so the total number of choices is $2^n$.) $\binom{n}{k}$ is the number of subsets of size $k$; sum the numbers of subsets of each size to get the overall number of subsets.

8.1.1 Summary

Multiplication principle for counting. Suppose that stage 1 of a process can be completed in any one of $n_1$ ways. Further, suppose that for each way of completing the stage 1, stage 2 can be completed in any one of $n_2$ ways. Then the two-stage process can be completed in any one of $n_1\times n_2$ ways. This rule extends naturally to a $k$-stage process, which can then be completed in any one of $n_1\times n_2\times n_3\times\cdots\times n_k$ ways.
Number of ordered arrangements. The number of ordered arrangements of $k$ items, selected without replacement from a set of $n$ distinct items is \[ n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!} \]
Number of combinations. The number of ways to choose $k$ items without replacement from a group of $n$ distinct items where order does not matter, denoted $\binom{n}{k}$, is \[ \binom{n}{k} = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!} \]

a.k.a., jimmies ↩︎