1.9 Permutations and
Combinations:
1.9.1
Permutations
Problem :
A team has 10 players. Only six can fit into one photo frame. Manager has to be
in each of the photo session. A photographer was asked to give an estimate for all
the different combinations of photos. A photo with frame costs Rs.22. Find out
the estimate given by photographer to the Manager.
Problem :
In a hexagon how many triangles can be formed?
Is it not
interesting to solve the above problems?
Introduction:
We have learnt that the sum
of 1st ‘n’ natural numbers is given by
= 1+2+3+4
…..+n =
What if we multiply these
natural numbers instead of adding them?
1*2=2
1*2*3 =6
1*2*3*4 = 24…
We use the notation n!(
called ‘n factorial’) to denote the product of ‘n; consecutive natural number from 1.
n!=
1*2*3*4….*n
What do we observe?
1! =1
2!=
1*2=2=2*1!
3!=1*2*3=6
=3*2!
4! =1*2*3*4 = 24= 4*3!
n!
= n*(n-1)*(n-2)*(n-3)*…………3*2*1=n*(n-1)!
n!
= n*(n-1)! Or n = 
1.9.1 Example1 :
Let A , B and C be students of your class . You are
asked to arrange them in rows as follows:
1. with rows of 2 students
2. with rows of 3 students
How many arrangements can
you make in each of the case?
Working:
1.9.1.1: Arrange 2
rows with two
students in each row
1.Let
us ask A to stand first. We are left with B and C. We can ask B or C to stand
behind A ( so we have 2 arrangements AB and AC)
2.Let
us ask B to stand first. We are left with A and C. We can will ask A or C to stand behind B (so
we have 2 arrangements BA and BC)
3.Let
us ask C to stand first. We are left with A and B. We can ask A or B to stand behind C (so we
have 2 arrangements CA and CB)
|
I position |
A |
B |
C |
|||
|
II
position |
B |
C |
A |
C |
A |
B |
In all we have 6(=3*2) ways
of arrangements: (AB, AC), (BA, BC), (CA, CB)
1.9.1.2: Arrange 3
rows with 3
students in each row:
1.Let
us ask A to stand first. We are left with B and C. We can ask B or C to stand behind
A( so we have 2 arrangements ABC and ACB)
2.Next
let us ask B to stand first. We are left with A and C. We can ask A or C to
stand behind B(so we have 2 arrangements BAC and BCA)
3.Next
let us ask C to stand first. We are left with B and A. We can ask A or B to
stand behind C (so we have 2 arrangements CAB and CBA)
|
I position |
A |
B |
C |
|||
|
II position |
B |
C |
A |
B |
C |
A |
|
III
position |
C |
B |
C |
C |
B |
C |
In all we have 6(=3*2) ways
of arrangements: (ABC, ACB), (BAC, BCA), (CAB, CBA)
1.9.1 Example 2:
Let us take the case of 4 students A, B, C and D in the above example. How many
different Queues can you form?
1. With Queues of 2
students
2. With Queues of 3
students
How many arrangements can
you make in each of the case?
Working:
1.9.1.2.1: Arrange
Queues of 2 students
|
I position |
A |
B |
C |
D |
||||||||
|
II position |
B |
C |
D |
A |
B |
C |
D |
A |
B |
C |
D |
A |
Totally we have 12(=4*3) ways
of arrangements (AB, AC, AD),( BA, BC, BD),( CA, CB, CD),( DA, DB, DC
1.9.1.2.2: Arrange
Queues of 3 students:
|
I position |
A |
B |
C |
D |
||||||||||||||||||||
|
II position |
B |
C |
D |
A |
B |
C |
D |
A |
B |
C |
D |
A |
||||||||||||
|
III
position |
C |
D |
B |
D |
C |
D |
B |
D |
C |
D |
B |
D |
C |
D |
B |
D |
C |
D |
B |
D |
C |
D |
B |
D |
We have:
6(=3*2) Queues with A in
the front (ABC, ABD, ACB ACD, ADB, ADC )
6 Queues with B in the
front (BAC, BAD, BCA, BCA, BDA, BDC)
6 Queues with C in the
front (CAB, CAD, CBA, CBD, CDA, CDB)
6 Queues with D in the
front (DAB, DAC, DBA, DBC, DCA, DCB)
Totally we have 24(=4*3*2)
ways arrangements
The number of arrangements
(‘permutations’) of ‘n’ things taken ‘r’ things at a time is denoted by nPr
Let us analyse
our workings:
|
Examples |
Total Number of students(n) |
Number of students in the row(r) |
Number of arrangements |
Notation |
Meaning |
|
Example
1.1 |
3 |
2 |
6 |
3P2 |
Permutation
of 3 objects taken 2 at a time |
|
Example
1.2 |
3 |
3 |
6 |
3P3 |
Permutation
of 3 objects taken 3 at a time |
|
Example
2.1 |
4 |
2 |
12 |
4P2 |
Permutation
of 4 objects taken 2 at a
time |
|
Example
2.1 |
4 |
3 |
24 |
4P3 |
Permutation
of 4objects taken 3 at a time |
Permutation is a way of
arranging objects in an orderly way.
1.9.2
Fundamental Principles of counting:
Assume that you and your
friend go to school together. Assume that there are 4 routes to go to your
friend’s house from your house and 3 routes from your friend’s house to the
school. Also, Assume that you have a pet dog ‘Jony’ which some times
follows you.
Find out how many different
routes, ‘Jony’ can
take to reach your house from the school, via your friend’s house?
Note: There are 4 routes to
reach your friend’s house from your house and there are 3 routes to reach
school from your friend’s house.
‘Jony’ can take any of the three routes
(A or
B or
C)
from the school to reach your friends house. From your friend’ house it can
reach your house in four ways (1 or 2 or 3 or 4).
The following table lists
the different ways that ‘Jony’ can take to reach your house from the school via
your friend’s house.
|
No |
From School to friend’s house |
From friend’s house to your
house |
Route |
|
1 |
A |
1 |
A-1 |
|
2 |
2 |
A-2 |
|
|
3 |
3 |
A-3 |
|
|
4 |
4 |
A-4 |
|
|
5 |
B |
1 |
B-1 |
|
6 |
2 |
B-2 |
|
|
7 |
3 |
B-3 |
|
|
8 |
4 |
B-4 |
|
|
9 |
C |
1 |
C-1 |
|
10 |
2 |
C-2 |
|
|
11 |
3 |
C-3 |
|
|
12 |
4 |
C-4 |
‘Jony’ can chose
12(=3*4) ways of reaching your house from the school.
Similarly there are 12 (=4*3) ways of reaching
school from your house.
In summary, if an
activity can be done in ‘m’ ways and another activity is done in ’n’ ways then
the 2 activities together can be done in (m*n) ways.
To find the formula for number of arrangements (Permutations)
possible among ‘n’ things with ‘r’ things taken at a time.
Method:
Let us assume that we have
‘n’ number of objects and ‘r’ number of boxes.
Let boxes be numbered as 1,2,3,….(r-1),r.
Our task is to fill these
boxes by taking ‘r’ objects at a time from ‘n’ number of objects.
|
Box No. |
1 |
2 |
3 |
…… |
(r-1) |
r |
|
No of
ways |
n |
(n-1) |
(n-2) |
|
n-(r-2) |
n-(r-1) |
1. First box can be filled in n different ways.
2. Second box can be filled
in (n-1) different ways.
3. Third box can be filled in
(n-2) different ways.
…
r. r’th
box can be filled in
(n-r+1) different ways.
By fundamental principle, r
boxes can be filled in
n*(n-1)*(n-2)*(n-3)…..(n-r+1)
ways
This is the number of
permutations of ‘n’ things taken ‘r’ at a time and is denoted by nPr
nPr =
n*(n-1)*(n-2)*(n-3)…..(n-r+1) =======è(1)
By substituting r=n in the
above equation we get
nPn
= n*(n-1)*(n-2)*(n-3)…..(n-n+1)
= n*(n-1)*(n-2)*(n-3)…..*1
nPn =n!
Let us multiply and divide
RHS of equation (1) by the same term (n-r)*(n-r-1)*…..3*2*1 we get
nPr
= {n*(n-1)*(n-2)*(n-3)…..(n-r+1)*
(n-r)*(n-r-1)*…..3*2*1}/{(n-r)*(n-r-1)*…..3*2*1}
=
{
n!= 1*2*3……*n and (n-r)! =
1*2*3….*(n-r)}
Since nPr= ,
Note:
nP1=
= 
= n
nP1
=n
nP(n-1)
=
(Substitute r = (n-1) in nPr)
= n! (1!= 1)
nP(n-1)=
n!= nPn
(n-r)!
= n!/ nPr{ nPr=
n!/(n-r)! }
By substituting r=n in the
above equation we get
0!
= n!/
nPn
= n!/n!
( nPn=
n! )
=1
0! =1
We summarise the following:
|
n = n!/(n-1)! |
|
nPn =n! |
|
nP1 =n |
|
nP(n-1)= n!= nPn |
|
0! =1 |
1.9.2 Problem 1 :
In how many ways the letters of the word COMPUTER can
be arranged? How many of these begin with M?
Solution:
Since the number of letters
in the word = 8, we can form 8!=40320 different words
of 8 letters.
|
Position
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
Letters |
M |
Fill
from letters among C,O,P,U,T,E,R |
||||||
If M is fixed in the first
place then we are left with (n=7) letters to fill the other 7 places.
Then, the number of possibilities
are = 7! =5040 words
1.9.2 Problem 2:
How many 3 digit numbers can be formed using the digits2,3,4,5and
6 without repetitions? How many of these are even numbers?
Solution:
We know nPr
= : It is given that n=5(2,3,4,5,6)
and r=3
|
Hundred |
Ten |
Unit |
|
Choose
From (2,3,4,5,6) |
||
Number of 3 digit numbers which can be
formed = 5P3 = 
= 
=60
Among these, even numbers
are those ending with 2,4 and 6(unit place is 2 or 4 or
6)
Let us find out how many 3
digit numbers can be formed that ends with 2.
|
Hundred |
Ten |
Unit |
|
Choose
From (3,4,5,6) |
2 |
|
Even numbers:
Since the unit place is
already taken by 2,
we can only have 3, 4,5and 6 in hundredth and tenth places.
Since 2 will always be in
the units place, we only
need to find all the 2
digit numbers possible with 3,4,5 and 6(r=2).
The number of 2 digit
numbers that can be formed using (n=4) digits (3,4,5,6)
are =4P2= 
= 4*3 = 12
So with 2 in units place we
can have 12 3-digit numbers.
Similarly with 4 in units
place we can have 12 3-digit numbers.
Similarly with 6 in units
place we can have 12 3-digit numbers.
In all we can have 36(=12+12+12) even numbers.
1.9.2 Problem 3:
How many 3 digit numbers can be formed using 0,1,2,3?
Solution:
Here n=4 and r=3.
The number of 3 digit
numbers that can be formed are 4P3 =
= 4!=24
However, in case of 3 digit
numbers, a number starting with 0 can not be considered as a 3 digit number
(012 is not a 3 digit number but it is a 2 digit number).
Hence from the result we
need to subtract the number of 3-digit numbers starting with 0.
Let us find out the number
of 3-digit numbers starting with 0 .So we have n=3( 1,2,3)
and r=2
With 0 as the first digit,
number of 3-digit numbers we can make=3P2 = 3! =6.
Thus we can make 18(=24-6) 3-digit numbers from 0,1,2,3.
1.9.2 Problem 4:
In how many ways can 7 different books be arranged in a shelf? In how many ways
can we arrange three particular books so that they are always together?
Solution:
Here n=7. So the number of
ways these books can be arranged is 7! = 5040.
Let the books be A,B,C,D,E,F,G.
It is said that three books need to be together. Let they be B, C and D. For easy
understanding we can tie these 3 books together and call this bundle as H. So we are left with A,H,E,F,G(5
objects). These can be arranged in 5!=120 ways.
Since H is bundle of 3
books (B,C,D). The books in the bundle H themselves
can be arranged in 3!=6
ways.
Thus we have 6*120=720
ways of arranging 7 books such that 3 books are always together.
1.9.3
Combinations:
1.9.3 Example 1 :
Let A , B and C be students of your class. A photographer was asked to take
photos such that:
1. Different combinations
of 2 students in one snap shot
2. Different combinations
of 3 students in a snap shot
How many shots does he need
to take?
Working:
Example 1.1: Photo
session for group of 2 students
It can be seen from the
example 1.9.1.1.1 that,
the following arrangements are possible
|
I position |
A |
B |
C |
|||
|
II position |
B |
C |
A |
B |
C |
A |
But for a photo session we
notice that AB = BA, BC = CB, and CA=AC.
Though there are 6
arrangements possible, we only have 3 unique combinations (AB, BC, CA).
Example 1.2: Photo
session for group of 3 students
It can be seen from the
example 1.9.1.1.2 that, the following arrangements are possible
|
I position |
A |
B |
C |
|||
|
II position |
B |
C |
A |
B |
C |
A |
|
III position |
C |
B |
C |
C |
B |
C |
But for a photo session all
the 6 combinations are same.
Though there are 6 arrangements
possible, there is only one unique combination (ABC).
1.9.3 Example 2:
Let A B C D be 4 students in your class . A
photographer was asked to take photos such that:
1. Different combinations
of 2 students in one snap shot
2. Different combinations
of 3 students in one snap shot
How many snap shots does he
need to take?
Working:
Example 2.1: It can be
seen from the example 1.9.1.2.1 that, the following 12 arrangements are possible
|
I position |
A |
B |
C |
D |
||||||||
|
II position |
B |
C |
D |
A |
C |
D |
A |
B |
D |
A |
B |
C |
Notice that for a photo
session AB=BA, AC=CA, AD=DA, BC=CB, BD=DB and CD=DC.
Though 12 arrangements are possible , we only
have 6(=3*2) unique combinations (AB, AC, AD, BC, BD, CD).
Example 2.2: It can be
seen from the example 1.9.1.2.2 that, the following 24 arrangements
are possible
|
I position |
A |
B |
C |
D |
||||||||||||||||||||
|
II position |
B |
C |
D |
A |
C |
D |
A |
B |
D |
A |
B |
C |
||||||||||||
|
III position |
C |
D |
B |
D |
B |
C |
C |
D |
A |
D |
A |
C |
B |
D |
A |
D |
A |
B |
B |
C |
A |
C |
A |
B |
Note for a photo session
ABC=BAC=ACB=BCA=CAB=CBA
ABD=ADB=BAD=DAB=DBA=BDA
ACD=ADC=CAD=DAC=DCA=CDA
BCD=BDC=CBD=CDB=DBC=DCB
are
all same.
Though 24 combinations are
possible, there are only 4
unique combinations. (ABC, ABD, ACD, BCD)
The number of combinations
of ’n’ things taken ‘r’ things at a time is denoted by nCr
Let us analyse
our results
|
Examples |
Total Number of students(n) |
Number of students Per shot |
Number of combinations |
Notation |
|
Example
1.1 |
3 |
2 |
3 |
3C2 |
|
Example
1.2 |
3 |
3 |
1 |
3C3 |
|
Example
2.1 |
4 |
2 |
6 |
4C2 |
|
Example
2.2 |
4 |
3 |
4 |
4C3 |
Let us find the
relationship between permutations(1.9.1) and combinations(1.9.3) using
the examples 1 and 2 of Permutations and Combinations.
|
Examples |
Number of students(n) |
Number of students taken at a time(r) |
Number of Permutations nPr) (1.9.1) |
Number of Combinations(nCr) (1.9.3) |
nPr/nCr = |
|
Example
1.1 |
3 |
2 |
6= 3P2 |
3=3C2 |
2=2! |
|
Example
1.2 |
3 |
3 |
6= 3P3 |
1=3C3 |
6=3! |
|
Example
2.1 |
4 |
2 |
12= 4P2 |
6=4C2 |
2=2! |
|
Example
2.2 |
4 |
3 |
24= 4P3 |
4=4C3 |
6=3! |
We notice that nPr= nCr *
r! nCr =
nPr÷r!
Formula for number of combinations of ‘n’ things taken
‘r’ at a time:
In the example 2.1
discussed above we notice the following
(Permutations of ‘n’ things taken ‘r’ at a time)= (Selection (Combination) of ‘n’
things taken ‘r’ at a time)*(Arrangement of ‘r’ things)
nPr = nCr* rPr
1.9.3 Problem 1:
If nPr
= 336 and nCr=56 find n and r
Solution:
We know nPr÷nCr
= r!
r!= 
= 6=3*2*1=3!
r=3
Substitute r=3 in nCr= nPr÷r!
= {n! ÷ (n-r)} ÷r!
= {n*(n-1)*(n-2)*(n-3)! ÷
(n-3)! }÷3!
56 = n*(n-1)*(n-2) ÷6
I.e. 56*6 =336 =
n*(n-1)*(n-2) = 8*7*6
n=8
1.9.3 Problem 1:
A king has 8 different types of ornamental jars in his courtyard. Tell me the
number of different combinations in which theses can be arranged?
(Lilavati Shloka 116)
Solution:
Total number of jars(n) =8
|
No |
Type
of arrangement |
Nos |
|
1 |
No of
arrangements with 1 jar at a time |
8C1 |
|
2 |
No of arrangements with 2 jars at a time |
8C2 |
|
3 |
No of arrangements with 3 jars at a time |
8C3 |
|
4,5,6 |
------------------ |
|
|
7 |
No of arrangements with 7 jars at a time |
8C7 |
|
8 |
No of arrangements with 8 jars at a time |
8C8 |
Total number of
arrangements = 8C1+
8C2
+ . . . + 8C7
+ 8C8 =255 = 28-1
1.9.3 Problem 3 :
A Marriage bureau is in the business of identifying girls
for boys and boys for girls. They are having 5 girls and 4 boys in their
register looking for a match. In how many ways they can make proposals with 2
boys and 2 girls?
Solution:
1. There are 4 boys. The
number of ways in which 2 boys can be grouped are 4C2=4*3*2!/2!*2!=6
2. There are 5 girls. The
number of ways in which 2 girls can be grouped are 5C2=5*4*3!/3!*2! = 10
For every group of 2 boys
selected out of 6 groups, we can match with every group of 2 girls selected out
of 10 groups.
Total number of
proposals possible = 6*10=60
1.9.3 Problem 4 : A team has 10 players. Only
six can fit into one photo frame. Manager has to be in each of the photo
session. A photographer was asked to give an estimate for all the different
combinations of photos. A photo with frame costs Rs.22. Find out the estimate
given by photographer to the Manager
Solution:
Here n =10, r=5( manager has to be in every photo)
The number
of 5-member groups teams that can be formed from 10 members are
= 10C5
= 10!/5!*5!
= (10*9*8*7*6*5!)/(5!*5!)
= 10*9*8*7*6/120( 5! gets cancelled)
= 9*4*7 =252 photos
Total cost = 252*22= Rs.5, 544
1.9.3 Problem 5 :
Your school has one teacher for each of the subjects :
Mathematics, Social science, General Science, Moral science, English, Hindi,
Local Language, Physical Training. One of them is a headmaster.
(a) How many committees of
5 members can be formed?
(b) How many of them will
not have Headmaster in them?
Solution:
Number of teachers (n) = 8
Number of teachers in the
committee (r) =5
Number of committees
that can be formed is
= 8C5=
8!/(8-5)!*5!= 8*7*6*5!/3!*5!= 8*7*6/6 = 56
If we are to have Headmaster in the committee,
then we are left with only 7 teachers for selection. In such a case
The number of teachers (n)
= 7.
Since headmaster is already
a member of the committee, we only need to form a committee of 4 members (r) =4.
Number of committees
with head master is
= 7C4= 7!/(7-4)!*4!= 7*6*5*4!/3!*4!= 7*6*5/6 = 35
No of committees without
headmaster = total number of committees – Number of committees with head master
= 56-35 =21
1.9.3 Problem 6 :
There are 20 non collinear points on a plane. How many (a) straight lines (b)
triangles can be formed by joining these points?
Solution:
|
The
number of non collinear points (n=20) Since
straight line has 2 points (r=2), Total
number of straight lines that can be formed are = 20C2=
20!/(20-2)!*2!= 20*19*18!/18!*2! =
20*19/2 = 190 Since
triangles are formed with 3
points(r=3), Total
number of triangles that can be formed are = 20C3=
20!/(20-3)!*3!= 20*19*18*17!/17!*3! =
20*19*18/6 = 1140 |
|
Solution:
1.9.3 Problem 6 :
In a hexagon how many triangles can be formed?
Solution:
The number of vertices in a
hexagon (n)=6
The number of points
required for a triangle(r) =3
Number
of triangles that can be formed in a hexagon are
= 6C3=
6!/(6-3)!*3!= 6*5*4*3!/3!*3!= 20
1.9.3 Problem 7: A country had selected a
team of 8 batsmen and 7 bowlers to play a cricket match in
Solution:
If he chooses to have 5
bowlers then he can only have 6 batsmen out of 8.
If he chooses to have 6
bowlers then he can have 5 batsmen out of 8.
For every group of bowlers the
captain chooses, he has several choices of groups of batsmen and hence total
choice available for a particular option is product of these two choices.
|
Possibilities |
Total bowlers available =7 |
Total batsmen available =8 |
No of combinations |
|
|
1 |
5 (r=5) |
6 (r=6) |
=7C5*8C6 |
21*28=588 |
|
2 |
6 (r=6) |
5 (r=5) |
=7C6*8C5 |
7*
56=392 |
The captain has a choice of 980(588+392)
choices!!!
1.9.3 Problem 8: Indian
parliament has selected 8 members to form a 5-member Social Welfare Committee.
The Health Minister and Women Welfare Ministers are among these 8 members. The
committee’s role is to give recommendations for improvement of Welfare of
Citizens. There is a rule that the committee should be headed by a Minister and
there can not be more than one minister in the same committee. Find out how
many committees can be formed as per the rule?
Solution:
Since the committee has to
be headed by a minister, one of the ministers has to be in the committee. With
one minister being a member of committee and two ministers can not be in the
same committee,
Number of members available
for selection is (n=6)(=8-2)
Since one minister is
always in the committee, we need to select only 4 members for the committee
(r=4)(=5-1)
The no of ways
committee can be formed =6C4= 15
1.9
Summary of learning
|
Properties |
Permutations |
Combinations |
|
Meaning ====> |
Arrangement
of things in an orderly manner |
Selection
of different objects |
|
Example ====> |
How
many different words can be formed from the letters of the word ‘MATHS’ |
How
many 10 member hockey team be
formed from a list of 20 players |
|
Definition ====> |
No of ways
of arranging ‘n’ things taken ‘r’ things at a time |
No of
combinations of ‘n things taken ‘r’ things at a time |
|
Formula ====> |
nPr = n(n-1)(n-2)…(n-r+1)= |
nCr = nPr /r! |
|
Relationship ===> |
nPr= nCr * r! |
|