Counting Strategies: the product rule for counting, permutations and combinations

The audience of this tutorial and what you will learn the following in detail:

The Systematic Listing Strategies

This is a topic introduced in GCSE 9-1 mathematics specification. It's related to the concept of probability.
As a part of this tutorial, you will first learn something that is not in the GCSE - factorial. It, however, is not rocket science - a very easy concept, indeed.

Factorial - n!

Factorial is defined as follows:

n! = n x (n-1) x (n-2) x (n-3) x .... x 3 x 2 x 1

E.g.

3! = 3 x 2 x 1 = 6
4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4 x 3 x 2 x 1 = 120

The factorial of both 0 and 1 are defined as 1 - 0! = 1; 1! = 1.

With the following programme, you can easily find the factorial of any number:

Factorial Calculator - n!

n  

Now, let's deal with some simple calculations involving the factorials of numbers:

E.g.1

Find 5!/3!

5!/3! = 5 X 4 X 3!/3!
= 5 X 4
= 20
We stop the expansion of the top factorial at 3 so that the factorial of 3 at the bottom can be canceled out.

E.g.2

Find 6!/4!

6!/4! = 6 X 5 X 4!/4!
= 6 X 5
= 30
We stop the expansion of the top factorial at 4 so that the factorial of 4 at the bottom can be canceled out.

E.g.3

Find 6!/5!

6!/5! = 6 X 5!/5!
= 6
= 6
We stop the expansion of the top factorial at 5 so that the factorial of 5 at the bottom can be canceled out.

E.g.4

Find 6!/(4! 2!)

6!/(4! 2!) = 6 X 5 X 4!/(4! 2!)
= 6 X 5 X 4!/ 4! 2!
= 30 / 2!
= 30/2
= 15
We stop the expansion of the top factorial at 4, the bigger factorial of the denominator, so that the factorial of 4 at the bottom can be cancelled out.

E.g.5

Find 6!/(5! 1!)

6!/(5! 1!) = 6 X 5!/(5! 1!)
= 6 X 5!/ 5! 1!
= 6 / 1!
= 6 / 1
= 6
We stop the expansion of the top factorial at 5, the bigger factorial of the denominator, so that the factorial of 5 at the bottom can be cancelled out.

E.g.6

Find 6!/(6! 0!)

6!/(6! 0!) = 6!/(6! 0!)
= 6!/ 6! 0!
= 1 / 0!
= 1 / 1
= 1
We stop the expansion of the top factorial at 6, the bigger factorial of the denominator, so that the factorial of 6 at the bottom can be cancelled out.

The Arrangements

E.g.1

How many ways can the letters, A and B, be arranged?

A,B
B,A
2 = 2 x 1 = 2!

E.g.2

How many ways can the letters, A, B and C, be arranged?

A, B, C
B, A, C
A, C, B
B, C, A
C, B, A
C, A, B
6 = 3 x 3 x 1 = 3!

E.g.3

How many ways can the letters, A, B, C and D, be arranged?

A, B, C, D | B, C, D, A | C, D, B, A | D, A, B, C |
A, B, D, C | B, C, A, D | C, D, A, B | D, A, C, B |
A, C, B, D | B, D, A, C | C, A, B, D | D, B, C, A |
A, C, D, B | B, D, C, A | C, A, D, B | D, B, A, C |
A, D, C, B | B, A, C, D | C, B, A, D | D, C, A, B |
A, D, B, C | B, A, D, C | C, B, D, A | D, C, B, A |

24 = 4 x 3 x 2 x 1 = 24 = 4!

Formula: The number of arrangement from n different objects is simply n!.

E.g.4

How many arrangements can be made from the English alphabet?
It's staggering 26! - 4.0329146112660565 x 10²⁶.

E.g.5

A family of three, dad(D), mom(M) and their toddler son(T), booked three adjacent seats on a coach. How many arrangements were there?
D, M, T | D, T, M | M, D, T | M, T, D | T, D, M | T, M, D
6 different arrangements.

E.g.6

There are 6 red balls, 5 green balls and 4 blue balls in a container. Sara takes two balls from it. List all the possible combinations.
R,R | R, G | R, B |G, B| G, G | B, B |
6 different arrangements.

E.g.7

The numbers, 3, 4, 6, 7 are written on four cards. How many 4-digit-numbers greater than 6000 can be made from them?
6347, 6374, 6437, 6473, 6734, 6743
6 arrangements - 1 x 6 = 1 x 3!.

E.g.8

The numbers, 1, 2, 3, 4, 5, 6, 7, are written on seven cards. How many 4-digit-numbers greater than 7000 can be made from them?
7342, 7374, 7431, 7473, 7634, 7643...
720 arrangements - 1 x 6! = 1 x 720 = 720.

E.g.9

The numbers, 1, 5, 3, 8 are written on four cards. How many even numbers can be made from them?
The last digit must be 8. Then, the rest, 3 digits, can be rearranged in 3! ways.
3! x 1 = 6 x 1 = 6.
1, 5, 3, 8 | 3, 5, 1, 8 | 5, 3, 1, 8 | 3, 1, 5, 8 | 1, 3, 5, 8 | 5, 1, 3, 8 |

E.g.10

The numbers, 1, 5, 3, 8, 9 are written on five cards. How many numbers can be made, if the two prime numbers stay together?
The numbers, 3 and 5 must stay together as a single number. Then, they can be rearranged in 4! ways.
4! = 24.
The prime numbers, 3 and 5, however, can be arranged in two different ways too - 3, 5 or 5, 3.
The total number of arrangements = 2 x 24 = 48

The Product Rule for Counting

