14A - Fundamental Counting Principle and Factorial Notation

Investigation – You needs to catch a bus and a train to work. There are 3 different ways to travel
from A to B and 4 different ways to travel from B to C. How many different ways are there to travel
from A to C?

• Fundamental counting principle

If one event can happen in 𝑎𝑎 different ways, a second event in 𝑏𝑏 different ways, and a third event
in 𝑐𝑐 different ways and so on, then the successive events can happen in ____________________
different ways.

Tip: - Draw dashes to show positions available.

- Write numbers on dashes to indicate number of possibilities.
- Then, multiply

Examples

1) How many different 3 course dinner can be chosen if a restaurant offers these choices?

2) The number plate on a car has 2 letters, followed by 4 numbers. How many different number
plates of this type are possible?

3) How many five-letter words can be formed in which the second and fourth letters are vowels
and the other three letters are consonants,
a) if letters can be repeated? b) if letters cannot be repeated?

4) In how many ways can four letters from the word BRIDGE be arranged if no letter is repeated?

5) In how many ways can 5 people stand in a line?

Factorial Notation, ! – a short way to write the product of consecutive positive integers

n! =

6) Five boys – Arden, Dominic, Marc, Ivan and Brad – run a 100m race.
a) How many 1st-2nd-3rd-4th-5th placings are possible?

b) How many 1st-2nd-3rd placings are possible?

7) Evaluate without a calculator

12!
a) 4! b) 9! ×3!

8) Simplify:
𝑛𝑛! (𝑛𝑛−2)!(𝑛𝑛−1)!
a) (𝑛𝑛−1)! b) 𝑛𝑛!(𝑛𝑛−3)!

1 1
c) (𝑛𝑛+1)! − (𝑛𝑛−1)!

9) How many numbers greater than 5000 can be formed with the digits 2, 3, 5, 7, 9 if
a) no digit is repeated? b) digits can be repeated?
 14B - Permutations (Ordered Selection) – Without Repetition
Investigation – In how many ways can 10 people select a committee consisting of a president,
vice-president, a treasurer and a secretary?
 Number of possible committees = ______ x ______ x ______ x _______
= (in factorial notation)

A permutation describes an ordered selection/arrangement of a number of objects from a total

number of objects without replacement/repetition.
- It is used when the order is important – e.g. the first three people in a running race (the
order matters)

Investigation – In how many ways can 3 people select a committee consisting of a president,
vice-president and a secretary?
 Number of possible committees = ______ x ______ x ______

= (in factorial notation)

• Special Case of 0! and nPr

nP
n= and 0! =

Proof
Examples

1) Evaluate 9P4.

2) a) Find the number of arrangements of 3 digits that can be formed using the digits 0 to 9 if each
digit can be used only once.

b) How many 3-digit numbers greater than 700 can be formed?

c) How many of these numbers are divisible by 5?

3) a) How many six-digit numbers can be formed entirely from odd digits?

b) How many of these numbers contain at least one seven?

(HSC 20111 Q2 (e))

(HSC 2006 Q3 (c))

 14C - Permutations – Grouping Restrictions
Tip: It is good to order the group first, then order the individuals within each group.

1) (2012 HSC Q5) How many arrangements of the letters of the word OLYMPIC are possible if the C
and the L are to be together in any order?
(A) 5! (B) 6! (C) 2 x 5! (D) 2 x 6!

2) How many ways are there of arranging the letters of the word MEALS if:
a) if the consonants are to be grouped b) if the vowels will be at the front and back?
together?

3) In how many ways can 5 boys and 4 girls be arranged in a line if:
a) boys and girls alternate? b) three boys must be at the start of the line?

c) line begins and ends with a boy? d) girls are together

e) boys and girls are in separate groups? f) two girls Amanda and Cindy are together?

g) a particular boy, John, insists on being between two girls?

4) (Cambridge Ex 14C – Q8) Find how many arrangements of the letters of the word UNIFORM are
possible:
a) if the vowels must occupy the first, middle and b) if the word must start with U and end with M
last positions

