Transcript 2016-05-03 (Tuesday) - Permutation

HKDSE Mathematics
Ronald Hui
Tak Sun Secondary School
Homework
SHW7-B1:
SHW7-P1:
RE8:
EHHW1:
EHHW2:
Ronald HUI
Sam L
Sam L
Sam L
Tashi, Kelvin, Sam L, Pako
Tashi, Kelvin, Sam L, Pako
Homework
SHW9-B1: Sam L
SHW9-C1: Kelvin (RD), Sam L
SHW9-D1: Tashi, Matthew (RD), Ken (RD),
SHW9-E1:
SHW9-R1:
SHW9-P1:
RE9:
Ronald HUI
Kelvin, Yan Tin, Walter
Tashi, Kelvin
Tashi, Kelvin, Sam L
Tashi, Sam L
Sam L, Pako
Book 5B Chapter 10
Basic Principles of Counting
Addition Rule of Counting
There are 7 cats and 5 dogs in a pet shop.
In how many ways can
I choose a pet to buy?
Addition Rule of Counting
Method 1: There are 7 ways of choosing a cat.
Method 2: There are 5 ways of choosing a dog.
∴
The total number of ways of choosing a pet
 7  55
 12
You have applied the addition
rule of counting.
In general,
suppose a task can be performed by k methods,
in which there are
n1 ways to perform method 1,
n2 ways to perform method 2, … ,
nk ways to perform method k,
then there are in total n1 + n2 + … + nk ways to
perform the task.
If a task can be performed using two
methods which have common ways,
can we still apply the addition rule
of counting?
In this case, we need to subtract
the common ways when we apply
the rule to avoid double
counting. Let’s see an example.
Suppose Mary has 6 different stickers, Ada has 4
different stickers and they have 2 stickers in common.
How many different choices are there if a sticker is
chosen?
Mary’s
stickers
E
C
A
A
G
F
D
B
B
H
The required number of ways  6  4422
8
8
Ada’s
stickers
In general, we have the following rule.
If a task can be performed using either method 1
with n1 ways or method 2 with n2 ways, and there
are m ways in common, then the number of ways
to perform the task is n1 + n2 – m.
Method 2
Method 1
n1
m
n2
Follow-up question
A number is chosen from 1 to 60 inclusive. How many
ways of selecting a number that
(a) is either a multiple of 6 or 11?
(b) is either a multiple of 3 or 11?
(a) By the addition rule of counting,
the required number of ways
= 10 + 5
There are 10 multiples of 6: 6, 12, 18, ... , 60.
= 15
There are 5 multiples of 11: 11, 22, 33, 44, 55.
There are no common multiples of 6 and 11.
Follow-up question
A number is chosen from 1 to 60 inclusive. How many
ways of selecting a number that
(a) is either a multiple of 6 or 11?
(b) is either a multiple of 3 or 11?
(b) By the addition rule of counting,
the required number of ways
= 20 + 5 – 1
There are 20 multiples of 3: 3, 6, 9, ... , 33, ... , 60.
= 24
There are 5 multiples of 11: 11, 22, 33, 44, 55.
There is 1 common multiple of 3 and 11: 33.
Multiplication Rule of Counting
A restaurant offers 3 kinds of bread and 2 kinds of
drinks.
I want to have a bread and a
drink for my breakfast. How
many choices do I have?
1st step
∴
2nd step
Possible outcomes
Total number of choices
=32
=6
Number of kinds of bread = 3
Number of kinds of drinks = 2
In general, we can use the
multiplication rule of counting
to solve this kind of problem.
Multiplication Rule of Counting
Suppose a task involves a sequence of k steps.
If there are
n1 ways to perform step 1,
n2 ways to perform step 2, … ,
nk ways to perform step k,
then the number of ways to perform the task is
n1  n2  …  nk.
Example:
There are 3 different pencils, 4 different rulers and
6 different books in a bag. Find the number of
ways of choosing a pencil, a ruler and a book from
the bag.
The required number of ways
=346
= 72
Some problems may involve both the
addition rule and the multiplication rule of
counting. Let’s see an example.
There are 8 Japanese courses, 6 French courses and
5 German courses. If Victor wants to select two courses
of different languages, how many choices are there?
There are 3 possible types:
Type 1
Japanese course + French course
Type 2
Japanese course + German course
Type 3
French course
+ German course
There are 8 Japanese courses, 6 French courses and
5 German courses. If Victor wants to select two courses
of different languages, how many choices are there?
Type 1
Number of choices for a Japanese course and a French course
By multiplication rule of counting
= 8  6 = 48
Type 2
Number of choices for a Japanese course and a German course
By multiplication rule of counting
= 8  5 = 40
Type 3
Number of choices for a French course and a German course
By multiplication rule of counting
= 6  5 = 30
There are 8 Japanese courses, 6 French courses and
5 German courses. If Victor wants to select two courses
of different languages, how many choices are there?
∴
The required number of choices
By addition rule of counting
= 48 + 40 + 30
= 118
Do you know why the addition
rule of counting is used in the last
step?
Follow-up question
There are 15 boys and 13 girls in both class A and
class B. If a boy and a girl are selected from the same
class to participate in an exchange program, how
many choices are there?
By multiplication rule of counting,
number of choices of selecting a boy and a girl from class A
 15 13  195
Similarly,
number of choices of selecting a boy and a girl from class B
 195
By addition rule of counting,
the required number of choices  195  195  390
Book 5B Chapter 10
Permutation
Factorial Notation
We use the notation n! to denote the product of the
first n positive integers from 1 to n.  n! is read as n factorial.
For any positive integer n,
n !  n (n  1)(n  2)  ...  3  2  1 .
Moreover, we define 0!  1.
Example:
3!  3  2 1  6
5!  5  4  3  2 1  120
In fact, we can find the value of
n! by calculator. For example,
keying in
which is 5040.
gives the value of 7! ,
But we can also evaluate expressions
involving factorial without calculator.
For example,
5!5! 55443!
5!
3! 5  44


10

10
2
!3! 2!2!33!
!
2
2!2!3!
23!
Factorial notation is useful in finding the number of
arrangements or permutations.
Permutation
Consider 2 different pictures on a wall.
Picture A
Picture B
Picture B
We may also
arrange the
pictures in this way.
Picture A
Permutation
Consider 2 different pictures on a wall.
Picture A
Picture B
Picture B
In daily life, we often
come across
situations of
arranging objects.
Picture A
An arrangement of a certain number of objects in
a definite order is called a permutation.
Let us study how to find the
number of permutations of several
distinct objects.
Suppose we want to arrange the following 3 soldiers
in a row. How many different arrangements are there?
B
A
1st
Number of
choices
C
2nd
3rd
Suppose we want to arrange the following 3 soldiers
in a row. How many different arrangements are there?
A
B
C
1st
3rd
3

Number of
choices
2nd
Step 1 There are 3 ways to choose the first soldier.
Suppose we want to arrange the following 3 soldiers
in a row. How many different arrangements are there?
1st
B
C
A
C
A
B
2nd
3
2
A
B
C

Number of
choices
3rd
Step 2 There are 2 ways to choose the second soldier.
Suppose we want to arrange the following 3 soldiers
in a row. How many different arrangements are there?
1st
B
C
A
C
A
B
2nd
3
2
A
B
C
C
B
C
A
B
A
3rd
1

Number of
choices
____
____
____
____
____
____
Step 3 There are 1 way to choose the third soldier.
Suppose we want to arrange the following 3 soldiers
in a row. How many different arrangements are there?
1st
B
C
A
C
A
B
2nd
3
2
A
B
C
Number of
choices
By the multiplication rule of counting,
number of permutations  3  2  1  6
____
____
____
____
____
____
C
B
C
A
B
A
3rd
1
------- ABC
------- ACB
------- BAC
------- BCA
------- CAB
------- CBA
6 possible
outcomes
3  2  1  3!
Now we want to arrange the following 4 soldiers in a
row. How many different arrangements are there?
1st
Number of choices
2nd
3rd
4

Step 1 There are 4 ways to choose the first soldier.
4th
Now we want to arrange the following 4 soldiers in a
row. How many different arrangements are there?
Number of choices
1st
2nd
4
3
3rd
4th

Step 2 There are 3 ways to choose the second soldier.
Now we want to arrange the following 4 soldiers in a
row. How many different arrangements are there?
Number of choices
1st
2nd
3rd
4
3
2
4th

Step 3 There are 2 ways to choose the third soldier.
Now we want to arrange the following 4 soldiers in a
row. How many different arrangements are there?
Number of choices
1st
2nd
3rd
4th
4
3
2
1

Step 4 There are 1 way to choose the fourth soldier.
Now we want to arrange the following 4 soldiers in a
row. How many different arrangements are there?
Number of choices
1st
2nd
3rd
4th
4
3
2
1
By the multiplication rule of counting,
number of permutations  4  3  2  1  24
4  3  2 1  4!
By similar arguments, we have:
The number of permutations of n distinct objects
without repetition is n!.
In some situations, not all of the
n distinct objects are arranged.
By similar arguments, we have:
The number of permutations of n distinct objects
without repetition is n!.
Let us consider the case when we
only arrange some of the objects but
not all of them.
If 2 soldiers are selected and arranged in a row, how
many different arrangements are there?
1st
Number of choices
2nd
4

Step 1 There are 4 ways to choose the first soldier.
If 2 soldiers are selected and arranged in a row, how
many different arrangements are there?
Number of choices
1st
2nd
4
3

Step 2 There are 3 ways to choose the second soldier.
If 2 soldiers are selected and arranged in a row, how
many different arrangements are there?
Number of choices
1st
2nd
4
3
By the multiplication rule of counting,
number of permutations  4  3  12
4  3  4  ( 4  1)
If 3 soldiers (instead of 2) are selected and arranged
in a row, how many different arrangements are there?
1st
Number of choices
2nd
3rd
4

Step 1 There are 4 ways to choose the first soldier.
If 3 soldiers (instead of 2) are selected and arranged
in a row, how many different arrangements are there?
Number of choices
1st
2nd
4
3
3rd

Step 2 There are 3 ways to choose the second soldier.
If 3 soldiers (instead of 2) are selected and arranged
in a row, how many different arrangements are there?
Number of choices
1st
2nd
3rd
4
3
2

Step 3 There are 2 ways to choose the third soldier.
If 3 soldiers (instead of 2) are selected and arranged
in a row, how many different arrangements are there?
Number of choices
1st
2nd
3rd
4
3
2
By the multiplication rule of counting,
number of permutations  4  3  2  24
432
 4  ( 4  1)  ( 4  2)
By similar arguments, we have:
The number of permutations of n distinct objects
taken r at a time without repetition, denoted by Prn ,
is n (n 1)(n  2)...(n r 1).
Prnn  n(n  1)( n  2)( n  3)...( n  r  1)
n  n  (n  1)  (n  2)  ...  (n  r  1)
P
r
Pr  n  (n  1)  (n  2)  ...  (n  r (n1) r )!
 n(n  1)( n  2)( n  3)...( n  r  1)
(
n

r
)!
(
n

r
(n1) r )! )!
 n

(
n

1)

(
n

2)

...

(
n

r

n  (n  1)  (n  2)  ...  (n  r  1) (n  r )!
(n  r )!
n!
 n!
 !r )!
 (n n
((n
n  r)!
r)!
By similar arguments, we have:
The number of permutations of n distinct objects
taken r at a time without repetition, denoted by Prn ,
n!
.
is
(n  r )!
Prn  n(n  1)( n  2)( n  3)...( n  r  1)
n
Pr  n  (n  1)  (n  2)  ...  (n  r (n1) r )!
 n(n  1)( n  2)( n  3)...( n  r  1)
(n  (rn)!  r )!
 n  (n  1)  (n  2)  ...  (n  r  1)
(n  r )!
n!

(n n
 !r )!
n!
n!
n

0! = 1
  n!
In particular, Pn 
(n  r)!
(n  n )! 0!
Example:
The number of permutations of 5 distinct balls
taken 2 at a time without repetition is
P25 = 5  4 = 20.
One possible
permutation:
1st
2nd
Example:
The number of permutations of 6 distinct balls
taken 2 at a time without repetition is
P26 = 6  5 = 30.
One possible
permutation:
1st
2nd
Example:
The number of permutations of 6 distinct balls
taken 3 at a time without repetition is
P36 = 6  5  4 = 120.
One possible
permutation:
1st
2nd
3rd
In fact, we can find the value
of Prn by calculator. For
example,
keying in
which is 56.
gives the value of P28 ,
Follow-up question
(a) P48 means the number of permutations of
8 distinct objects taken ___
4 at a time without
___
repetition.
(b) Evaluate the following expressions.
(i)
210
P37 = _____
(ii)
240 240
P514 = _______
Recall:
1. The number of permutations of n distinct objects
without repetition is n!.
2. The number of permutations of n distinct objects
n
taken r at a time without repetition, denoted by Pr ,
n!
is n  (n  1)  (n  2)  ...  (n  r + 1) =
.
(n  r )!
Let us see how to use the
above results to solve
permutation problems.
Example:
There are 7 distinct numbers 1, 3, 4, 5, 7, 8 and 9.
(a) How many 7-digit numbers can be formed by
using the above 7 numbers without repetition?
There are 7 distinct digits.
(a) Number of 7-digit numbers formed  7!  5040
Example:
There are 7 distinct numbers 1, 3, 4, 5, 7, 8 and 9.
(b) How many 3-digit numbers can be formed by
using the above 7 numbers without repetition?
There are 7 distinct digits.
7
6
210
(b) Number of 3-digit numbers formed  P37  7
 P5
3  210
Example:
There are 7 distinct numbers 1, 3, 4, 5, 7, 8 and 9.
(c) How many 3-digit numbers formed in (b) are
divisible by 5?
(c) For a 3-digit number formed in (b) to be divisible by 5,
its last digit must be 5.
5
Choose 2 numbers from the remaining
6 numbers and arrange them in order.
Example:
There are 7 distinct numbers 1, 3, 4, 5, 7, 8 and 9.
(c) How many 3-digit numbers formed in (b) are
divisible by 5?
(c) For a 3-digit number formed in (b) to be divisible by 5,
its last digit must be 5.
6
∴ Number of choices for 1st digit and 2nd digit  P2
6

P
 30
6
2 5
5
 30
∴
The required number is 30.
Follow-up question
6 distinct letters are shown below.
O R A N G E
(a)
(b)
(a)
How many 6-letter strings can be formed by
using the above 6 letters without repetition?
How many 4-letter strings can be formed by
using the above 6 letters without repetition?
Number of 6-letter strings formed
 6!  720
 6  5  4  3  2 1
6!  360
720
Follow-up question
6 distinct letters are shown below.
O R A N G E
(a)
(b)
(b)
How many 6-letter strings can be formed by
using the above 6 letters without repetition?
How many 4-letter strings can be formed by
using the above 6 letters without repetition?
Number of 4-letter strings formed
 P46  360

5
4
4
3
3
6
6
5

 360
360
Example:
4 male and 5 female models are selected from 6 male and
8 female models to stand on a stage. In how many ways
can they be arranged in a row if models of the same sex
must stand next to each other?
Suppose the male models stand on the left.
4 male models
Number of ways of choosing 4 male
models from the 6 male models and
arrange them in order  P46
5 female models
Number of ways of choosing 5 female
models from the 8 female models and
arrange them in order  P58
Example:
4 male and 5 female models are selected from 6 male and
8 female models to stand on a stage. In how many ways
can they be arranged in a row if models of the same sex
must stand next to each other?
Suppose the male models stand on the left.
4 male models
∴
5 female models
Number of ways of arranging the 4 male models on the left
and the 5 female models on the right
 P46  P58
By multiplication rule of counting
4 male models
5 female models
Number of ways of arranging the 4 male models on the left
and the 5 female models on the right
 P46  P58
5 female models
4 male models
Number of ways of arranging the 5 female models on the left
and the 4 male models on the right
 P58  P46
The number of ways of arranging the
male models on the right is the same as
that of arranging the male
models on the left.
4 male models
5 female models
Number of ways of arranging the 4 male models on the left
and the 5 female models on the right
 P46  P58
5 female models
4 male models
Number of ways of arranging the 5 female models on the left
and the 4 male models on the right
 P58  P46
∴
The required number of arrangements
 P46  P58  2
 4 838 400
Follow-up question
2 boys and 3 girls are selected from 5 boys and 7 girls and
stand in a queue. In how many ways can they be arranged if
all the girls must stand in front of the boys?
3 girls
2 boys
Number of ways of choosing 3 girls from the 7 girls and arrange
them in a queue  P37
Number of ways of choosing 2 boys from the 5 boys and arrange
them in a queue  P25
∴ The required number of ways
 P37  P25
 4200