8.01 Counting techniques

The probability of an event occurring is:

$P(event)=\frac{\text{number of favourable outcomes}}{\text{total possible outcomes}}$P(event)=number of favourable outcomestotal possible outcomes​

When calculating probabilities, using counting techniques to determine possible outcomes, makes the process easier. This chapter will focus on a number of these counting techniques.

The fundamental counting principle

Consider tossing a coin then rolling a six-sided dice. Let's look at all the possible outcomes by constructing a tree diagram. We will consider tossing the coin and rolling the dice as consecutive events.

The sample space of tossing then coin and then rolling a dice is:

$\left\{\text{H1, H2, H3, H4, H5, H6, T1, T2, T3, T4, T5, T6}\right\}${H1, H2, H3, H4, H5, H6, T1, T2, T3, T4, T5, T6}

We can see there is a total of $12$12 outcomes. We can also see from the tree diagram for each of the $2$2 possibilities for the coin toss there are $6$6 possibilities for the roll of the dice. We can calculate the total number of outcomes without determining the sample space by considering the number of outcomes of each event and multiplying them together, to account for all the possibilities, as follows:

Let's consider an application where the power of this method of counting becomes clear. In this example, it would be very inefficient to work out the number of outcomes by first determining the sample space.

Consider the number plate below. It has the format of three letters followed by three numbers.

To work out the total number of possible number plates, including those with repeated numbers and letters, we need to consider the possible outcomes for each position on the number plate.

For each letter, there are $26$26 possibilities. For each number, there are $10$10 possibilities (the numbers $0-9$0−9).

Therefore, the number of possibilities for each position is shown below:

For each of the $26$26 possibilities for the first letter, there are $26$26 for the second letter and for each of these combinations there are $26$26 possibilities for the third letter, and so on. We can multiply the possibilities for each position (we consider the selection of the letter or number of each position an event) to find the total as follows:

This is called the fundamental counting principle (or multiplication principle) and can be stated as follows:

Worked example

Example 1

A password contains six digits, which can be lower case letters or the numbers $0-9$0−9. Calculate the total number of possible passwords if each letter and number can only be used once.

Think: To use the fundamental counting principle, we need to first determine the number of possibilities for each digit. 

Do: There are $6$6 digits, with $26$26 possible letters and $10$10 possible numbers. Therefore, for each digit, there are $36$36 possibilities. However, The number of possibilities reduces by $1$1 for each subsequent digit as we can't use the same letter or number twice. Hence, the total number of possible passwords is:

Practice questions

Question 1

Question 2

Question 3

What are factorials?

In 1808, the French mathematician Christian Kramp wrote "I use the very simple notation $n!$n! to designate the product of numbers decreasing from $n$n to unity, i.e. $n!=n\times\left(n-1\right)\times\left(n-2\right)\times\left(n-3\right)\times...\times3\times2\times1$n!=n×(n−1)×(n−2)×(n−3)×...×3×2×1".

Today we refer to the product as "$n$n factorial". So $5!=5\times4\times3\times2\times1=120$5!=5×4×3×2×1=120 and $6!=6\times5\times4\times3\times2\times1=720$6!=6×5×4×3×2×1=720. 

Factorials grow quickly. For example, $18!=6402373705728000$18!=6402373705728000. The number $100!$100! has $24$24 zeros at the right hand end of the number.  In fact, the number $59!$59! is larger than the current estimate of atoms in the universe!

Simplifying expressions involving factorials

Since $8!$8! is $8\times7!$8×7!, then an expression like $8!+7!$8!+7! can be simplified as $8\times7!+7!=7!\left(8+1\right)=9\times7!$8×7!+7!=7!(8+1)=9×7!. Similarly, $\frac{8!}{7!}=\frac{8\times7!}{7!}=8$8!7!​=8×7!7!​=8. 

More generally, an expression like $\frac{n!}{\left(n-1\right)!}$n!(n−1)!​ can be simplified to $\frac{n\times\left(n-1\right)!}{\left(n-1\right)!}=n$n×(n−1)!(n−1)!​=n.

Similarly, $\frac{n!}{\left(n-3\right)!}=n\times\left(n-1\right)\times\left(n-2\right)$n!(n−3)!​=n×(n−1)×(n−2), and this type of simplification can be useful in solving certain equations. For example, to solve $n!=120\times\left(n-3\right)!$n!=120×(n−3)! for $n$n, we might proceed as follows:

The factorisation of the cubic equation was completed using polynomial division techniques. The quadratic factor cannot be broken into linear factors over the reals. Hence $n=6$n=6. However, since $n$n is an integer, you might notice, at the third line, that $6\times5\times4=120$6×5×4=120, and so the solution is determined as $n=6$n=6 even before the factorisation step.

By definition, we say that $0!=1$0!=1.

Worked examples

example 2

Evaluate $5!$5!

This is a simple one, either on your calculator use the factorial button.  On my calculator it is listed as $x!$x! you may need to check your manual for yours, OR, we write down and evaluate long hand. 

$5!=5\times4\times3\times2\times1=120$5!=5×4×3×2×1=120

example 3

Evaluate $\frac{6!}{4!}$6!4!​

Long hand this looks like this 

But let's just write that right hand side a slightly different way. See how $6!$6! is also equal to $6\times5\times4!$6×5×4! So, 

Being able to simplify factorials in this way is very important, because anything higher than $12!$12! often results in scientific notation on hand held calculators, and over $70!$70! won't compute on hand held calculators. 

example 4

Evaluate $\frac{7!\times4!}{5!\times2!}$7!×4!5!×2!​

Let's use the trick we just learnt in question 2.  And simplify the numerator where we can first. 

Practice questions

QUESTION 4

QUESTION 5