Counting Principles

(This is a section in the notes here.)

Counting in Probability. If each outcome is equally likely, i.e. $\mathbb P( \omega ) = p$ for all $\omega \in \Omega$ , then since

$1 = \sum_{\omega \in \Omega } \mathbb P( \omega ) = \sum_{\omega \in \Omega } p= |\Omega | p$ (where $|\Omega|$ is the number of outcomes in the set $\Omega$ ) it must be that $\begin{aligned} \label{count1} \mathbb P(\omega) = \frac{1}{| \Omega |} \,\qquad \text{ for all } \omega \in \Omega .\end{aligned}$

Further, since $\mathbb P ( E ) = \sum_{\omega \in E} \mathbb P(\omega)$ then $\begin{aligned} \label{count2} \mathbb P ( E) = \frac{\left| E \right| }{|\Omega |} \, .\end{aligned}$ So from the last two display equations above, we see that, when outcomes are equally likely, then to calculate probabilities we need to be able to count the number of outcomes in different sets.

Some Counting Rules. 1,2,3,4,… aside, we cover the following counting methods

Multiplication
Factorials
Permutations
Combinations

Card Game. We consider the probability of winning a card game in the following setting:

A card dealer has $5$ cards $A,K,Q,4,2$ .
You are dealt $3$ cards.
You win if you get $A,K,Q$ .

The probability of winning depends on what we mean by “the cards being dealt” and what is means by to “get A,K,Q”.

Multiplication.

Rules of the the card game. Suppose we play the card game in the following way

The dealer shuffles the deck. Shows a random card. Replaces it in the deck. And then repeats.
You win if you get $A$ then $K$ and then $Q$ , in that order.

The probability of winning. We can calculate the probability of winning as follows. The set of outcomes can be written as $\begin{aligned} \Omega = \{ (C_1,C_2,C_3) : C_1,C_2,C_3 \in \{ A,K,Q,4,2\} \}\, .\end{aligned}$ I.e. it is the set of triplets $(C_1,C_2,C_3)$ where the first, second and third card are in $\{ A,K,Q,4,2\}$ . If holds that

$\begin{aligned} | \Omega | = 5^3 = 125 \,.\end{aligned}$ Since there is only one winning hand among these $125$ equally likely possibilities, we have $\begin{aligned} \mathbb P ( \text{ winning } ) = \frac{1}{125}\,. %\end{aligned}$

Screenshot 2021-11-18 at 14.24.37

Note $| \Omega | = 5^3$ holds because.. Notice once we fix the first two cards $(C_1, C_2)$ there are $5$ different values for the third card. So the number of triplets $(C_1,C_2,C_3)$ is five times the number of pairs $(C_1,C_2)$ . By the same logic, once we fix the first card $C_1$ there are five values that $C_2$ can take. So the number of pairs $(C_1,C_2)$ is 5 times the number of values $C_1$ can take. Finally $C_1$ can take $5$ values. So we see the number of triples is $5\times 5 \times 5$ . See Figure 1.

Figure 1. This card game has 5 possibilities at each stage.

In General. For sets $\Omega_1$ ,…., $\Omega_k$ , we define the product set by $\begin{aligned} \prod_{i=1}^K \Omega_i := \big\{ (\omega_1,...,\omega_k) : \omega_1 \in \Omega_1,...,\omega_k \in \Omega_k) \big\}\,. %\end{aligned}$

Screenshot 2021-11-18 at 14.27.55

Following the argument as above we can see that $\begin{aligned} \left|\prod_{i=1}^k \Omega_i\right| = \prod_{i=1}^k | \Omega_i | \,. %\end{aligned}$

Screenshot 2021-11-18 at 14.28.14

Factorials

Rules of the the card game. Suppose we play the card game in the following way

The dealer shuffles the deck. Shows a random card. Replaces it in the deck. And then repeats.
You win if you get $A$ then $K$ and then $Q$ , in any order.

So now $(Q,K,A)$ is a now a winning hand as well as $(A,K,Q)$ .

The probability of winning. Since the way that the dealer deals has not changed we know the probability of any hand, that is, $\begin{aligned} \mathbb P ( (A,K,Q) ) = \cdots = \mathbb P( ( Q,K,A) ) = \frac{1}{125}\, . %\end{aligned}$

Screenshot 2021-11-18 at 14.28.48

So if we want to calculate the probability of winning we need to calculate the number of events with a winning hand. It is not hard to check that $\begin{aligned} \{\text{ winning } \} = \{ (A,K,Q), (A,Q,K), (K,A,Q), (K,Q,A),(Q,A,K),(Q,K,A) \} %\end{aligned}$

