iGCSE (2021 Edition)

# 8.01 Counting techniques

Lesson

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:

 Total number of outcomes $=$= $2\times6$2×6 Total number of outcomes $=$= $12$12

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$09).

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

$26$26 $26$26 $26$26 $-$ $10$10 $10$10 $10$10

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:

 $26\times26\times26\times10\times10\times10$26×26×26×10×10×10 $=$= $17576000$17576000 possibilities

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

The fundamental counting principle

If an event can happen in $a$a different ways, another event in $b$b different ways, another event in $c$c different ways and so on, then the successive events can happen in:

$a\times b\times c\times\ldots$a×b×c× different ways

#### Worked example

##### Example 1

A password contains six digits, which can be lower case letters or the numbers $0-9$09. 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:

 Total number of possible passwords $=$= $36\times35\times34\times33\times32\times31$36×35×34×33×32×31 Total number of possible passwords $=$= $1402410240$1402410240

#### Practice questions

##### Question 1

If there are $26$26 entrants in a particular poker tournament and only the top $3$3 get paid, how many different orderings of the paid places are possible?

##### Question 2

A university has $5$5 flagpoles and $8$8 different flags. In how many ways can the flags be arranged on the $5$5 flagpoles? (Only $1$1 flag per flagpole and order of flagpoles does matter.)

##### Question 3

A random three-letter string is to be formed from the letters A, B, C, D, E and F without repetition.

1. What is the probability that the string will begin with a vowel?

2. What is the probability that the string will end with a consonant?

3. What is the probability that the string will consist of all vowels?

4. What is the probability that the string will consist of all consonants?

5. What is the probability that the string will consist of a combination of vowels and consonants?

## 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×(n1)×(n2)×(n3)×...×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!(n1)! can be simplified to $\frac{n\times\left(n-1\right)!}{\left(n-1\right)!}=n$n×(n1)!(n1)!=n.

Similarly, $\frac{n!}{\left(n-3\right)!}=n\times\left(n-1\right)\times\left(n-2\right)$n!(n3)!=n×(n1)×(n2), 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×(n3)! for $n$n, we might proceed as follows:

 $n!$n! $=$= $120\times\left(n-3\right)!$120×(n−3)! $n\times\left(n-1\right)\times\left(n-2\right)\times\left(n-3\right)!$n×(n−1)×(n−2)×(n−3)! $=$= $120\times\left(n-3\right)!$120×(n−3)! $n\times\left(n-1\right)\times\left(n-2\right)$n×(n−1)×(n−2) $=$= $120$120 $n^3-3n^2+2n$n3−3n2+2n $=$= $120$120 $n^3-3n^2+2n-120$n3−3n2+2n−120 $=$= $0$0 $\left(n-6\right)\left(n^2+3n-120\right)$(n−6)(n2+3n−120) $=$= $0$0

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

 $\frac{6!}{4!}$6!4!​ $=$= $\frac{6\times5\times4\times3\times2\times1}{4\times3\times2\times1}$6×5×4×3×2×14×3×2×1​

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,

 $\frac{6!}{4!}$6!4!​ $=$= $\frac{6\times5\times4!}{4!}$6×5×4!4!​ $=$= $6\times5$6×5 $=$= $30$30

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.

 $\frac{7!\times4!}{5!\times2!}$7!×4!5!×2!​ $=$= $\frac{(7\times6\times5!)\times(4\times3\times2!)}{5!\times2!}$(7×6×5!)×(4×3×2!)5!×2!​ $=$= $7\times6\times4\times3$7×6×4×3 $=$= $504$504

#### Practice questions

##### QUESTION 4

Simplify $\frac{7!}{5!}$7!5!

##### QUESTION 5

Simplify $\frac{6!}{4!4!}$6!4!4! by identifying common factors of the numerator and denominator.

### Outcomes

#### 0606C11.2

Know and use the notation n! (with 0! = 1), and the expressions for permutations and combinations of n items taken r at a time.

#### 0606C11.3

Answer simple problems on arrangement and selection.