c) if all consonants must be in a group at the end d) if all consonants must be in a group
of the word

e) if the M us somewhere to the right of the U

5) (Cambrdige Ex 14C – Q16) In how many ways can ten people be arranged in a line:
a) without restriction b) if one particular person must sit at either end

c) if two particular people must sit next to one d) if neither of two particular people can sit on
another either end of the row

6) In how many ways can six students and two teachers be arranged in a row if:
a) the two teachers are together b) the teachers are not together

c) there are at least three students separating the teachers

(HSC 2008 Q4 (b))

 14D - Permutations – Identical Elements Restriction
Investigation – In how many ways can the six letters of the word MUM be arranged in a line?

Tip: - Find permutation for the same number of elements

- Divide by number of ways to arrange the number of identical objects.

1) [2012 Hurlstone Agricultural] – How many distinct eight letter arrangements can be made using the
letters of the word PARALLEL? (2 marks)

2) (2001 HSC)
a) How many arrangements of the letters in the b) How many arrangements of the letters in the
word ALGEBRAIC are possible? (1 mark) word ALGEBRAIC are possible if the vowels must
occupy the 2nd, 3rd, 5th and 8th positions? (2 mark)

3) (Cambridge Q13 b) How many five-letter words can be formed by using the letters of the word
BANANA?

4) How many six-letter words can be formed by using the letters of the word PRESSES?

(HSC 2010 Q3 (a))

 14E - Counting Underdered Selection (Combinations)
Investigation – How many groups of 3 can be selected from 4 people, A, B, C and D?

A combination describes an unordered selection/arrangement of a number of objects from a

total number of objects without replacement/repetition.
- It is used when the order is NOT important – e.g. AB is same as BA

Proof:

Investigation – Evaluate 7C2 and 7C5. What do you notice? Why is this happening?
 Example 1 [1995 HSC Q3 (a)] A security lock has 8 buttons labelled as shown. Each person
using the lock is given a 3-letter code.

(i) How many different codes are possible if letters can be repeated and their order is important?

(ii) How many different codes are possible if letters cannot be repeated and their order is
important?

(iii) Now suppose that the lock operates by holding 3 buttons down together, so that order is NOT
important. How many different codes are possible?

Example 2: Ten people meet to play doubles tennis.

(a) In how many ways can four people be selected (b) How many of these ways will include Maria
from this group to play the first game? (Ignore the and exclude Alex?
subsequent organisation into pairs.)

(c) If there are four women and six men, in how (d) Again with four women and six men, in how
many ways can two men and two women be many ways will women be in the majority?
chosen for this game?

Example 3: A committee of 6 people is to be selected at random from a group of 11 men and 12

women. Find the number of possible commitees if:
a) there is no restriction on who is on the b) all committee members are to be male
committee

c) Anna is included d) Bruce is not included

e) there are to be 4 women and 2 men f) there is a majority of women

g) there is at least one male

Example 4: [2014 CSSA Ext 1 Q8] A Mathematics department consists of 5 female and 5 male
teachers. How many committees of 3 teachers can be chosen which contain at least one female
and at least one male?
(A) 100 (B) 120 (C) 200 (D) 2 500

Example 5: (a) What is the number of combinations of the letters of the word EQUATION taken
four at a time (without repetition)?

(b) How many contain four vowels?

(c) How many contain the letter Q?

Example 6: Ten points P1, P2, ..., P10 are chosen in a plane, no three of the points being
collinear.
(a) How many lines can be drawn through pairs of the points?

(b) How many triangles can be drawn using the given points as vertices?

(c) How many of these triangles have P1 as one of their vertices?

(d) How many of these triangles have P1 and P2 as vertices?

Example 7: (HSC 2015 Q4) Example 8: (HSC 2016 Q8)

Example 9: (HSC 2012 Q11 e)

In how many ways can a committee of 3 men and 4 women be selected from a group of 8 men
and 10 women? (1 mark)
Here are the real Challenges!

Example 10: In how many ways can four runners and three swimmers be arranged in a row if
there are eight runners and five swimmers to select from?