Screenshot 2021-11-18 at 14.29.27

That is there are $6$ winning hands. So the probability of winning is $\begin{aligned} \mathbb P( \text{ winning } ) = \frac{6}{125}\, . %\end{aligned}$

Screenshot 2021-11-18 at 14.29.31

Six winning hands holds because.. Notice there are $3$ possibilities for the first card, where we are still on for a win, namely, $A$ , $K$ , $Q$ . We can suppose without any lost generality that the first card was $Q$ , then for the 2nd card there are $2$ possibilities that can be dealt where we can still win namely $A$ and $K$ . Again we can suppose that the card was $K$ , then for the 3rd card there is $1$ possibility where we win, namely, $A$ . So there if we look across the three stages of this card game there are $3$ possibilities for the 1st card then for each of these there are $2$ possibilities for the 2nd card and then $1$ for the final card, which gives $3\times 2 \times 1 = 6$ winning hands. See Figure 2

Screenshot 2021-11-18 at 14.31.10

Figure 2. There are initially $3$ potentially winning first cards, and the one less at each stage.

In general. Given a set $C$ with $|C|=n$ , which we can think of as a deck of cards. We are interested in counting the different of ways of dealing out the deck: $\begin{aligned} F := \{ (c_1,c_2,...,c_n) : c_1,....,c_n \in C\text{ where }c_i \neq c_j\text{ for all } i \neq j \} %\end{aligned}$

Screenshot 2021-11-18 at 14.31.43

In general, following the argument as above it holds that $\begin{aligned} |F| = n \times (n-1) \times (n-2) \times .... \times 2 \times 1 %\end{aligned}$

Screenshot 2021-11-18 at 14.31.48

Definition [Factorial] Given a positive integer $n$ , $n$ factorial is defined to be

$n ! := n\times (n-1) \times (n-2) \times .... \times 2 \times 1$ (By convention we define $0!:=1$ )

So $n!$ counts the number of ways we can order a set of $n$ elements.

Permutations

Rules of the the card game. Suppose we play the card game in the following way

The dealer shuffles the deck. Takes out a random card, but does to put it back in the deck . And then repeats.
You win if you get $A$ then $K$ and then $Q$ , in that order.

The probability of winning. In this case, there is only one winning hand $(A,K,Q)$ . However, the set of hands has now changed as we can not longer repeat any card. This is similar to factorials, however, as you may recall, for a factorial we deal out all the cards, whereas here we only deal three out of the five cards. So here the sample space is

$\begin{aligned} \Omega = \{ (C_1,C_2,C_3) : C_1,C_2,C_3 \in \{ A,K,Q,4,2\} \text{ where } C_i \neq C_j \text{ for all } i \neq j \}\, .\end{aligned}$

As we will argue shortly $| \Omega | = 60 \,.$ Thus $\begin{aligned} \mathbb P( \text{ winning } ) = \frac{1}{60}\, . %\end{aligned}$

Screenshot 2021-11-18 at 14.34.50

It holds that $| \Omega | = 60$ because.. Similar our discussion on factorials, there are $5$ possibilities for the first card dealt. Suppose for instance the first card is $A$ , although the same argument would hold equally for any other card. Now once the first card is dealt there are $4$ remaining possibilities for the second card, namely, $\{ K,Q,4,2\}$ . Suppose for instance the second card is a $K$ . Then there are $3$ possibilities for the third, namely, $\{ Q,4,2\}$ . In total this leads to $5\times 4 \times 3 = 60$ possible ways of dealing $3$ cards from a pack of $5$ cards. See Figure 3

Figure 3. There are initially $5$ potentially winning first cards, and the one less at each stage of the $3$ stages.

In general. Given a set $C$ with $|C|=n$ , which we can think of as a deck of cards. We are interested in counting the different of ways of dealing out $k$ cards without replacement: $\begin{aligned} P := \{ (c_1,c_2,...,c_k) : c_1,....,c_k \in C\text{ where }c_i \neq c_j\text{ for all } i \neq j \} %\end{aligned}$

Screenshot 2021-11-18 at 14.36.39

In general, following the argument as above it holds that $\begin{aligned} |P| = n \times (n-1) \times (n-2) \times .... \times (n-k+2) \times (n-k+1) %\end{aligned}$

Definition [Permutation] Given non-negative integers $n$ and $k$ with $k\leq n$ the permutation is defined to be

$P^n_k := n \times (n-1) \times (n-2) \times .... \times (n-k+2) \times (n-k+1)$ or more compactly using factorials: $P^n_k := \frac{n!}{(n-k)!}$

So $P^n_k$ counts the number of ways we can order $k$ elements from a set of $n$ .

Combinations.

Rules of the the card game. Suppose we play the card game in the following way

The dealer shuffles the deck. Takes out a random card, but does not put it back in the deck . And then repeats.
You win if you get $A$ then $K$ and then $Q$ , in any order.

The probability of winning. There are two ways to think about the above game. We focus first on the way that is most similar to out previous argument on permutations.

As before the ways of dealing the cards is exactly the same as our discussion on permutations.

$\begin{aligned} \Omega_1 = \{ (C_1,C_2,C_3) : C_1,C_2,C_3 \in \{ A,K,Q,4,2\} \text{ where } C_i \neq C_j \text{ for all } i \neq j \}\, .\end{aligned}$ Thus $|\Omega_1 | = 5!/2!= 5\times 4 \times 3 = 60$ for the same reason as previously. Further since the order of the cards $\{ A, K, Q \}$ does not matter. For the same reason as our discussion on factorials there are $3! = 3\times 2 \times 1=6$ winning hands. Thus $\begin{aligned} \label{eq:combprob} \mathbb P( \text{ winning }) = \frac{3! \cdot 2!}{5!}=\frac{6}{60} = \frac{1}{10} \, . %\end{aligned}$

Screenshot 2021-11-18 at 14.38.32

A further way of thinking: removing the order… Rather than thinking of removing cards one at a time, we could think of taking out three cards at the same time from the deck of five cards, without paying attention to the order that they came out. Here we are interest in the set of three cards removed, e.g. $\{ A, K, Q \} = \{ Q, K, A \}$ , rather than the order that the cards where taken out, e.g. $(A,K,Q) \neq (Q,K,A)$ . Here we could then think of a slightly different sample space: $\begin{aligned} \Omega_2 = \{ \{C_1,C_2,C_3 \} : C_1,C_2, C_3 \in \{ A,K,Q,4,2 \} \text{ where } C_i \neq C_j \text{ for all } i \neq j \} %\end{aligned}$

Screenshot 2021-11-18 at 14.39.12

We can think of this as dividing the deck of cards $\{ A, K, Q, 4,2 \}$ into two decks: the cards dealt out, and the cards still in the deck, E.g. $\begin{aligned} \text{(the deck of cards)\qquad} \overset{|}{A}, \overset{\circ}{K}, \overset{|}{Q}, \overset{\circ}{4} ,\overset{|}{2} & \rightarrow \{ \overset{|}{A}, \overset{|}{Q}, \overset{|}{2} \}\tag{cards dealt out} \\& \searrow \{ \overset{\circ}{K},\overset{\circ}{2} \} \tag{cards in the deck } %\end{aligned}$

Screenshot 2021-11-18 at 14.39.47

Here “ $|$ ” indicates the card is dealt and “ $\circ$ ” indicates that the card stays in the pack.

In addition to the above argument that gave in above. A way to think about counting the number of outcomes in $\Omega_2$ . Is to imagine we deal out the whole deck. The first three cards are given to the players and the last two cards remain with the dealer. The number of ways of dealing out the deck we know is $5!$ from our discussion on factorials. This over-counts as we don’t care what the order is for the first $3$ cards dealt or for the last $2$ cards that remain in the deck. For example suppose we are dealt $A,K,Q$ , there are $3!$ ways of dealing out $A,K,Q$ as the first three cards, and, for each way the $A,K,Q$ is dealt, for the cards $4,2$ still in the deck, there are $2!$ ways of ordering these cards. In other words $5!$ over counts by a factor of $3! \times 2!$ . From this we can see that $\begin{aligned} | \Omega_2 |= \frac{5!}{3!2!} = 10\, . %\end{aligned}$

Screenshot 2021-11-18 at 14.40.16

There is only one outcome in $\Omega_2$ where we win so $\begin{aligned} \mathbb P( \text{ winning } ) = \frac{1}{10}\,. %\end{aligned}$

Screenshot 2021-11-18 at 14.43.15

In General. Given a set $C$ with $| C| = n$ , which we can think of as a deck of cards. We are interested in the number of ways of dealing $k$ cards: $\begin{aligned} D := \{ \{c_1,c_2,...,c_k\} : c_1,....,c_k \in C\text{ where }c_i \neq c_j\text{ for all } i \neq j \} %\end{aligned}$

Screenshot 2021-11-18 at 14.43.48

In general the argument above gives that $\begin{aligned} |D| = \frac{n!}{k! (n-k)!}\,. %\end{aligned}$

Screenshot 2021-11-18 at 14.43.51

Definition [Combination] Given a non-negative integers $n$ and $k$ with $k \leq n$ , the combination of $n$ choose $k$ is defined to be

$C^n_k := {n \choose k} := \frac{n!}{k! (n-k)!} \, .$

So $C^n_k$ counts the number of ways we can chose $k$ elements from a set of $n$ .

Multinomials. In combinations the cards were dealt to one person (and the dealer) what if we wanted to consider dealing more hands. It is not hard to check that if there are $n$ cards and $k_1,...,k_m$ are the number of cards dealt to each player. (here we think of $k_m$ as the number of cards that the dealer has left.) Note $k_1 + ... +k_m = n$ . Then the natural extension of the combination, which gives the number of ways of dealing cards, as above is a multinomial which is given by $\begin{aligned} { n \choose k_1,...,k_m } = \frac{n!}{k_1! k_2! ... k_m!}\,. %\end{aligned}$

Screenshot 2021-11-18 at 14.44.38

Additional Remarks. $^\star$

Here are a few additional remarks.
(These remarks are not examinable. So you may choose to skip, but it might yet be helpful).

A bit more interpretation for combinations. Notice earlier we thought of a combination as dividing up the deck of five cards:

$\overset{1}{A}, \overset{0}{K}, \overset{1}{Q}, \overset{0}{4} ,\overset{1}{2}$ Here “ $1$ ” indicates the card is dealt and “ $0$ ” indicates that the card stays in the pack. So we could think of $C^n_k$ as counting the number of strings of $n$ digits with exactly $k$ ones. E.g. For $C^5_3=10$ because there are 10 such strings:

(For this reason you can see that $\sum_{k=0}^n C^n_k = 2^n$ .)

Polynomials, Pascals Triangle. Consider the expansion of $(x+1)^n$ . Notice that $\begin{aligned} \label{eq:Poly} (1+x)^n = {n \choose 0} + {n \choose 1} x + {n \choose 2} x^2 + ...+ {n \choose n} x^n \, . %\end{aligned}$

Screenshot 2021-11-18 at 14.45.18

Why? Well for instance if we look at the $x^3$ term in $(1+x)^5$ then to get one $x^3$ term we need to include three $x$ terms and two $1$ terms from the expansion of $(1+x)^5$ . For instance here is one example: $\begin{aligned} (1+\overset{|}{x}) (\overset{\circ}{1}+x) ( 1+\overset{|}{x}) ( \overset{\circ}{1}+ x) (1+\overset{|}{x}) \, .\end{aligned}$ This is the same as $\overset{|}{A}, \overset{\circ}{K}, \overset{|}{Q}, \overset{\circ}{4} ,\overset{|}{2}$ from earlier so the number of such terms is $C^5_3$ . This why the coefficients are combinations.

The Binomial Theorem. Notice from the above result we can see that $\begin{aligned} { n+1 \choose k } = { n \choose k} + { n \choose k-1} %\end{aligned}$

Screenshot 2021-11-18 at 14.46.00

Hint: $(1+x)^{n+1} = (1+x)^n (1+x)$ . This is called the Binomial Theorem.

Pascal’s Triangle. If we repeatedly apply the above formula we get a nice shape for listing out combinations: $\begin{gathered} 1 \\ 1\quad 1\\ 1 \quad 2 \quad 1\\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ 1 \quad 5 \;\;\; 10 \;\;\; 10 \quad 5 \quad 1\\ \vdots\end{gathered}$ This is called Pascal’s Triangle.

Stirlings Formula. When $n$ is large, $n!$ can be a really big number. (A good reason to have the exclamation mark.) We can quantify how much with the following formula $n! \sim \sqrt{(2\pi n)} e^{-n} n^n$ Here the $\sim$ means that the ratio between the two numbers approaches $1$ as $n$ gets large.

Examples

Example. What is the probability of winning the jackpot in the national lottery (lotto)?
(Recall the national lottery $6$ random balls from a set of $59$ balls. You win if you get all $6$ correct, regardless of order.)

Answer. The number of draws in $C^{59}_6 = 45057474$ and only one wins so $\mathbb P ( \text{win} ) = 1/45057474$ .

