PERMUTATION
AND COMBINATION
Permutation: The different arrangements of a given number or things
by taking some or all at a time, are called Permutations.
a) All
permutations (or arrangements) made with the letters of a, b, c by taking two
at a time are (ab, ba, ac, ca, bc, cb)
b) All
permutations made with the letters a, b, c, taking all at a time are: (abc,
acb, bac, bca, cab, cba).
Number of Permutations: Number of all permutations of n
things, taken r at a time, is given by:
npr = n ( n – 1 ) ( n – 2
)……(n – r + 1 ) = n! / ( n – r ) !
1. Ex.6p2 =
(6 x 5) = 30
2. Ex.7p3
= (7 x 6 x 5) = 210;
Note: Number of all permutation that is n
things, we can take all at a time = n!
An Important Result:
If there are n subjects of which p1
are alike of one kind; p2 are alike of another kind; p3
are alike of third kind and so on and pr are alike of rth kind, such
that (p1 + p2 + ... pr) = n.
Then, number of permutations of these
n objects is = n!/[(p1!) (p2!) (p3!)……………. (pr!)]
Example: In how many different ways the words ‘HOUSE’ can be
arranged?
Answer: The
word HOUSE contains 5 letters.
Required number of word using formula
5p5 = 5! = (1 x 2 x 3 x 4 x 5) = 120.
Example: In how many several way the word KOLKATA can be prepared
so that as vowel always come together?
Answer:
First of all we need to know how many
vowel in this given word, here is three vowel that is O and A, A. then we count
the consonant that is four. Now we count the number of vowel as a single unit
that is vowel O A, A count as single unit and add it with consonant so we have
a four unit.
(4 consonant +three vowels as single
unit) = 5 x 3(three vowel)
5! x 3! = 1 x 2 x 3 x 4 x 5 x 1 x 2 x
3 = 720 ways we prepared the word.
Example: In how many several way the word HOUSE can be prepared so
that as vowel always come together?
Answer:
First of all we need to know how many
vowel in this given word, here is three vowel that is E ,O and U. Then we count
the consonant that is Two. Now we count the number of vowel as a single unit
that is vowel E,O and U count as single unit and add it with consonant so we
have a three unit.
(2 consonant + three vowels as single
unit) = 3 x 3(three vowel)
3! x 3! = 1 x 2 x 3 x 1 x 2 x 3 = 36
ways we prepared the word.
Example: In how many several ways the word CAME can be arranged, that
the vowels not come together?
Answer:
First of all we need to know how many
vowel in this given word, here is two vowel that is A and E. Then we count the
consonant that is Two. Now we count the number of vowel as a single unit that
is vowel A and E count as single unit and add it with consonant so we have a
three unit.
(2 consonant + two vowels as single
unit) = 3 x 2(two vowel)
Note: If we Subtract total number ways from
within vowel ways than we get the not come to-gather ways,
So, (4! – 3! x 2! ) = 12.
What is Combination?
Each of the different groups or
selections which can be formed by taking some or all of a number of objects, is
called a combination. In combination we can select only one item at time it
based on selection on choice. Suppose Ball, Marbel, etc.
Examples:
Type 1: Suppose
we want to select two out of three girls A, B, C. Then possible
selections are AB, BC, and CA.
Note: that AB and BA represent the same
selection.
Type 2: Suppose
we select all three girls Like A, B, C. Then the selection is ABC.
Note: BAC, ABC, CAB are the same choice of selection.
Type 3: All the combinations formed by a,
b, c, taking two at a time are ab, bc, ca.
Type4: The
only combinations that can be formed of three letters a, b, c taken all
at a time is abc.
Type5: Various persons of 2 out of four
persons A, B, C and D are: AB, AC, AD, BC, BD, CD.
Type6: Note
that ab and ba are two different permutations but they represent
the same combination.
Number of Combinations: The number of all combinations of n
things, taken r at a time is:
nCr = n! / r! ( n – r ) ! =
n ( n – 1 ) ( n – 2 ) …….to r factors / r!.
Note: If n = r then nCr
= 0 and nC0 = 1
Important Rule:
nCr = nC(n
– r ) = 1
Example: find
the value of 16C13
Answer:
16C( 16
– 13 ) = 16C3 = (16 x 15 x 14 x 13!)/ (3!)
= (16 x 15
x 14) / (3 x 2 x 1) = 560
Example: Find
out value of 10P3
Answer:
10C3=
10 x 9 x 8 / 3! = 10 x 9 x 8 / 3 x 2 x 1 = 120
Example: Find
the value of 50C50
Answer:
50C50
= 1. [nCn = 1]
Difference between
Permutations and Combinations and How to identify them
Sometimes, it will be clearly stated
in the problem itself whether permutation or combination is to be used. However
if it is not mentioned in the problem, we have to find out whether the question
is related to permutation or combination.
Consider a situation where we need to
find out the total number of possible samples of two objects which can be taken
from three objects P, Q, R. To understand if the question is related to
permutation or combination, we need to find out if the order is important or
not.
a) If
order is important, PQ will be different from QP, PR will be different from RP
and QR will be different from RQ
b) If
order is not important, PQ will be same as QP, PR will be same as RP and QR
will be same as RQ
Hence,
a) If
the order is important, problem will be related to permutations.
b) If
the order is not important, problem will be related to combinations.
For permutations, the problems can be
like "What is the number of permutations the can be made", "What
is the number of arrangements that can be made", "What are the
different number of ways in which something can be arranged", etc.
For combinations, the problems can be
like "What is the number of combinations the can be made", "What
is the number of selections the can be made", "What are the different
number of ways in which something can be selected", etc.
pq and qp are two different permutations, but they represent the same
combination.
Mostly problems related to word
formation, number formation etc will be related to permutations. Similarly most
problems related to selection of persons, formation of geometrical figures,
distribution of items (there are exceptions for this) etc will be related to
combinations.
Repetition:
The term repetition is very important
in permutations and combinations. Consider the same situation described above
where we need to find out the total number of possible samples of two objects
which can be taken from three objects P, Q, R.
a) If
repetition is allowed, the same object can be taken more than once to make a
sample. i.e., PP, QQ, RR can also be considered as possible samples.
b) If
repetition is not allowed, then PP, QQ, RR cannot be considered as possible
samples. Normally repetition is not allowed unless mentioned specifically.
MEMORY
BASED SOLVED EXAMPLES BASED ON VARIOUS TYPES:
Type 1 - Based on Selection
1. A boy has 3 library cards and 8 books of his interest in the
library. Of these 8, he does not want to borrow chemistry part II unless
Chemistry part I is also borrowed. In how many ways can he choose the three
books to be borrowed?
Solution:
Two possibilities are there:
(i) Chemistry part I is available in
8 books with Chemistry part II
Or
(ii) Chemistry part II is not
available in 8 books but Chemistry part I is available.
Total No. of was = 1 x 1 x 6C1
+ 7C3 = 6 + (7 x 6 x 5) / (3 x 2) = 6 + 35 = 41
2. In a group of 6 boys and 4 girls, four children are to be
selected. In how many different ways can they be selected such that at least
one boy should be there?
Solution:
In a group of 6 boys and 4 girls,
four children are to be selected such that at least one boy should be there.
Hence we have 4 options as given
below
We can select 4 boys ...(option 1)
Number of ways to this = 6C4
We can select 3 boys and 1 girl
...(option 2)
Number of ways to this = 6C3
× 4C1
We can select 2 boys and 2 girls ...
(option 3)
Number of ways to this = 6C2
× 4C2
We can select 1 boy and 3 girls ...
(option 4)
Number of ways to this = 6C1
× 4C3
Therefore total number of ways = 6C4
+ 6C3 × 4C1 + 6C2
× 4C2 + 6C1 × 4C3
= 15 + 18 + 90 + 24 = 209
3. A box contains 1010 balls out of which 33 are red and rest are
blue. In how many ways can a random sample of 66 balls be drawn from the bag so
that at the most 22 red balls are included in the sample and no sample has all
the 66 balls of the same colour?
Solution:
Six balls can be selected in the
following ways:
One red ball and 5 blue ball (Or) Two
red balls and 4 blue balls
Total number of ways = (3C1
× 7C6) + (3C2 × 7C4)
= 63 + 105 = 168
4. How many groups of 6 persons can be formed from 8 men and 7
women?
Solution:
Total no. of person = 8 + 7 = 15
No. of groups = 15C6
= 15! /{6! (15 - 6)!} = 15! / (6! 9!) = (15 x 14 x 13 x 12 x 11 x 10) × 9! /(9!
×6 x 5 x 4 x 3 x 2 x 1) = 5005
5. There is a 7-digit telephone number with all different digits.
If the digit at extreme right and extreme left are 5 and 6 respectively, find
how many such telephone number are possible?
Solution:
There is a 7 - digit telephone number
but extreme right and extreme left positions are fixed.
i.e. for first place and last we have
choice respectively i.e., 6 x x x x x 5
For 2nd place we have 8 choices (i.e.
0,1,2,3,4,7,8,9,)
similarly for next place we have 7
choices ,
for next place we have 6 choices and
so on...
∴ Required number of ways = 8C1 x 7C1 x 6C1 x 5C1 x 4C1= 8 x 7
x 6 x 5 x 4 = 6720
6. In how many ways, can 24 persons be seated around a circular
table if there are is 13 seats?
Solution:
First , we select 13 persons out of
24 persons in 24C13 ways.
Now, these 13 persons can be seated
in 12! ways around a table .
So required number of ways = 24C13
x 12! = [24! / {13!(24 - 13)!}] x 12! = [24! / {13! x 11!}] x 12! = 24! × 12! /
{13 × 12! × 11!} = 24! / (13 x 11!)
7. The number of ways in which a committee of 3 ladies and 4
gentlemen can be appointed from a group consisting of 8 ladies and 7 gentlemen,
if Mrs. X refuses to serve in a committee if Mr. Y is its member, is
Solution:
If Mrs. X is selected among the
ladies in the committee, then Mr. Y is not selected or if Mrs. X is not
selected then Mr. Y can be there in the committee...
So, required number of ways = 8C3
x 6C4 + 7C3 x 7C4
= [(8 x 7 x 6)/(3 x 2)] x [(6 x 5)/(2 x 1)] + [(7 x 6 x 5)/(3 x 2)] x [(7 x 6 x
5)/(3 x 2)] = 840 + 1225 = 2065
Type 2 – Based on Selection + Arrangement
1. There are 5 yellow, 4 green and 3 black balls in a bag. All the
12 balls are drawn one by one and arranged in a row. Find out the number of
different arrangements possible.
Solution:
Number of different arrangements
possible = 12!/(5! × 4! × 3!) = [12 ×11 ×10 ×9 ×8 ×7 ×6 ×5 ×4 ×3 ×1/(5 ×4 ×3 4
×3 ×2 3 ×2)]
= 11 ×10 ×9 ×4 ×7 = 27720
2. In how many ways can 9 different colour balls be arranged in a
row so that black, white, red and green balls are never together?
Solution:
Total number of ways in which 9
different colour balls can be arranged in a row = 9! …….(A)
Now we will find out total number of
ways in which 9 different colour balls can be arranged in a row so that black,
white, red and green balls are always together.
We have total 9 balls. Since black,
white, red and green balls are always together, group these 4 balls together
and consider as a single ball. Hence we can take total number of balls as 6.
These 6 balls can be arranged in 6! ways.
We had grouped 4 balls together.
These 4 balls can be arranged among themselves in 4! ways.
Hence, total number of ways in which
9 different colour balls be arranged in a row so that black, white, red and
green balls are always together = 6! × 4! …… (B)
From (A) and (B),
Total number of ways in which 9
different colour balls can be arranged in a row so that black, white, red and green
balls are never together = 9! – 6! X 4! = 345600
3. A mixed doubles tennis game is to be played between two teams
(each team consists of one male and one female). There are four married
couples. No team is to consist of a husband and his wife. What is the maximum
number of games that can be played?
Solution:
Married couples:
MF MF MF MF ⇒ AB, CD, EF, GH
Possible teams:
AD CB EB GB
AF CF ED GD
AH CH EH GF
Team AD can play only with CB, CF,
CH, EB, EH, GB, GF (7 teams).
Teams AD cannot play with AF, AH, ED
and GD.
The same will apply with all teams,
So, number of total matches = 12 x 7 = 84
But every match includes 2 teams, so
the actual number of matches = 84/2 = 48
4. In how many different ways can four books A, B, C and D be
arranged one above another in a vertical order such that the books A and B are
never in continuous position?
Solution:
The number of arrangement in which A
and B are not together = Total number of arrangement - Number of arrangement in
which A and B are together = 4! - 3! x 2! = 24 - 12 = 12
5. 2 Men and 1 women board a bus in which 5 seats are vacant, one
of these 5 seats is reserved for ladies. A woman may or may not sit on the seat
reserved for ladies. In how many different ways can the five seats be occupied
by these passengers?
Solution:
Case I :-
If lady sets on reserved seat, then
2 men can occupy seats from 4 vacant
seats in 4P2 = 4 x 3 = 12 ways
Case II :-
If lady does not site on reserved
seat, then 1 women can occupy a seat from seat in 4 ways, 1 man can occupy a
seat from 3 seats in 3 ways, also 1 man left can occupy a seat from remaining
two seats in 2 ways.
∴ Total ways = 4 x 3 x 2 = 24 ways
Hence, from Case I and case II, total
ways = 12 + 24 = 36 ways
Type 3 – Word Problems
1. In how many different ways can the letters of the word
‘MATHEMATICS’ be arranged so that the vowels always come together?
Solution:
In MATHEMATICS, the consonants M and
T are repeated two times each.
Also the vowel A is repeated two
times.
Since there are four vowels being
repeated, vowels can be arranged in 4!/2 = 12 ways
Now remaining 7 consonants, with M, T
being repeated, can be written in 7!/(2 * 2) = 1260 ways
Now four vowels together can take any
of the 8 places as shown below:
Total number of ways in which the
letters of the word MATHEMATICS can be arranged such that vowels always come
together = 1260 x 8 x 12 = 120960
2. In how many ways can the letters of the word 'Director' be
arranged so that the three vowels are never together?
Solution:
Total number of letters = 8
Number of vowels = 3; r occurs twice.
Total number of arrangements when
there is no restriction = 8! / 2!
When three vowels are together,
regarding them as one letter, we have only 5 + 1 = 6 letters
These six letters can be arranged in
6! / 2! Ways, since r occurs twice.
But the three vowels can be arranged
among themselves in 3! ways.
Hence number of arrangement when the
three vowels are together = 6! x 3! / 2!
∴ Required number = 8! / 2! - {6! x 3! / 2!} = 18,000
3. In how many different ways can the letters of word JUDGE be
arranged so that the vowels always come together?
Solution:
Total number of letters = 5
Number of vowels = 2.
If we consider both vowel as a one
letter then,
Required number = 4! 2! = 48.
4. How many three letter computer passwords can be formed (no
repetition allowed) with at least one symmetric letter?
Solution:
Total number of password using all
alphabets -Total
number of password using no symmetric
alphabets = (26 x 25 x 24) - (15 x 14 x 13) = 12870
5. How many different numbers can be formed from the digits 3, 4,
5, 6 and 7 when repetitions are allowed?
Solution:
Number of 1 digit numbers = 5
Number of 2 digit numbers = 52
= 25
Number of 3 digit numbers = 53
= 125
Number of 4 digit numbers = 54
= 625
Number of 5 digit numbers = 55
= 3125
∴ Total number of numbers formed with these digits
= 5 + 25 + 125 + 625 + 3125 = 3905
6. In how many ways, can the letters of the word 'ASSASSINATION' be
arranged, so that all the S are together?
Solution:
When All S are taken together, then
ASSASSINATION has 10 letters.
So, 10 letters in total can be
arranged in 10 ! ways .
[∵ All 'S' are considered as 1]
But, here are 3 'A' and 2'I' and 2
'N' .
∴ Required number of ways = 10! / (3! x 2! x 2!) = 151200
Type 4 – Miscellaneous
1. How many 3-digit numbers can be formed from the digits 2, 3, 5,
6, 7 and 9, which are divisible by 5 and none of the digits is repeated?
Solution:
Since each desired number is
divisible by 5, so we must have 5 at the unit place. So, there is 1 way of
doing it.
The tens place can now be filled by
any of the remaining 5 digits (2, 3, 6, 7, 9). So, there are 5 ways of filling
the tens place.
The hundreds place can now be filled
by any of the remaining 4 digits. So, there are 4 ways of filling it.
Therefore, required number of numbers
= (1 x 5 x 4) = 20.
3. There are 14 points in a plane, out of which 4 are collinear.
Find the number of triangles made by these points.
Solution:
The required number of triangles = nC3
- mC3
Here, n = 14, m = 4
= 14C3 - 4C3
= (14 x 13 x 12 x 11! ) / (3! x 11!)
- 4! / (3! x 1!)
= (14 x 13 x 12)/6 - 4/1
= 14 x 26 - 4 = 364 - 4 = 360
4. A question paper consists of two sections having respectively 3
and 5 questions. The following note is given on the paper. "It is not
necessary to attempt the entire question". One question from each section
is compulsory. In how many ways, a candidate can select the question?
Solution:
Here, we have two sections A and B.
Section A has 3 question and B has 5 question and one question from each
section is compulsory according to the given condition.
∴ Number of ways selecting one or more than one question from
section A = 23 - 1 = 7
Similarly, from section B = 25
- 1 = 31
According to the rule of
multiplication, the required number of ways in which a candidate can select the
question = 7 x 31 = 217
5. A five-digit number divisible by 3 is to be formed using digits
0, 1, 2, 3, 4 and 5 without repetition, the total number of ways this can be
done, is
Solution:
A five-digit number, which is
divisible by 3, is formed when sum of digits is also divisible by 3.
So, combination formed using
six-digits, which are divisible by 3 = 5 + 4 + 3 + 2 + 1 = 15 = 5 + 4 + 2 + 1 +
0 = 12
So, set of number are (5, 4, 3, 2, 1)
and (5, 4, 2, 1, 0).
Number formed by using 1st set = 5 x
4 x 3 x 2 x 1 = 120
Similarly, using 2nd set = 4 x 4 x 3
x 2 x 1 = 96
Hence, using 2nd set, underlined
place cannot be filled by 0, otherwise it will become a four-digit number.
∴ Total number = 120 + 96 = 216
6. A new flag is to be designed with six vertical stripes using
some or all of the colour yellow, green,blue and red. Then, the number of ways
this can be made such that no two adjacent stripes have the same colour is
Solution:
Any of the 4 colour can be chosen for
the first stripe. Any of the remaining 3 colours can be used for the second
stripe. The third stripe can again be coloured in 3 ways (we can repeat the
colour of the first stripe but not use the colours of the second stripe).
Similarly, There are 3 ways to colour
each of the remaining stripes.
∴ The number of ways the flag can be coloured is 4(3)5
= (12) (3)4 = 12 x 81
7. How many numbers can be formed from 1, 2, 3, 4, 5, (without
repetition), when the digit at the unit's place must be greater than that in
the ten's place?
Solution:
The digit in the unit's place should
be greater than that in the tens' place.
Hence, if digit 5 occupies the unit
place, then remaining four digits need not to follow any order, hence required
number = 4!
However, if digit 4 occupies the unit
place then 5 cannot occupy the tenth position. Hence, digit at the ten's place
and it will be filled by the digit 1, 2 or 3. This can happen in 3 ways. The
remaining 3 digit can be filled in the remaining three place in 3! ways.
Hence, in all, we have (3 x 3!)
numbers ending in 4. Similarly, if we have 3 in the unit's place and it will be
either 1 or 2. This can happen in 2 ways. Hence, we will have (2 x 3!) number
ending in 3 . Similarly, we can find that there will be 3! numbers ending in 2
and no number with 1. Hence, total number of numbers
= 4! + (3) x 3! + (2 x 3!) + 3! = 4!
+ 6 x 3! = 24 + (6 x 6) = 60
8. Everybody in a room shakes hands with everybody else. The total
number of handshakes is 66. The total number of persons in the room is?
Solution:
Let there be n persons in the room.
The total number of hand shakes is same as the number of ways of selecting 2
out of n.
nC2 = 66
⇒ n(n - 1) / 2! = 66
⇒ n2 - n - 132 = 0
⇒ (n - 12) (n + 11) = 0
∴ n = 12
