Transcript Book 6 Chapter 19 Permutations and Combinations

19
Permutation and
Combination
Case Study
19.1 Counting Principle
19.2 Permutation
19.3 Combination
Chapter Summary
Case Study
You may try to work it out by
counting but it won’t be easy.
If each team member has to shake
hands with all other members once,
then how many times does each
team need to shake hands?
Andy joins a summer camp.
On the first day, each team member has to shake hands with all other
members in the same team once.
If there are 4 members in each team, what is the total
number of times each team must shake hands?
Let the 4 team members be A, B, C and D respectively.
From the figure, we then have the following possibilities:
AB AC AD BC BD CD
Therefore, the total number of times each team must shake hands is 6.
P. 2
19.1 Counting Principle
A. Addition Rule in the Counting Principle
In this section, we will learn the concept of the counting
principle and how to apply two counting rules to determine
the number of possibilities that exist in a given situation.
Consider the following situation.
Mr. Lee plans to go to Macau this weekend. He can choose the ferry
service offered by company A or company B. The number of ferry trips
offered by company A and company B are 32 and 28 respectively.
Therefore the total number of ferry trips that he can choose from is
32  28  60
ferry tips from company A
ferry tips from company B
P. 3
19.1 Counting Principle
A. Addition Rule in the Counting Principle
We find the answers by applying the addition rule in the
counting principle which is stated as follows:
Addition Rule in the Counting Principle
If there are k different choices to finish a task and there are n1 ways
to finish the 1st choice, n2 ways to finish the 2nd choice, ... , and nk
ways to finish the kth choice, then the total number of ways to
finish the task  n1 + n2 + … + nk.
P. 4
19.1 Counting Principle
A. Addition Rule in the Counting Principle
Example 19.1T
The opening ceremony of a library will be held on a day either in
October or November. However, the ceremony will not be held on 1st
October. How many choices do they have for the day of the ceremony?
Solution:
If they choose a day in October, then they have 30 choices.
If they choose a day in November, then they have 30 choices.
The number of choices they have
 30  30
 60
P. 5
19.1 Counting Principle
B. Multiplication Rule in the Counting Principle
Suppose there is only one task. If the procedure for finishing the
task involves several steps, we have to use the multiplication rule instead
of the addition rule to count the number of ways to finish the task.
A fast food shop offers hamburger sets which consist of a hamburger
and a drink. A customer may choose one filling for the hamburger and
a drink from the menu.
We can list all the possible ways of choosing a hamburger set as below.
Beef + Coffee
Cheese + Coffee
Chicken + Coffee
Sausage + Coffee
Beef + Tea
Cheese + Tea
Chicken + Tea
Sausage + Tea
Beef + Orange juice
Cheese + Orange juice
Chicken + Orange juice
Sausage + Orange juice
Therefore, the number of ways of choosing a hamburger set is
4  3  12
number of ways of choosing
a filling from the 4 choices
number of ways of choosing
a drink from the 3 choices
P. 6
19.1 Counting Principle
B. Multiplication Rule in the Counting Principle
In general, if we want to perform a task with more than one
step and each step will not affect the others, we can apply the
multiplication rule in the counting principle.
Multiplication Rule in the Counting Principle
Suppose a task can be divided into k steps and each step will not
affect the others. If there are n1 ways to finish the 1st step, n2 ways
to finish the 2nd step, ... , and nk ways to finish the kth step, then the
total number of ways to finish the task  n1  n2  … nk.
P. 7
19.1 Counting Principle
B. Multiplication Rule in the Counting Principle
Consider the example of choosing a book from the shelf.
If, instead of choosing only one book, Lily has to choose a book from
each of the three categories, then how many choices are there?
k3
We can divide the task into three steps:
n1  10
Step 1: Choose a literary book from 10 choices
n2  15
Step 2: Choose a fiction book from 15 choices
n3  12
Step 3: Choose a science book from 12 choices
Therefore, the number of choices is 10  15  12  1800.
P. 8
19.1 Counting Principle
B. Multiplication Rule in the Counting Principle
Example 19.2T
A basketball tournament lasts for 4 days. On each day, there
are 8 matches. How many matches are there in total?
Solution:
By the multiplication rule,
the number of matches
 4 8
 32
The first step is to choose a
day and the second step is
to choose a match.
P. 9
19.1 Counting Principle
B. Multiplication Rule in the Counting Principle
Example 19.3T
The order numbers from a pizza shop are made up of a non-vowel
letter and a three-digit number from 101 to 999. How many possible
order numbers are there?
Solution:
By the multiplication rule,
the number of order numbers
 (26  5)  (999  100)
 18 879
P. 10
19.1 Counting Principle
B. Multiplication Rule in the Counting Principle
Example 19.4T
5 coins are put into 4 boxes. If each box can contain at most 5 coins,
in how many ways can the coins be put into the boxes?
Solution:
We can interpret the ‘step’ as ‘choosing a coin’.
By the multiplication rule,
the number of ways of putting the coins into the 4 boxes
 4 4 4 4 4
 1024
Since ‘choosing a coin’ is
the ‘step’ and there are 5
coins, there are 5 steps.
P. 11
19.1 Counting Principle
B. Multiplication Rule in the Counting Principle
Let us study a more complicated example.
The figure shows a road network connecting
4 cities A, B, C and D.
Helen drives her car from city A to city D.
How many ways are there for her to complete
the journey?
She can choose a route from A to D via B or a route from A to D via C.
In this case, we need to apply the addition rule and the multiplication
rule together.
By the multiplication rule,
the number of ways from A to D via B  3  3  9
the number of ways from A to D via C  3  2  6
By the addition rule,
the total number of ways from A to D  9  6
 15
P. 12
19.1 Counting Principle
B. Multiplication Rule in the Counting Principle
Example 19.5T
Robert and Alice are dining in a Chinese restaurant. They decide to order
a set meal. Out of 3 kinds of food: steamed, stirfried and deepfried, 2 can
be chosen. For steamed food, there are 8 choices. For stirfried food, there
are 12 choices. For deepfried food, there are 9 choices. How many ways
for them to order the set meal?
Solution:
There are three combinations:
1. Steamed food and stirfried food;
2. Steamed food and deepfried food;
3. Stirfried food and deepfried food.
Therefore, by the addition rule and the multiplication rule,
the number of choices
 8 12  8  9  12  9
 276
P. 13
19.2 Permutation
A. Factorial Notation
The product of the first n natural numbers is denoted by n!,
which is read as ‘n factorial’.
n!  n  (n – 1)  (n – 2)  …  2  1
For example,
4!  4  3  2  1  120
5!  5  4  3  2  1  720
Notice that 5!  5  4!.
We can press the function
key x! or n! on a
calculator to find the value
of n factorial.
In general, we have:
n!  n  (n – 1)!
P. 14
19.2 Permutation
A. Factorial Notation
We can express the product of some integers in terms of
factorial notation.
For example:
7  6  5  4  3  2 1
3  2 1
7!

3!
7654 
 2  4  6  8  10  12  14  27  (1  2  3  4  5  6  7)
 27  7!
P. 15
19.2 Permutation
B. Concept and Notation of Permutation
The letters A, B and C can be arranged as:
ABC, ACB, BAC, BCA, CAB, CBA
Each of the above arrangements, such as ABC, is called a permutation.
A permutation of n objects is an arrangement of the objects
in a definite order.
In the above example, each arrangement of the letters A, B, C consists of
a complete list of the letters without repetition.
So there are six permutations of these letters.
P. 16
19.2 Permutation
B. Concept and Notation of Permutation
Consider arranging 4 letters A, B, C and D in a line.
Position 1 Position 2 Position 3 Position 4
We can arrange the letters using the following 4 steps.
(a) Consider the above figure. Select a letter and write it down in
position 1. This can be done in 4 ways.
(b) After selecting the letter in position 1, there are 3 letters left.
For position 2, a letter can be selected in 3 ways.
(c) After selecting the letters in positions 1 and 2, there are 2 letters left.
For position 3, a letter can be selected in 2 ways.
(d) For the final position, a letter can be selected in 1 way.
By the multiplication rule in the counting principle, the number of ways
to arrange 4 different letters into a line  4  3  2  1  4!.
The number of permutations of n distinct objects without
repetition is n  (n  1)  …  2  1  n!.
P. 17
19.2 Permutation
B. Concept and Notation of Permutation
Example 19.6T
A four-digit number is formed with the digits ‘3, 5, 7, 8’ where each
digit can be used only once in a number.
(a) How many different numbers can be formed?
(b) List all the even numbers formed.
Solution:
(a)
(b)
Number of four-digit numbers  4!
 24
 The even numbers formed are:
3578, 3758, 5378, 5738, 7358, 7538.
P. 18
19.2 Permutation
B. Concept and Notation of Permutation
Sometimes, we need to take out r objects from n distinct objects
and arrange them in order.
We regard two arrangements as different if the order of the objects is
different.
In this case, each arrangement is called a permutation of r objects
selected from n objects.
Consider the following figure.
Position 1
Position 2
...
Position (r – 1)
Position r
For position 1, n objects can be selected.
For position 2, (n – 1) objects can be selected.
...
For position r, (n – r  1) objects can be selected.
After the first (r  1)
selections, the number of
objects left is n  (r  1)
 n  r  1.
P. 19
19.2 Permutation
B. Concept and Notation of Permutation
By the multiplication rule,
the total number of permutations
 n  (n – 1)  (n – 2)  ...  (n – r  1)
n  (n  1)  (n  2)  ... (n  r  1)  (n  r )  ...1

(n  r )  ...1
n!

(n  r )!
n
which is denoted by Pr , where n and r are positive integers.
Position 1
Position 2
n objects (n – 1) objects
...
Position (r – 1)
Position r
(n – r  2) objects (n – r  1) objects
The number of permutations of r objects from n distinct objects
n!
without repetition  Prn 
(n  r )!
P. 20
19.2 Permutation
B. Concept and Notation of Permutation
Notes:
From the formula Prn 
n!
, when r  n, Prn is just the number of
(n  r )!
permutations of n objects:
n!
n!
Pnn 

(n  n)! 0!
Note that 0! have not been defined. In order to be consistent, we define
n!
0!  1. Thus, Pnn 
1
 n!
which is the same as the previous result.
We can use the function key
nPr on a calculator to find
the value of Prn.
P. 21
19.2 Permutation
B. Concept and Notation of Permutation
Example 19.7T
Given six digits: 2, 4, 5, 6, 8, 9. How many different three-digit
numbers can be formed if each digit can be used only once?
Solution:
Number of possible outcomes
 P36
 120
P. 22
19.2 Permutation
C. Applications of Permutation
Suppose Andy, Bobby and Chris are members of the class
committee. A chairperson, a secretary and a treasurer are to be
selected from them. How many possible results are there?
By listing all of the possibilities, we find that there are 6 different
possible results.
Chairperson
Secretary
Treasurer
However, it is time-consuming
Andy
Bobby
Chris
to list all of the possibilities if
Andy
Chris
Bobby
more people are involved.
Bobby
Bobby
Chris
Chris
If we consider the chairperson
as position 1, the secretary as
position 2 and the treasurer as
position 3, the problem can be
regarded as a permutation of 3 objects.
Andy
Chris
Andy
Bobby
Chris
Andy
Bobby
Andy
Therefore, the number of possible results  3!  6, which is the same
as we found by listing.
P. 23
19.2 Permutation
C. Applications of Permutation
Example 19.8T
5 girls and 3 boys are selected as members of the school debate
team which is comprised of a first speaker, a second speaker and a
third speaker. Suppose Lily is the first speaker. Find the number
of different teams that can be formed.
Solution:
2 speakers are left to be selected from 7 students.
Number different teams
 P27
 42
P. 24
19.2 Permutation
C. Applications of Permutation
Example 19.9T
The Chan family is having a photo taken at the entrance to Disneyland.
The family consists of Mr. Chan, Mrs. Chan and their three children.
Find the number of ways they could line up if
(a) Mr. and Mrs. Chan must stand at the two sides;
(b) Mr. and Mrs. Chan must stand next to each other;
(c) Mr. Chan stands in the middle and Mrs. Chan stands next to him.
Solution:
(a) As the positions of Mr. and Mrs. Chan are fixed, it is necessary to
arrange the children only.
Moreover, Mr. and Mrs. Chan can stand in 2 ways.
Number of ways  2  3!  12
(b) As Mr. and Mrs. Chan must stand next to each other, we can regard
them as one unit. Therefore, we have (5 – 1)! arrangements.
Moreover, Mr. and Mrs. Chan can stand in 2 ways.
By the multiplication rule, the number of ways  (5 – 1)!  2!  48
P. 25
19.2 Permutation
C. Applications of Permutation
Example 19.9T
The Chan family is having a photo taken at the entrance to Disneyland.
The family consists of Mr. Chan, Mrs. Chan and their three children.
Find the number of ways they could line up if
(a) Mr. and Mrs. Chan must stand at the two sides;
(b) Mr. and Mrs. Chan must stand next to each other;
(c) Mr. Chan stands in the middle and Mrs. Chan stands next to him.
Solution:
(c) As Mr. and Mrs. Chan must stand next to each other and the
position are fixed, it is necessary to arrange the children only.
Moreover, Mr. and Mrs. Chan can stand in 2 ways.
Number of ways  2  3!  12
P. 26
19.3 Combination
A. Concept and Notation of Combination
Combination concerns the number of ways to choose r objects
from n objects, but unlike permutation, the order of the r objects
is not considered.
Suppose we want to choose 3 distinct letters are chosen from 5 letters
A, B, C, D and E.
We can choose {A, B, C}, {B, C, E}, {C, D, E} and so on.
Since we do not concern about the order of the letters, the following
6 permutations are regarded as the same selection: {A, B, C}.
{A, B, C} , {A, C, B}, {B, A, C}, {B, C, A}, {C, A, B}, {C, B, A}
Such a selection is called a combination.
A combination is a selection of certain objects without
considering the order.
P. 27
19.3 Combination
A. Concept and Notation of Combination
We know that the number of permutations of 3 letters from
5 letters is P35.
To find the number of combinations:
Step 1:
Select any 3 letters from the 5 letters. Let the number of ways be N.
Step 2:
Arrange the 3 letters selected in Step 1. The number of ways is 3!.
By the multiplication rule in the counting principle,
N  3! P35
P35
N
3!
 10
P35
We denote
by C35 .
3!
P. 28
19.3 Combination
A. Concept and Notation of Combination
In general, we denote
P!
n!
Crn  
r! (n  r )!r!
where n and r are positive integers.
The number of combinations of r objects from n distinct objects
P!
n!
without repetition  Crn  
r! (n  r )!r!
For example,
5!
C25 
(5  2)!2!
5  4  3  2 1

(3  2 1)  (2 1)
5 4

2 1
 10
We can use the function key
nCr on a calculator to find
the value of Crn.
P. 29
19.3 Combination
A. Concept and Notation of Combination
Example 19.10T
Three different numbers are selected from {1, 4, 5, 7, 9}.
(a) How many different combinations of the numbers are there?
(b) List all the combinations that include ‘5’.
Solution:
(a) Total number  5
Number to be selected  3
5
Number of combinations  C3
 10
(b) Possible combinations are:
{1, 4, 5}, {1, 7, 5}, {1, 9, 5}, {4, 7, 5}, {4, 9, 5}, {7, 9, 5}.
P. 30
19.3 Combination
B. Applications of Combination
Let us see some of applications of combination.
P. 31
19.3 Combination
B. Applications of Combination
Example 19.11T
In a class of 30 students, 6 are selected to be the class representatives.
How many ways are there to select the representatives if
(a) both the monitor and monitress are selected?
(b) both the monitor and monitress are not selected?
Solution:
(a) Total number of students  30 – 2
 28
Number of students to be selected  6 – 2
4
The total number of ways  C428
 20 475
(b) Total number of students  30 – 2
 28
The total number of ways  C628
 376 740
P. 32
19.3 Combination
B. Applications of Combination
In solving counting problems, it is important to identify
whether permutation or combination is involved.
1. For problems that involve ordering, Prn should be used.
2. For problems in which ordering is not important, Crn should be used.
P. 33
19.3 Combination
B. Applications of Combination
Example 19.12T
A research team consists of 10 boys and 6 girls. 3 of them are selected to
present their studies to a class.
(a) In how many ways can the team be formed?
(b) If the team consists of 2 boys and 1 girl, in how many ways can the
team be formed?
(c) If the team consists of 1 boy and 2 girls, in how many ways can the
team be formed?
Solution:
16
(a) The total number of ways  C3  560
(b) Number of ways to select 2 boys  C210  45
Number of ways to select 1 girl  C16  6
 Total number of ways  45 6  270
(c) Number of ways to select 1 boy  C110  10
Number of ways to select 2 girls  C26  15
 Total number of ways  1015  150
P. 34
Chapter Summary
19.1 Counting Principle
1. Addition Rule in the Counting Principle
There are k different choices to finish a task and there are n1 ways
to finish the 1st choice, n2 ways to finish the 2nd choice, ... , and
nk ways to finish the kth choice, then the total number of ways to
finish the task  n1  n2  ...  nk.
2. Multiplication Rule in the Counting Principle
Suppose a task can be divided into k steps and each step will not
affect the others. If there are n1 ways to finish the 1st step, n2 ways
to finish the 2nd step, ... , and nk ways to finish the kth step, then
the total number of ways to finish the task  n1  n2  … nk.
P. 35
Chapter Summary
19.2 Permutation
1. A permutation of n objects is an arrangement of the objects
in a definite order.
2.
The number if permutations of n distinct objects without repetition is
 n!
 n  (n  1)  (n  2)  …  2  1
3. A permutation of r objects selected from n objects is an arrangement
of r objects from n distinct objects.
4.
The number of permutation of r objects from n distinct objects
without repetition
 Prn
n!

(n  r )!
P. 36
Chapter Summary
19.3 Combination
1. A combination is a selection of certain objects without
considering the order.
2.
The number of combinations of r objects from n distinct
objects without repetition
 Crn
P!

r!
n!

(n  r )!r!
P. 37