Example 11: In how many ways can four people be divided into:
a) a 1st pair and then a 2nd pair b) any pair

Example 12: (HSC – Ext 2 - 2010 Q4 (d)) A group of 12 people is to be divided into discussion
groups.
(i) In how many ways can the discussion groups be formed if there are 8 people in one group, and
4 people in another? (1 mark)

(ii) In how many ways can the discussion groups be formed if there are 3 groups containing 4
people each? (2 marks)

Example 13: How many four-letter words can be formed from the letters of ABBOTT?
 14F - Using Counting in Probability
Example 1: [2013 Independent Ext 1] (2 marks) The letters of the word NUMBER are arranged
at random in a row. Find the probability that consonants occupy both end positions.

Example 2: A PIN has 4 numbers. If I forget my PIN I am allowed 3 tried to get it right. Find the
probability that I get it within the 3 tries.

Example 3: A bag contains 3 white and 6 black cubes. Two cubes are drawn at random without
replacement. Calculate the probability that both cubes are black.

Example 4: Eight people of whom A and B are two, arrange themselves at random in a straight
line. What is the probability that
(a) A and B are next to each other (b) A and B are not next to each other

(c) A and B occupy the end positions (d) there are at least three people between A and
B

Example 5: The letters of the word TWITTER are arranged randomly. What is the probability that
the three Ts are grouped together?
Example 6: From a group of 12 people of whom 8 are males and 4 are females, a sample of 4 is
selected at random. What is the probability that the sample contains at least 2 females?

Example 7: A box contains 10 pairs of headphones two of which are defective. A sample of three
pairs of headphones is drawn at random from the box without replacement. Find the probability
that not more than one pair of headphones is defective.

Example 8: (HSC 2004 Q2(e)) A four-person team is to be chosen at random from nine women
and seven men.

(i) In how many ways can this team be chosen? (1 mark)

(ii) What is the probability that the team will consist of four women? (1 mark)

Example 9: (HSC 2017 Q10)

Example 10: (HSC 2007 Q5 (b))

 14G - Circular Arrangements
Discuss– In how many ways can 4 people sit around a circular table?

Tip: Fix one person, then calculate the number of arrangements.

Example 1: a) In how many ways can 6 people sit around a circular table?

b) If seating is random, find the probability that 3 particular people will sit together.

Example 2: 5 boys and 5 girls are arranged in a circle. In how many ways can this be done
(a) if there are no restrictions (b) if the boys and the girls alternate

(c) if the boys and girls are in distinct groups (d) if a particular boy and girl wish to sit next to
one another

e) if two particular boys do not wish to sit next to f) if one particular boy wants to sit between two
each other particular girls?

Example 3: Seven people are sitting around a table.

(i) How many seating arrangements are possible? (1 mark)

(ii) Two people, Kevin and Julia, do not sit next to each other. How many seating
arrangements are now possible? (2 marks)
Example 4: Four married couples are to be seated around a circular table for dinner.
(a) In how many ways can the people be seated around the table?

(b) If each married couple is to be seated together, in how many ways can this be done?

Example 5 (2013 HSC Q7): A family of eight is seated randomly around a circular table. What is
the probability that the two youngest members of the family sit together?
6!2! 6! 6!2! 6!
(A) 7! (B) 7!2! (C) 8! (D) 8!2!

Example 6 (2014 HSC Q8): In how many ways can 6 people from a group of 15 people be chosen
and then arranged in a circle?
14! 14! 15! 15!
(A) 8! (B) 8!6 (C) 9! (D) 9!6

Example 7 (2018 HSC Q8): six men and six women are to be seated at a round table. In how
many different ways can they be seated if men and women alternate?

(A) 5! 5! (B) 5! 6! (C) 2! 5! 5! (D) 2! 5! 6!

Example 8: In how many ways can 10 people be seated across two tables, each seating five
people?

(Challenge) Example 9 (2001 EXT2 HSC) A class of 22 students is to be divided into four groups
consisting of 4, 5, 6 and 7 students.

(i) In how many ways can this be done? Leave your answer in simplified form. (2 marks)

