Example. A lottery allows to select a two-digit number. Each digit may be either 1, 2, or 3. Show all possible out comes. Show all possible outcomes.
Solution. There are three different ways to choose the first digit. For each choice of the first digit, there are three different ways of choosing the second digit (a tree diagram would visually show this). Hence, there are nine possible outcomes of the two-digit numbers and they are
$${11,12,13,21,22,23,31,32,33}$$
Theorem [The Fundamental Principle of Counting]. If a choice consists of $k$ steps, of which the fist can be made in $n_1$ ways, for each of these the second can be made in $n_2$ ways, …, and for each of these the $k$th can be made in $n_k$ ways, then the whole choice can be made in $n_1n_2\cdots n_k$ ways.
Proof. Let $S_i$ denote the set of outcomes for the $i$th task, $i=1,\cdots,k$, and let $n(S_i)=n_i$. Then the set of outcomes for the entire job is
$$S_1\times S_2\times\cdots\times S_k={(s_1,s_2,\cdots,s_k)| s_i\in S_i,\ 1\leq i\leq k}$$
Now, we show that
$$n(S_1\times S_2\times\cdots\times S_k)=n(S_1)n(S_2)\cdots n(S_k)$$
by induction on $k$. Let $k=2$. For each element in $S_1$, there are $n_2$ choices from the set $S_2$ to pair with the element. Thus, $n(S_1\times S_2)=n_1n_2$. Suppose that
$$n(S_1\times S_2\times\cdots\times S_m)=n(S_1)n(S_2)\cdots n(S_m)$$
For each $m$-tuple in $S_1\times S_2\times\cdots\times S_m$, there are $n_{m+1}$ choices of elements in the set $S_{m+1}$ to pair with the $m$-tuple. Thus,
\begin{align*} n(S_1\times S_2\times\cdots\times S_{m+1})&=n(S_1\times S_2\times\cdots\times S_m)n(S_{m+1})\\ &=n(S_1)n(S_2)\cdots n(S_{m+1})\ (\mbox{by the induction hypothesis}) \end{align*}
Therefore, by the induction principle,
$$n(S_1\times S_2\times\cdots\times S_k)=n(S_1)n(S_2)\cdots n(S_k)$$
Example. In designing a study of the effectiveness of migraine medicines, 3 factors were considered.
- Medicine (A, B, C, D, Placibo)
- Dosage Level (Low, Medium, High)
- Dosage Frequency (1, 2, 3, 4 times/day)
In how many possible ways can a migraine patient be given medicine?
Solution. $5\cdot 3\cdot 4=60$ different ways.
Example. How many license-plates with 3 letters followed by 3 digits exist?
Solution. There are $10\cdot 10\cdot 10=1000$ ways to choose 3 digits. For each $3$ digit, there are $26\cdot 26\cdot 26=17,576$ ways to choose 3 letters. Hence, the number of ways to make license-plates is $17,270,576,000$.
Example. How many numbers in the range $1000-9999$ have no repeated digits?
Solution. There are 9 different ways to choose the first digit. For each choice of the first digit, there are 9 different ways to choose the second digit without repeating the first digit. For each choice of the first and the second digits, there are 8 different ways to choose the third digit without repeating the first and the second digits. For each choice of the first, second and third digits, there are 7 different ways to choose the fourth digit without repeating the first, second, third digits repeated. Therefore, the answer is $9\cdot 9\cdot 8\cdot 7=4,536$ ways.
Example. How many license-plates with 3 letters followed by 3 digits if exactly one of the digits is 1.
Solution. \begin{align*} 26\cdot 26\cdot 26\cdot(1\cdot 9\cdot 9+9\cdot 1\cdot 9+9\cdot 9\cdot 1)&=26\cdot 26\cdot 26\cdot 3\cdot 9\cdot 9\\ &=4,270,968 \end{align*}
ways.
References:
- Marcel B. Finan, A Probability Course for the Actuaries
- Sheldon Ross, A First Course in Probability, Fifth Edition, Prentice Hall, 1997