Example. What is the probability of winning the jackpot in Euromillions?
(Recall that Euromillions has $5$ main numbers between $1$ and $50$ and $2$ “lucky stars” between $1$ and $12$ .

Answer. The total number of combinations for the main numbers is $C^{50}_5 = 2118,760$ and for the lucky stars $C^{12}_2 = 66$ . So in total $C^{50}_5 \times C^{12}_2 = 139,838,160$ . So the probability is $1/139838160$ .

Example. How many distinct words can be made out of $A,B,B,A$ .

Answer. $C^4_2 = 6$ . (Like above think of the positions $(1,2,3,4)$ of letters as cards and a card being dealt being the same as being assigned an $A$ in that position.)

Example. How many distinct words can be made out of $B,A,N,A,N,A$ .

Answer. $6!/(1!3!2!) = 60$ . (Same principle as previous question but now is a multinomial.)

Example [Birthday Paradox] In a football game there are 23 players (including the referee). What is the probability that two or more players have the same birthday.¹

Answer. Note that $\begin{aligned} \mathbb P ( \text{two or more same birthday } ) = 1 - \mathbb P ( \text{all different} ) \, . %\end{aligned}$

Screenshot 2021-11-18 at 14.48.25

So we need to count the number of ways the birthdays can be organized and the number of ways that all birthdays can be different. Notice that the sample space has size $| \Omega | = (365)^{23} \, .$ (I.e. Notice that the number of birthday for the 1st player is 365, and for the 2nd player it is 365 and so forth), whereas the number of ways the players can have different birthdays is a permutation: $\begin{aligned} | \{\text{\,all different\,}\} | = P^{365}_{23} \, . %\end{aligned}$

Screenshot 2021-11-18 at 14.48.59

(I.e. Notice that the number of birthday for the 1st player is 365, and for the 2nd player it is 364 – because player $1$ ’s birthday is taken– and so forth).

Thus $\begin{aligned} \mathbb P (\text{all different} ) = \frac{P_{23}^{365}}{365^{23}} = 0.4927 %\end{aligned}$

Screenshot 2021-11-18 at 14.49.41

and $\begin{aligned} \mathbb P ( \text{two or more same birthday } ) = 0.5073 \, . %\end{aligned}$

The result may be quite surprising as you would think it unlikely to share a birthday with any individual. However, there are many pairs of birthdays between the players. These balance out to give 50% chance of two players having the same birthday.

Example. A parking inspector randomly inspects $7$ different cars in a car park with $35$ cars where $5$ cars have not bought a ticket. If the inspector inspects a car without a ticket then the car receives a fine. Find the probability that exactly two cars are fined.

Answer. The number of ways of inspecting $7$ cars out of $35$ is $C^{35}_{7}$ . I.e. $\begin{aligned} |\Omega | = {35 \choose 7} = 6724520 %\end{aligned}$

Screenshot 2021-11-18 at 14.51.24

We can suppose, without loss of generality, that the first $5$ cars have not bought a ticket. If $2$ cars are fined, the inspector must choose to inspect $2$ among these first $5$ cars and must choose to inspect $5$ the remaining $30$ cars: E.g. $\begin{aligned} \underbrace{ \overset{I}{1}, \overset{I}{2}, 3,4, 5,}_{\text{no ticket}} \underbrace{\overset{I}{6},7,8,\overset{I}{9},\overset{I}{10},11,12,\overset{I}{13},14,15,16,17,...,31,32,\overset{I}{33},34,35}_{\text{ticket}}\, . %\end{aligned}$

Screenshot 2021-11-18 at 14.51.52

Here “ $I$ ” means inspected. The are $C^5_2$ ways of choosing the two cars without a ticket, and $C^{30}_5$ ways of choosing the five cars with a ticket. Since any way of choosing the first two cars does not influence our choices for remaining five. For this reason we multiply the both combinations to give: $\begin{aligned} |\{\text{ two cars fined }\}| = { 5 \choose 2} \times { 30 \choose 5} = 1425060 \, . %\end{aligned}$

Screenshot 2021-11-18 at 14.52.21

Thus $\begin{aligned} \mathbb P (\text{ two cars fined } ) = \frac{{ 5 \choose 2} \times { 30 \choose 5}}{{35 \choose 7}} = 0.212 \, . %\end{aligned}$

Screenshot 2021-11-18 at 14.52.25

You can ignore Feb 29th on leap years.↩

Multiplication.

Factorials

Permutations

Combinations.

Additional Remarks.

Examples

Share this:

Like this:

Leave a Reply Cancel reply

Additional Remarks. $^\star$