(ii) Suppose that the four groups have been chosen. In how many ways can the 22
students be arranged around a circular table if the students in each group are to be
seated together? Leave your answer in simplified form. (2 marks)
 14H - The Pigeonhole Principle

Consider that there are 10 pigeons flying into 9

pigeonholes.

Then there will be at least one pigeonhole with at least

___ pigeons.

Pigeonhole Principle

• If there are n pigeonholes and (n +1) pigeons to fly into them, then at least one pigeonhole
must hold 2 or more pigeons.

• If 𝑛𝑛 items are distributed amongst 𝑚𝑚 pigeonholes and 𝑛𝑛 > 𝑚𝑚, then at least one pigeonhole will
contain more than one item.

Note:
• This section of work mostly contains proofs.
• Questions can be asked in reverse.
• Express your ideas carefully and concisely with sentences!

Example 1: Complete:

a) If 11 pigeons fly into 10 pigeonholes, there will be at least one pigeonhole with at least ___
pigeons.

b) If 31 pigeons fly into 10 pigeonholes, there will be at least one pigeonhole with at least ___
pigeons.

c) If there are 10 pigeonholes, then the least number of pigeons that will guarantee that there is
at least one pigeonhole with at least ____ pigeons is 71.

Example 2: Keira selects words at random from a novel she is reading. How many words must
she select to be certain to have at least 2 words that start with the same letter?
As the number of pigeonholes increases, it’s useful to find the remainder from division.

Example 3 (Cambridge): a) Seventy guests sit at a restaurant with 23 tables. Prove that there
must be at least one table with at least 4 guests.

b) Explain how many guests there must be to guarantee that at least one of the 23 tables has at
least 11 guests.

Example 4 (Cambridge): A suburb has 15 large apartment blocks.

(a) If a shopkeeper knows 200 people from these blocks, explain why he must know at least 14
people from at least one block.

(b) How many people from these blocks must he know in order to know at least 25 people from at
least one block?

Example 5: If there is a drawer with 12 blue socks, 8 red socks and 9 green socks, how many
socks must be removed to ensure:
a) 2 green socks are drawn

b) 3 of every coloured sock is drawn

c) 4 of one colour sock is drawn

Example 6 (Cambridge): Every person has fewer that 500 000 hairs on their head. Prove that in
Sydney, with a population of more than 5 000 000, there are at least eleven people with exactly
the same number of hairs on their heads.

Example 7 (Cambridge): Vikram has 30 distinct ties. Every day, including weekends, he selects a
tie at random to wear. How many successive dates are needed to guarantee that there is at least
one day of the week on which he has worn the same tie on at least 6 occasions?

Example 8: What is the minimum number of students in a school in order for us to guarantee that
at least two students will have the same initials?

Example 9: A square with side length 2 cm has 9 points drawn at random inside the square. Show
that it is possible for 3 of these points to form a triangle with an area less than 1.

Example 10: Given 5 points randomly placed inside of a 2 x 2 box, prove that there must be a pair
of two points that are within √2 of each other.
Example 11 (Cambridge): Fifteen people come into a room, and there are many handshakes as
they meet — no pair shakes hands twice. Prove that there will be at least two people who have
made the same number of handshakes.

Example 12: A thief breaks into a bookstore in the middle of night. In the bookstore, there are 10
Spanish books, 20 French books, 8 Italian books, 15 Korean books and 25 Japanese books.

The thief is interested in learning a language, but doesn't dare turn on light, so they can't see the
titles of the books.

How many books does the thief have to take to be certain they have 12 books in the same
language?

Example 13:(2022 HSC Q12(b)) A sports association manages 13 junior teams. It decides to
check the age of all players. Any team that has more than 3 players above the age limit will be
penalised. A total of 41 players are found to be above the age limit.
Will any team be penalised? Justify your answer. (2 marks)

Example 14: (2020 Ext 1 HSC Q12) To complete a course, a student must choose and pass
exactly three topics.
There are eight topics from which to choose. Last year 400 students completed the course.
Explain, using the pigeonhole principle, why at least eight students passed exactly the same three
topics. (2 marks)