Transcript Counting Techniques

COUNTING TECHNIQUES
PERMUTATIONS
AND
COMBINATIONS
Computer Science, Statistics and Probability all involve
counting techniques which are a branch of mathematics
called combinatorics (ways to combine things). We'll be
introducing this topic in this section.
For dinner you have the following choices:
ENTREES
MAINS
soup
salad
chicken
prawns
hamburger
DESSERTS
How many different combinations
of meals could you make?
icecream

We'll build a tree diagram to
show all of the choices.
Notice the number of choices at each branch
2
choices
3
choices
2
choices
We ended up with
12 possibilities
soup, chicken, ice cream
soup, chicken, 
2  3  2 = 12
prawns
soup, prawns, ice cream
soup, prawns, 
soup, hamburger, ice cream
soup, hamburger, 
salad, chicken, ice cream
salad, chicken, 
prawns
salad, prawns, ice cream
salad, prawns, 
Now to get all
possible choices we
follow each path.
salad, hamburger, ice cream
salad, hamburger, 
Multiplication Principle of Counting
If a task consists of a sequence of choices in which
there are p selections for the first choice, q selections for
the second choice, r selections for the third choice, and
so on, then the task of making these selections can be
done in
pqr
different ways.
If we have 6 different shirts, 4 different pants, 5 different pairs
of socks and 3 different pairs of shoes, how many different
outfits could we wear?
6  4  5  3 = 360
A permutation is an ordered arrangement
of r objects chosen from n objects.
For combinations order does not matter but for
permutations it does.
There are three types of permutations.
The first is distinct with repetition.
This means there are n
distinct objects but in
this means different
choosing r of them you
can repeat an object.
Let's look at a 3
There are 10 choices for the first number
combination lock
There are 10 choices for the second number
with numbers 0
and you can repeat the first number
through 9
There are 10 choices for the third number
and you can repeat
By the multiplication principle there are 10  10  10 = 1000 choices
This can be generalized as:
Permutations: Distinct Objects with Repetition
The number of ordered arrangements of r objects
chosen from n objects, in which the n objects are
distinct and repetition is allowed, is nr
What if the lock had four choices
for numbers instead of three?
104 = 10 000 choices
The second type of permutation is distinct, without
repetition.
Let's say four people have a race. Let's look at the
possibilities of how they could place. Once a person has
been listed in a place, you can't use that person again (no
repetition).
Based on the multiplication principle:
First place would be
choosing someone from
4  3  2  1 = 24 choices
among 4 people.
Now there are only 3 to
choose from for second
place.
Now there are only 2
to choose from for
third place.
Only one possibility for
fourth place.
4th
3rd
2nd
1st
nP
r
, means the number of ordered arrangements of r objects
chosen from n distinct objects and repetition is not allowed.
n
n!
Pr 
n  r !
In the last example: 4 P
4
4!
4  3  2 1


 24
4  4!
0!
If you have 10 people
racing and only 1st, 2nd
and 3rd place how many
possible outcomes are
there?
10
0! = 1
10!
10 9  8  7!
P3 

 720
10  3!
7!
A combination is an arrangement of r
objects chosen from n objects regardless
of order.
nC
r
, means the number combinations of r objects chosen
from n distinct objects and repetition is not allowed.
n
 n
n!
Cr 
or  
n  r !r!
r
Order doesn't matter here so the combination 1, 2, 3 is not
different than 3, 2, 1 because they both contain the same
numbers.
You need 2 people on your committee and you have 5 to
choose from. You can see that this is without repetition
because you can only choose a person once, and order
doesn’t matter. You need 2 committee members but it
doesn't matter who is chosen first. How many
combinations are there?
5!
5  4  3!
C2 

 10
5  2! 2! 3! 2
5
The third type of permutation is involving n objects that
are not distinct.
How many different combinations of letters in specific
order (but not necessarily English words) can be formed
using ALL the letters in the word REARRANGE?
Not Examinable.. Just for Fun 
E
R
N
R
A
A
G
E
R
The "words" we form will have 9 letters so we need 9 spots to
place the letters. Notice some of the letters repeat. We need
to use R 3 times, A 2 times, E 2 times and N and G once.
9C
6C
4C


 2C1  1C1
3
2
2
First we choose
positions for the
R's. There are 9
positions and we'll
choose 3, order
doesn't matter
84  15  6  2  1 = 15 120 possible "words"
That leaves
6 positions
for 2 A's.
That leaves
4 positions
for 2 E's.
That leaves
2 positions
That leaves
for the N.
1 position
for the G.
This can be generalized into the following:
Permutations Involving n Objects
That Are Not Distinct
The number of permutations of n objects
of which n1 are of one kind, n2 are of a
second kind, . . ., and nk are of a kth kind
is given by
n!
n1 ! n2 !  nk !
where n  n1  n2 
 nk
A Challenging Example. Have a go. 
How many even numbers greater than 4000 can be
formed using some or all of the digits 1, 2, 3, 4, 5, 6 if each
digit must feature no more than once in a number?
We could have even numbers with 4, 5 or 6 digits
This Gives 4 possibilities to work with:
PART A: 4, 5 or 6 EVEN digits beginning with a 4 OR 6
PART B: 4, 5 or 6 EVEN digits beginning with a 5
PART C: 5 or 6 EVEN digits beginning with a 2
PART D: 5 or 6 EVEN digits beginning with a 1 or 3
A Challenging Example. Have a go. 
How many even numbers greater than 4000 can be
formed using some or all of the digits 1, 2, 3, 4, 5, 6 if each
digit must feature no more than once in a number?
PART A: 4, 5 or 6 EVEN digits beginning with a 4 OR 6
2
4
+
2
3
4
2
3
+
2
2
4
1
This gives a total of 240
3
2
2
2
A Challenging Example. Have a go. 
How many even numbers greater than 4000 can be
formed using some or all of the digits 1, 2, 3, 4, 5, 6 if each
digit must feature no more than once in a number?
PART B: 4, 5 or 6 EVEN digits beginning with a 5
1
4
+
1
3
4
3
3
+
2
1
4
1
This gives a total of 180
3
3
2
3
A Challenging Example. Have a go. 
How many even numbers greater than 4000 can be
formed using some or all of the digits 1, 2, 3, 4, 5, 6 if each
digit must feature no more than once in a number?
PART C: 5 or 6 EVEN digits beginning with a 2
1
4
1
3
2
4
3
2
+
2
1
This gives a total of 96
2
A Challenging Example. Have a go. 
How many even numbers greater than 4000 can be
formed using some or all of the digits 1, 2, 3, 4, 5, 6 if each
digit must feature no more than once in a number?
PART D: 5 or 6 EVEN digits beginning with a 1 or 3
2
4
2
3
2
4
3
3
+
2
1
This gives a total of 288
3
A Challenging Example. Have a go. 
How many even numbers greater than 4000 can be
formed using some or all of the digits 1, 2, 3, 4, 5, 6 if each
digit must feature no more than once in a number?
We could have even numbers with 4, 5 or 6 digits
This Gives 4 possibilities to work with:
PART A: 4, 5 or 6 EVEN digits beginning with a 4 OR 6 = 240
PART B: 4, 5 or 6 EVEN digits beginning with a 5 = 180
PART C: 5 or 6 EVEN digits beginning with a 2 = 96
PART D: 5 or 6 EVEN digits beginning with a 1 or 3 =288
Number of possible even numbers greater than 4000 = 804
Acknowledgement
I wish to thank Shawna Haider from Salt Lake Community College, Utah
USA for her hard work in creating this PowerPoint.
www.slcc.edu
Shawna has kindly given permission for this resource to be downloaded
from www.mathxtc.com and for it to be modified to suit the Western
Australian Mathematics Curriculum.
Stephen Corcoran
Head of Mathematics
St Stephen’s School – Carramar
www.ststephens.wa.edu.au