Suppose the English letters, A, B, C and the Greek letters, α, β and λ are in two different containers. A letter is taken from each container and a meaningless word is formed. The process is as follows:

 

There are 9 arrangements, provided that the order of the two letters is immaterial. It's 3 x 3 = 9.

E.g.1

A coin is tossed and a die is thrown. Find all the possible outcomes.

H, 1 | H, 2 | H, 3 | H, 4 | H, 5 | H, 6
T, 1 | T, 2 | T, 3 | T, 4 | T, 5 | T, 6
12 different outcomes - 2 x 6 = 12.

E.g.2

Two dice are thrown. Find all the possible outcomes.

1, 1 | 1, 2 | 1, 3 | 1, 4 | 1, 5 | 1, 6
2, 1 | 2, 2 | 2, 3 | 2, 4 | 2, 5 | 2, 6
3, 1 | 3, 2 | 3, 3 | 3, 4 | 3, 5 | 3, 6
4, 1 | 4, 2 | 4, 3 | 4, 4 | 4, 5 | 4, 6
5, 1 | 5, 2 | 5, 3 | 5, 4 | 5, 5 | 5, 6
6, 1 | 6, 2 | 6, 3 | 6, 4 | 6, 5 | 6, 6
12 different outcomes - 6 x 6 = 36.

Food for Thought

A van that sped fast after an accident on a country lane in the UK, was reported to having letters, F, V, digits 6 and 8 as well as the letters E, V and R on its number plate. The witness, who reported the incident to the police, was not sure whether they were in that exact order. How many vans would the police have checked to track down the culprit?
Ans:24

Arranging Objects with Like Objects

E.g.

How many ways can you arrange the letters, M, N, N, and N?

MNNN, NMNN, NNMN, NNNM - 4 ways = 4!/3!

How many ways can you arrange the letters, BBC?

BBC, BCB, CBB - 3 ways = 3!/2!

How many ways can you arrange the letters, A, B, B, and A?

ABBA, AABB, BABA, BBAA, ABAB, BAAB - 6 ways = 4!/2!2!

Rule:

If there are n objects with m likes, then the number of different arrangements are n!/m!.

E.g.

The letters of the word, CALCULUS, are rearranged. List the number of possibilities.
n = 8!/2!2!2! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 / 8 = 5040

The letters of the word, MINIMUM, are rearranged. List the number of possibilities.
n = 7!/3!2! = 7 x 6 x 5 x 4 x 3 x 2 x 1 / 12 = 420

How many numbers can you make from the digits, 2, 3, 7 and 5 that are divisible by 5?
Since they are divisible by 5, they must end up with 5.
_ _ _5
The other 3 can be rearranged in 3!, 6 , ways.
The number of rearrangements are 6.

Food for Thought

Anne rearranges her 7 flower pots according to their age. She plans to keep the two pots she bought during the last two weeks, one at a time, closer to her kitchen. How many different ways can she rearrange them?Ans:240

Permutations - nPr

The arrangements where the order matters are called permutations.

nPr = n!/(n-r)!

E.g.

Pick up three boys from a group that has 5 children, Adam, Benn, Charles, David ,and Esper, in order to arrange them in the order of their height.
It could be, Adam, Benn, Charles or Charles, Benn, Adam or Adam, Charles, Esper etc - 20 possibilities
20 = 5!/2! = 5!/(5-3)! = 5P3.

Calculator for finding nPr

n:    r:  

 

Combinations - nCr

The arrangements where the order does not matter are called combinations.

nCr = n!/(n-r)!r!

E.g.1

Pick up three envelopes with letters A, B, C, D, E - one in each of them.
It could be, ABC, BAC,CAB etc.They, however, are counted as just one combination.
10 = 10!/3!2! = 5C2.

E.g.2

For a friendly African Cup of Nations football tournament, 6 players each from Namibia, Mali, Zambia and 3 players from Cameroon are going to participate.
1) How many ways can the organizers pick 11 players for the event?
2) If the organizers choose to pick 3 player each from Namibia, Mali, Zambia and 2 players from Cameroon, how many combinations of players are possible?
1) 11 players to be chosen from 21 players, regardless of the country.
No of combinations = 21c11 = 352716
2)3 players each from Namibia can be chosen, 6c3 ways = 20
Similarly, 3 players from Zambia and Mali can be chosen, 20 ways, each.
2 players can be chosen from Cameroon in 3c2 ways = 3
Total number of combinations = 20 x 20 x 20 x 3 = 24000.

Calculator for finding nCr

n:    r:  

 

Food for Thought

A diagonal is defined as a line that connects two vertices of a polygon that are not adjacent. Find the number of possible diagonals in a square, pentagon and hexagon. Hence, derive a formula for the number of diagonals in a polygon of side n - Ans:(n² - 3n)/2.

Practice Questions

1. There are x boys and 16 girls in a toddler group and are 112 ways of choosing a boy and a girl. Find the value of x.
2. There are 3 starters, 6 main courses and 4 desserts in a menu of a certain restaurant. Find the maximum number of ways of choosing a starter, a main course and a dessert from this menu.
3. A toddler is given the letters of vowels and asked to pick up two letters. How many ways are there for him to do it?
4. A farmer has ten 10 black sheep and 12 white sheep in a pen. He wants to take 3 sheep for shearing. How many ways can he do it?
5. Four consonants are chosen from the word, RICHMOND. How many ways are there for the task?

 

Answers

Move the mouse over, just below this, to see the answers:

1. 7
2. 72
3. 20
4. 2400
5. 15

 

Now that you have read this tutorial, you will find the following tutorials very helpful too: