Transcript permutation - H1 H2 A Maths tuition

NO ONE CAN PREDICT TO WHAT HEIGHTS YOU CAN SOAR
EVEN YOU WILL NOT KNOW UNTIL YOU SPREAD YOUR WINGS
Chapter 19
PERMUTATIONS
AND
INTRODUCTION
( In our daily lives, we often need to
enumerate
“events”
such
as
the
arrangement of objects in a certain way,
the partition of things under a certain
condition, the distribution of items
according to a certain specification and so
on.
( In this topic, we attempt to formulate a
general principle to help us to answer
some counting problems like :
INTRODUCTION
z In how many ways can the numbers
0,1,2,3,4,5,6,7,8,9 be used to form a
4-digit number ?
z In how many ways can 4
representatives be chosen from a
group of 10 students?
Multiplication Principle
Example 1: There are 3 roads connecting
city A and city B, and 4 roads connecting
city B and city C. How many ways are
there to travel from city A to city C via city
B?
Multiplication Principle
Solution:
City
A
City
B
City
C
Total number of ways = 3 x 4 = 12
Multiplication Principle
In this example, we may regard
( travelling from A to C via B as a task,
( travelling from A to B as stage1, and from B
to C as stage 2.
( stage1 and stage 2 are necessary or
chained/linked for the task to be completed.
Multiplication(r-s) Principle
z Then we can develop the Multiplication
Principle which states that if it requires
two necessary stages to complete a task
and if there are r ways and s ways to
perform stage 1 and stage 2 respectively,
then the number of ways to complete the
task is r  s ways.
Multiplication Principle
Certainly, we can extend the Multiplication
Principle to handle a task requiring more
than 2 stages:
z If a task/process consists of k linked
steps/stages, of which the first can be
done in n1 ways, the second in n2
ways,…, the r th step in nr ways, then the
whole process can be done in
n1  n2  …  nr  …  n k ways.
- TWO BASIC PRINCIPLES-
Addition Principle
z If a task can be carried out through n possible
distinct(mutually exclusive)
processes(sub-tasks) and if the first process can
be done in n1 ways, the second in n2 ways,…,
the r th tasks in nr ways, then the task can be
done in a total of
n1 + n2 + … + nr + … + nk ways.
- TWO BASIC PRINCIPLES-
Addition Principle
Example 2:
z In how many ways can a man travel from
Singapore to Tokyo if there are 4 airlines
and 3 shipping lines operating between
the 2 cities ?
Solution: Task: Travel to Tokyo from Singapore
Task by air – 4 ways
Task by sea – 3 ways
Total number of ways = 4 + 3 = 7
- TWO BASIC PRINCIPLES-
Addition Principle
Note:
z Since the man cannot travel by air and
sea at the same time, we say that the two
(approaches in carrying out the) tasks are
mutually exclusive .
- TWO BASIC PRINCIPLES-
Addition Principle
Most questions may be a combination of the
two different principles as shown below:
Example 2a:
z In how many ways can we select 2 books
of different subjects from among 5 distinct
Science books, 3 distinct Mathematics
books and 2 distinct Art books?
- TWO BASIC PRINCIPLES-
Addition Principle
Solution:There are three cases to consider:
Case 1: Select 1 Science & 1 Maths book.
No. of ways = 5 x 3 = 15
Case 2: Select 1 Science & 1 Art book.
No. of ways = 5 x 2 = 10
Case 3: Select 1 Maths & 1 Art book.
No. of ways = 3 x 2 = 6
Hence, combining Case 1, 2 and 3, total
no.of ways of selecting 2 books of different
subjects = 15 + 10 + 6 = 31
- TWO BASIC PRINCIPLES-
Ex 2a: Solution
(A different presentation)
2 books,
different
subjects
2
Maths
Science
= 3 x 5 = 15
Maths
Art
=3x2=6
Science
Art
= 5 x 2 = 10
Total = 31
PERMUTATIONS
DEFINITION
z Let S be a set of n objects.
z A permutation (arrangement) of r objects drawn
from the set S( where r < n) is a sub-set of S
containing r objects in which the order of the
objects in the sub-set is taken into consideration.
PERMUTATIONS
z Are the following permutations?
z a) Arranging 3 different books on a shelf.
z b) Choose 4 books from a list of 10 titles to take
away for reading.
z c) Seating 500 graduates in a row to receive their
degree scrolls.
z d) Forming three-digit numbers using the integers
1, 2, 3, 4, 5.
z e) Select two students from a CG to attend a talk.
PERMUTATIONS
Illustration
S={
} = set of 5 objects
Permutations( order within group is considered)
Of 3 objects
 different

permutations
 of 3objects

Of 4 objects
 different

permutations
 of 4objects

- PERMUTATIONS-
Interpretation of
n
Pr
z When r objects taken from n different objects are
permuted (arranged), the number of possible
permutations denoted by nPr , is given by
nP =
r
n(n - 1)(n - 2) … (n - r + 1)
= n(n  1)( n  2)  ...  (n  r  1)( n  r )( n  r  1)  ...  2  1
(n  r )( n  r  1)  ...  2  1
n!
=
(n  r)!
- PERMUTATIONS-
Interpretation of
n
Pr
Special case :
When all the n different objects are permuted,
n
thenumber of permutations is = Pn = n!
- PERMUTATIONS-
Rules Of Permutations
L1: No. of arrangementsof all n
different objects in a row / line  Pn  n !
n
L2 : No. of arrangementsof r out of n
different objects in a row / line  Pr
n
- PERMUTATIONS-
Example 3
z In how many ways can the letters A, B, C
be arranged ?
Solution:
3
No. of ways = P = 3! = 6
3
- PERMUTATIONS-
Example 4
z There are 10 vacant seats in a bus. In
how many ways can 2 people seat
themselves ?
Solution:
No. of ways = 10P2
= 10 x 9
= 90
- PERMUTATIONS-
Example 5
z Find the number of ways of filling 5
spaces by selecting any 5 of 8 different
books.
Solution:
No. of ways = 8P5
=8x7x6x5x4
= 6720
- CONDITIONAL PERMUTATIONS-
Example 6
z How many arrangements of the letters of the
word ‘BEGIN’ are there which start with a
vowel ?
Solution:
z The first letter must be either E or I ie 2
ways. The rest can be arranged in 4! ways.
Therefore no. of arrangements = 2 x 4! = 48
- CONDITIONAL PERMUTATIONS-
Example 6
z How many arrangements of the letters of the
word ‘BEGIN’ are there which start with a
vowel ?
Solution:( A different presentation)
E,I
Arrange using 4 letters ( minus E or I)
No of arrangements beginning with a vowel
= 2 x 4! = 48
- PERMUTATIONS-
Rules Of Permutations
L1: No. of arrangementsof all n
different objects in a row / line  Pn  n !
n
L2 : No. of arrangementsof r out of n
different objects in a row / line  Pr
n
- CONDITIONAL PERMUTATIONS-
Example 7
z In how many ways can the letters of the
word ‘ORANGE’ be arranged with the
restriction that
(i) the 3 vowels must come together
(ii) the 3 vowels must not come together
(iii) the 3 vowels are all separated?
- CONDITIONAL PERMUTATIONS-
Example 7
z In how many ways can the letters of the word
‘ORANGE’ be arranged with the restriction that
(i) the 3 vowels must come together
Be
Solution:
(i)
R
objective
N
G
{ O,A,E }
Strategy: bundle the 3 vowels together as 1 unit but
remember you will have to arrange the 3 vowels within
this unit in 3! ways.
No. of words in which the 3 vowels are together
= 4! x 3! = 144
- CONDITIONAL PERMUTATIONS-
Example 7
z In how many ways can the letters of the
word ‘ORANGE’ be arranged with the
restriction that
(ii) the 3 vowels must not all come together
Solution:
No. of ways to arrange all 6 letters = 6! = 720
No. of arrangements in which the vowels are
together = 144
Therefore, the no. of arrangements in which the
vowels are not all together = 720 – 144 = 576
- CONDITIONAL PERMUTATIONS-
Example 7
z In how many ways can the letters of the word
‘ORANGE’ be arranged with the restriction that
(iii) the 3 vowels are all separated?
Solution:
Qn: How do we separate some objects?
Ans: We use the other objects as separators!
Thus we use the consonants to separate the 3
vowels as in the configuration below:
 C C  C 
- CONDITIONAL PERMUTATIONS-
Example 7
 C C  C 
C being the position of a consonant and
position of a vowel.
the
The 3 C’s can be arranged in 3! ways; and we can use 4
positions to put in the 3 vowels in 4
ways.
3
Thus the number of ways of arranging ‘ORANGE’ so
P
that the 3 vowels are separated = 3! X 4 P = 144
3
- CONDITIONAL PERMUTATIONS-
Example 8
z Given six digits 1,2,4,5,6,7. Find the
number of 6-digit numbers which can be
formed using all 6 digits without repetition
if
z i) there is no restriction;
z ii) the numbers are all even;
z iii) the numbers begins with ‘1’ and end
with ‘5’.
- CONDITIONAL PERMUTATIONS-
Example 8
Solution:
(i) No. of ways = 6! = 720
2,4,6
(ii) For each no. formed to be even, the last
digit must be occupied by 2, 4 or 6 i.e.
there are 3 ways to fill the last digit.
The first 5 digits can be filled in 5! ways.
Therefore, the total no. of even nos. than
can be formed = 3 x 5! = 360
- CONDITIONAL PERMUTATIONS-
Example 8
1
5
(iii) The first digit(1) and the last digit(5) are
fixed (no arrangement needed).
The remaining 4 digits can be filled in 4!
ways.
Therefore, the total no. of such nos.
formed = 1 x 4! = 24
COMBINATIONS
z A Combination (Selection) of a given number of
articles is a sub-set of articles selected from those
given where the order of the articles in the subset is
not taken into consideration.
z Examples of combinations
z a) Pick a set of three integers from the numbers 1, 2, 3, 4, 5.
z b) Choose a committee of 3 persons from a group of 10
people.
z c) From a box of 200 lucky draw tickets, 3 to be drawn as
consolation prize.
COMBINATIONS
z Consider the number of permutations of three
different books A, B, C on a self:
z ABC, ACB, BAC, BCA, CAB, CBA ----- 3! = 6 ways
z If order is not important, then there is only one way to
choose all the three different books,
i.e. simply {A, B, C}
COMBINATIONS
Illustration
Possible selections or combinations of 3
objects drawn from the set { A, B, C, D }
are
{ A, B, C } , { A, B, D }, { A, C , D},{ B, C , D}.
No. of possible selections or combinations of
3 objects drawn from the set { A, B, C, D }
4
= 4 = C = 4P3 / 3!
3
COMBINATIONS
Possible selections or combinations of 2
objects drawn from the set { A, B, C, D }
are { A, B } , { A, C }, { A, D } , { B, C },
{ B, D } , { C, D }.
= 6 or
4
C2
= 4P2 /
2!
COMBINATIONS
An exercise
Possible selections or combinations of 2
objects drawn from the set { A, B, C, D,E }
are
{A, B} , {A, C} , {A, D} , {A, E} , {B, C} ,
{B, D} , {B, E} , {C, D} , {C, E} , {D, E}
No. of possible selections or combinations of
2 objects drawn from the set {A, B, C, D, E }
5
= 10 = C = 5P2 / 2!
2
COMBINATIONS
An exercise
Possible selections or combinations of 3
objects drawn from the set { A, B, C, D,E }
are
{A, B, C} , {A, B, D} , {A, B, E} , {A, C, D}
{A, C, E} , {A, D, E} , {B, C, D} , {B, C, E}
{B, D, E} , {C, D, E}
No. of possible selections or combinations of
2 objects drawn from the set {A, B, C, D, E }
5
= 10 = C = 5P3 / 3!
3
COMBINATIONS
Illustration
Possible selections or combinations of 6
nos. drawn from the set { 1,2,3,4,…,45 }
are
impossible to list out without the aid of a
computer.
No. of possible selections or combinations of
6 nos. drawn from the numbers 1 to 45
inclusive = 45 C = 8 145 060
6
COMBINATIONS
z The number of combinations of r objects
taken from n unlike objects is nC r , where
n
Cr
n!
n(n  1)(n  2)...( n  r  1)
= r ! (n  r )! 
r!
n
Pr
=
r!
- COMBINATIONS-
Example 9
z In how many ways can a committee of 3
be chosen form 10 persons ?
Solution:
z No. of ways = 10C3 = 120
- COMBINATIONS-
Example 10
z In how many ways can 10 boys be divided into 2
groups
(i) of 6 and 4 boys (unequal sizes)
Solution:
Select
First group of 6
Select
Second group of 4
No. of ways of forming groups = 10C6 X 4C4
= 210
- COMBINATIONS-
Example 10
z In how many ways can 10 boys be divided into 2
groups
(ii) of 5 and 5 boys (equal sizes)
Solution:
Select
First group of 5
Select
Second group of 5
No. of ways of forming groups = (10C5 X 5C5)/2!
= 126
- COMBINATIONS-
Example 11
z A committee of 5 members is to be
selected from 6 seniors and 4 juniors. Find
the number of ways in which this can be
done if
a) there are no restrictions,
b) the committee has exactly 3 seniors,
c) the committee has at least 1 junior
- COMBINATIONS-
Example 11
Solution:
a) If there are no restrictions, the 5 members
can be selected from the 10 people in 10C5
= 252 ways
- COMBINATIONS-
Example 11
Solution:
b) If the committee has exactly 3 seniors,
these seniors can be selected in 6C3 ways.
The remaining 2 members must then be
juniors which can be selected from the 4
juniors in 4C2 ways.
By the multiplication principle, the no. of
committees with exactly 3 seniors is
6C  4C = 120
3
2
- COMBINATIONS-
Example 12
Solution:
c) No. of committees with no juniors
= 4C0  6C5 = 6
No. of committees with at least 1 junior
= (total no. of committees) – (no. of
committees with no junior)
= 252 – 6 = 246
the end