Math Background

Lesson 4 Chapter 2

To tackle and solve the probability problem, there is always a need to count how many elements available in the event and sample space. Here, we discuss some important counting principles and techniques.

Get the source code for this lesson

Counting all possible outcomes

Let's consider the special case of having two experiments as $\mathcal{P}$ and $\mathcal{E}$ . The basic principle states that if one experiment ( $\mathcal{P}$ ) results in N possible outcomes and if another experiment ( $\mathcal{E}$ ) leads to M possible outcomes, then conducting the two experiments will have $M \times N$ possible outcome, in total. Assume experiment $\mathcal{E}$ has M possible outcomes as $\{\mathcal{E}_1,\mathcal{E}_2,\ldots,\mathcal{E}_M\}$ and $\mathcal{P}$ has N possible outcomes as $\{\mathcal{P}_1,\mathcal{P}_2,\ldots,\mathcal{P}_N\}$ .

It is easy to prove such a principle for its special case. All you need in to count all possible outcomes of two experiments:

$\begin{Bmatrix}(\mathcal{E}_1,\mathcal{P}_1),(\mathcal{E}_1,\mathcal{P}_2),\ldots,(\mathcal{E}_1,\mathcal{P}_N) \\ (\mathcal{E}_2,\mathcal{P}_1),(\mathcal{E}_2,\mathcal{P}_2),\ldots,(\mathcal{E}_2,\mathcal{P}_N)\\ \hdots \\ (\mathcal{E}_M,\mathcal{P}_1),(\mathcal{E}_M,\mathcal{P}_2),\ldots,(\mathcal{E}_M,\mathcal{P}_N)\end{Bmatrix}$

The generalized principle of counting can be expressed as below:

Generalized Basic Principle of Counting

Assume we have q different experiments with the corresponding number of possible outcomes as $\{N_1,N_2,\ldots,N_q\}$ . Then we can conclude that there is a total of outcomes $N_1 \times N_2 \times \ldots \times N_q$ for conducting all q experiments.

Permutation

What is a permutation? Suppose we have three persons called Michael, Bob, and Alice. Assume the three of them stay in a queue. How many possible arrangements we have? Take a look at the arrangements as follows:

$\left\{\begin{matrix}Michael, Bob, Alice\\ Michael, Alice, Bob\\ Alice, Bob, Michael\\ Alice, Michael, Bob\\ Bob, Michael, Alice\\ Bob, Alice, Michael\end{matrix}\right.$

As above, you will see six permutations. Right? But, we cannot always write all possible situations! We need some math. The intuition behind this problem is that we have three places to fill in a queue when we have three persons. For the first place, we have three choices. For the second place, there are two remaining choices. Finally, there is only one choice left for last place! So we can extend this conclusion to the experiment that we have $n$ choices. Hence, we get the following number of permutations:

$n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1 = n!$

which you can compute by Python as below:

View and run code in Google Colab.

NOTE: The descending order of multiplication from $n$ to $1$ is as above (the product of all positive integers less than or equal to n), denote as $n!$ , and called $n$ factorial.

Combination

The combination stands for different combinations of objects from a larger set of objects. For example, assume we have a total number of $n$ objects. With how many ways can we select $r$ objects from that $n$ objects? Let's get back to the above examples. Assume we have three candidates named Michael, Bob, and Alice, and we only desire to select two candidates. How many different combinations of candidates exist?

$\left\{\begin{matrix}Michael, Bob,\\ Michael, Alice\\ Alice, Bob\end{matrix}\right.$

Let's get back to the general question: How many selections we can have if we desire to pick $r$ objects from $n$ objects?

Combination

The number of unordered selections of $r$ objects from $n$ objects is denoted and calculated as:

$\binom{n}{r}=\frac{n!}{r!(n-r)!}$

NOTE: In the combination selection, we referred to the unordered selection. It means, the combination of $\{A,B,C\}$ is the same as $\{C,B,A\}$ i.e., the order does NOT matter.

View and run code in Google Colab.

The above definition can be generalized.

Generalization

Assume we have $n$ objects, $r$ groups of objects each with $n_i$ objects, and $n_1 + n_2 + \ldots + n_r = n$ . The number of unordered possible divisions of n objects into these $r$ distinct groups can be calculated as below: