Permutation & Combination Concepts by Gaurav Sharma  Part (1/2)

Let us suppose we want to name somebody with three letters say A,B,C. so what could be the possible names?
ABC, ACB, BCA, BAC, CBA, CAB
Now that was easy to figure out as less number of letters are there. But if we have to find that how many 6 letter names can be made out of English alphabets with certain conditions that would be time consuming. Here comes the need and application of this chapter. Permutations and combinations is a very interesting chapter and gives us food for thought
Fundamental principle of Addition
If there are two jobs such that they can be performed independently in m and n ways, then either of the two jobs can be performed in (m + n) ways.
Fundamental principle of Multiplication
If there are two jobs such that one of them can be completed in m ways, and when it has been completed in any one of these m ways, second job can be completed in n ways; then the two jobs in succession can be completed in m x n ways.
Example 1 : How many words of three distinct letters of English alphabets are there?
Answer : 26 * 25 * 24Example 2 : How many numbers lying between 5000 and 6000 (both inclusive), can be formed if,
(i) Repetition of digits is not allowed.
(ii) Repetition of digits is allowed.If we are to form the numbers without repeating any digit then we can’t take 5000 and 6000 as 0 is repeating. Now if number is between 5000 and 6000, we can say that thousand’s place can take only one digit that is 5. For hundred’s place we are left with only 9 digits, for ten’s place only 8 digits and for unit’s place only 7 digits.
So the total number of numbers between 5000 and 6000 in which no digit is repeating will be 9 x 8 x 7 = 504
Now if the repetition of digits is allowed, we can include all the numbers right from 5000 up to and with 6000. So the total number of numbers will be 1001
Number of ways to arrange r thing out of n, nPr = n!/(nr)!
For example : Number of ways in which 7 students can be seated on 10 chairs in 10P7.
How many words can be formed using all letters of word GENIUS?
Here since we are using 6 letters. So 6 letters can be arranged in 6 place in 6P6 = 6! WaysHow many words can be formed using all letters of the word ORIENTAL
OA: 8!In how many ways can letters of word GENIUS be arranged so that the word must start with N?
Here since first place is fixed as N. So remaining 5 letters can be arranged in 5 places in 5! WaysHow many of the words that can be formed using all letters of the word ORIENTAL will start with N?
OA: 7!How many of the words that can be formed using all letters of the word ORIENTAL will start with N and end with L?
OA: 6!In how many of the words that can be formed using all letters of the word ORIENTAL will all vowels come together?
Now here as we want those words where all vowels come together. so put all vowels in a box and consider it as a single letter. now we have 5 letters and these 5 letters can be arranged in 5! ways and also 4 vowels in that box can also be arranged in 4! ways so answer should be 5! * 4!In how many of the words that can be formed using all letters of the word ORIENTAL all vowels do not come together?
Total words  all vowels together.
so 8!  5! * 4!In how many ways can letters of word GENIUS be arranged so that no two vowels come together?
Here XGXNXSX. So 3 vowels can be arranged in 4 places in 4p3 ways and consonants themselves can be arranged in 3! ways. Hence 4p3 * 3!In how many of the words that can be formed using all letters of the word ORIENTAL, no two vowels come together?
OA: 5p4 * 4!In how many of the words that can be formed using all letters of the word ORIENTAL vowels occupy even places?
Now 4 vowels can be arranged at 4 even places in 4! ways and same way 4 consonants in 4! ways at odd places. so answer should be 4! * 4!In how many words that can be formed using all letters of the word ORIENTAL vowels and constants come alternatively?
As we did for even, same is for odd places. so total should be 2 × 4! × 4!Now suppose you have to choose 3 letters from 5 letters then selecting A, B, C and C, B, A are different cases?
Obviously no. here comes the concept of combinations. whenever we need to select few things we use combinations and when we need to arrange we use permutations.Difference between permutation and combination :
 In a combination only selection is made where as in a permutation not only selection is made but also an arrangement in a definite order is considered.
 In a combination, the ordering of the selected objects is immaterial where as in a permutation the ordering is essential. For example A,B and B,A are same as combination but different as permutations
 Practically to find the permutations of n different items, taken r at a time, we first select r items from n items and then arrange them. So, usually the number of permutation exceed the number of combinations.
 Each combination corresponds to many permutations. For example, the six permutations ABC, ACB, BCA, BAC, CBA & CAB correspond to the same combination ABC.
In how many ways can a cricket eleven be chosen from 15 players if
i) a particular player is always chosen
ii) a particular player is never chosenOA: 14C10, 14C11
The number of permutations of n things of which p1 are alike of one kind; p2 are alike of second kind; p3 are alike of third kind … pr are alike of rth kind such that p1 + p2 … + pr = n is n!/p1!p2!...pr!
Find the number of ways in which 6 boys and 6 girls can be seated in a row so that
a) All the girls sit together and all the boys sit together
b) All the girls are never togetherOA: a) 2 * 6!6! b) 12!  7!6!
The number of ways in which the letters of the word ARRANGE be arranged so that
a) Two R’s are never together
b) Two A’s are together but not two R’s
c) Neither two A’s nor two R’s are together.Solutions:
a) [RR], A,A,N,G,E = > 6!/2!
and total = > 7!/2!2!
so required answer = 7!/2!2! – 6!/2! = 900.
b) Both A’s together  > [AA],R,R,N,G,E = 6!/2! = 360
Both A’s and both R’s together  > [AA],[RR],N,G,E
= 5! = 120
required answer = 360 – 120 = 240.
c) Neither two A’s nor two R’s together  > 900 – 240 = 660How many chords can be drawn through 21 points on a circle ?
A chord is obtained by joining any two points on a circle. Therefore total number of chords drawn through 21 points is same as number of ways of selecting 2 points out of 21 points. Hence number of chords can be drawn in 21C2 = 210 ways.
There are 10 points in a plane, no three of which are in the same straight line, except 4 point which are colinear. Find the
a) Number of straight lines that can be formed
b) Number of triangles that can be formed using theseSolutions:
a) Number of straight lines that can be formed if all 10 are non collinear = 10C2 = 45
But 4 of them are collinear. So number of straight lines that can be formed using 4 points = 4C2 = 6
Now, 4 points when joined pairwise give only one line.
So, total lines = 45 – 6 + 1 = 40
b) Number of triangles that can be formed by joining 10 points = 10C3 = 120
Number of triangles formed by joining the 4 points, taken 3 at a time = 4C3 = 4
So total number of triangles = 120 – 4 = 116N is an integer such that 10^7 ≤ N ≤ 10^8 and sum of digits of N is 3. How many such numbers are possible?
N is an 8 digit number and its left most digit can be 1, 2 or 3.
 When left most digit is 1: Other two digits can be two 1’s and 5 0’s or one 2 and six 0’s.
Number of ways possible for (Two 1s and five 0s): 7!/5!2! = 21
Number of ways possible for (one 2 and 6 0’s): 7!/6! = 7
Therefore, 21 + 7 = 28 cases possible.  When leftmost digit is 2:
One of the other digit can be 1 so one 1 and six 0’s
Number of ways possible = 7!/1!6! = 7
7 cases possible here.  When leftmost digit is 3:
All other digits have to be 0
So only 1 case possible
So total cases = 28 + 7 + 1 = 36
There are six boxes numbered 1,2,3… 6. Each box is to be filled up either with a red or a green ball in such a way that atleast one box contains a green ball and the boxes containing green balls are consecutively numbered. The total number of ways in which this can be done is:
a) 5
b) 21
c) 33
d) 60Number of ways of filling 1 green ball: 6
[(1),(2),(3),(4),(5),(6)]Number of ways of filling 2 green balls: 5
[(1,2),(2,3),(3,4),(4,5),(5,6)]Number of ways of filling 3 green balls: 4
[(1,2,3) (2,3,4) (3,4,5) (4,5,6)]Number of ways of filling 4 green balls: 3
[(1,2,3,4) (2,3,4,5) (3,4,5,6)]Number of ways of filling 5 green balls: 2
[(1,2,3,4,5) (2,3,4,5,6)]Number of ways of filling 6 green balls : 1
[(1,2,3,4,5,6)]Hence required number of ways = 6 + 5 + 4 + 3 + 2 + 1 = 21
How many words can be formed by taking 4 letters at a time out of the letters of the word MATHEMATICS?
Total Letters : 11 (MM,AA,TT,H,E,I,C,S)
 All distinct : 8C4 x 4! = 1680 ( 8C4 because we have to select 4 out of 8 distinct letters M,A,T,H,E,I,C,S and 4! For the number of ways to arrange these)
 Two distinct and Two alike : 3C1 7C2 x 4!/2! = 756 ( 3C1 to select any 1 pair from (MM,AA,TT) 7C2 to select any two letters from the remaining 7 distinct letters and 4!/2! To arrange them)
 Two alike of one kind and two alike of another kind : 3C2 x 4!/2!2! = 18
So total number of ways = 1680 + 756 + 18 = 2454.
Number of ways to select r objects out of n distinct objects in nCr
In how many ways can we select 2 balls from a bag of 5 balls ( 1 Red, 1 Green, 1 Blue, 1 Yellow, 1 Orange) ?
Answer : 5C2But, in how many ways can we select 2 balls from a bag of 5 red balls ?
since all balls are red in color so answer should be 1Number of ways of selecting r objects out of n identical objects is 1
In how many ways can 5 letters be posted in 4 letter boxes ?
In this type of questions, one thing is repeatable and the other one is nonrepeatable.
So our answer is always : repeatable ^ non repeatable
So here the letter boxes are repeatable and the letters are not so our answer is 4^5Number of ways to arrange r things out of n when repetition is not allowed are : nPr
Number of ways to arrange r things out of n when repetition is allowed are : n^rFind the number of 3digit numbers than can be formed using the digits from 1 – 7 when repetition of digits not allowed.
Answer : Here repetition is not allowed so our answer will be of the form nPr.
N = 7 and r = 3
So our answer is 7P3Find the number of 3 digit numbers that can be formed using the digits from 1 – 7 when repetition of digits is allowed.
Answer : Here repetition is allowed so our answer will be of the form n^r
N = 7 and r = 3
So, our answer is 7^3Number of ways to arrange n items in a circle is (n1)!
A circle has no end points. If there are n items, let us say we place 1 of them at a fixed position. Now the end points are defined. So the number of ways in which (n1) items can be arranged are (n1)!
Number of ways to arrange n items in a garland is (n1)!/2
A garland has no end points. If there are n items let us say we place 1 of them at a fixed position. Now the end points are defined so the number of ways in which (n1) items can be arranged are (n1)! But this is to be divided by 2 as clockwise and anticlockwise arrangements are same. So total ways in which they can be arranged are (n1)!/2
Five boys and five girls sit alternatively around a round table. In how many ways can this be done?
Answer : Five boys can be arranged in a circle in 4! Ways
After that girls can be arranged in the 5 gaps between boys in 5! Ways
Hence total number of ways = 4! * 5! = 28808 chairs are arranged in a circular arrangement numbered 1 to 8. In how many ways can 4 boys and 4 girls be seated on them such that all girls must be seated on even numbered chair?
Answer : If chairs are numbered then the arrangement is no longer considered as circular as here end point is defined. So consider it as a linear arrangement. Thus answer should be 4! * 4!A round table conference is to be held among 20 delegates belonging from 20 different countries. In how many ways can they be seated if two particular delegates are
a) Always to sit together
b) Never to sit togethera) Let the two particular delegates who wish to sit together to be treated as one delegate. So we have 19 delegates who can be arranged on a round table in (191)! = 18! Ways.
Also the two particular candidates can be arranged among themselves in 2! = 2 ways.
So total number of arrangements = 2 x 18!
The number of arrangements of 20 delegates on a round table is (201)! = 19!b) Number of arrangements where 2 particular candidates never sit together = (total arrangements – When two are always together)
= 19! – 2 x 18!
= 17 x 18!12 persons are to be arranged around two round tables such that 1 table can accommodate 7 persons and another one can accommodate 5 persons. The number of ways in which these 12 persons can be arranged is
a) 12C5 x 6! X 4!
b) 6! X 4!
c) 12C5 x 6!
d) None of these7 persons can be selected for the final table in 12C7 ways. Now these 7 persons can be arranged in 6! Ways.
The remaining 5 persons can be arranged on the second table in 4! Ways.
Hence the total number of ways = 12C5 * 6! * 4!12 persons are to be arranged around two round tables such that 1 table can accommodate 7 persons and another one can accommodate 5 persons. The number of ways of arrangements possible if two particular persons A and B do not want to be on the same table is
a) 10C4 x 6! X 4!
b) 10C6 x 6! X 4! X 2
c) 11C6 X 6! X 4!
d) None of theseA can sit on first table and B on the second one or A on the second table and B on the first table.
If A is on the first table, then remaining six for the first table can be selected in 10C6 ways.
Now these 7 persons can be arranged in 6! Ways.
Remaining 5 persons can be arranged on the other table in 4! Ways.
Hence total number of ways are 10C6 * 6! * 4! * 212 persons are to be arranged around two round tables such that 1 table can accommodate 7 persons and other one can accommodate 5 persons. The number of arrangements possible if two particular persons A and B want to be together and consecutive is
a) 10C7 x 6! X 2! X 3! + 10C5 x 4! X 5! X 2!
b) 10C5 x 6! X 3! + 10C7 x 4! X 5!
c) 10C7 x 6! X 2! + 10C5 x 5! X 2!
d) None of theseIf A, B are on the first table then remaining 5 can be selected in 10C5 ways.
Now 7 persons including A and B can be arranged on the first table in which A and B are together in 2! 5! Ways. Remaining 5 can be arranged on the second table in 4! Ways.Total number of ways is 10C5 * 4! * 5! * 2!
If A, B are on second table then the remaining three can be selected in 10C3 ways.
Now 5 persons including A and B can be arranged on the second table in which A and B are together in 2! 3! Ways.
Remaining 7 can be arranged on the first table in 6! WaysHence the number of ways for the first table is 10C7 * 6! * 2! * 3!
Answer = 10C7 * 6! * 2! * 3! + 10C5 * 4! * 5! * 2!
Number of Squares and Rectangles in a Grid
Consider a 2 x 2 grid:
Number of rows = Number of columns = 2
Number of squares = 4 squares of side (1 x 1) + 1 square of side 2x2 = 4 + 1 = 2^2 + 1^2 = 5
Number of vertical lines = Number of horizontal lines = 3
So, number of rectangles = 3C2 x 3C2 = 3 x 3 = 9Consider a 3 x 3 grid
Number of rows = Number of columns = 3
Number of squares = 9 squares of side (1x1) + 4 squares of side (2x2) + 1 square of side (3x3) = 3^2 + 2^2 + 1^2 = 14
Number of vertical lines = Number of horizontal lines = 4
So number of rectangles = 4C2 x 4C2 = 6 x 6 = 36General formula for the number of squares for a n x n grid = 1^2 + 2^2 + … + n^2
General formula for the number of rectangles for a n x n grid = (n+1)C2 x (n+1)C2 = 1^3 + 2^3 + …. + n^3Find the number of squares & rectangles in a chess board:
In a chess board, number of rows = number of columns = 8
So number of squares = 1^2 + 2^2 + … + 8^2 = 8(8+1)(16+1)/6 = 204Number of vertical lines = Number of horizontal lines = 9
Number of rectangles = 9C2 x 9C2 = 36 x 36 = 1296Derangement
If n distinct objects are arranged in a row, then the number of ways in which they can be deranged so that none of them occupies its original place is:
D(n) = n!{1 – 1/1! + 1/2! – 1/3! + 1/4!  …. + (1)^n 1/n!}If r (0 ≤ r ≤ n) objects occupy the places assigned to them i.e none of the remaining (nr) objects occupy their original place, then the number of possible ways:
D(nr) = nCr D(nr)
= nCr (nr)! [ 1  1/1! + 1/2! – 1/3! + … + (1)^(nr)/(nr)!]Number of ways in which n items can be deranged: n! { 1 – 1/1! + 1/2! – 1/3! + 1/4!  … + (1)^n 1/n!}
Number of ways in which 1 item can be deranged:
1! {1 – 1/1!} = 0 (Obviously as only 1 item cannot be deranged)Number of ways in which 2 items can be deranged: 2! { 1 – 1/1! + 1/2!} = 1
Number of ways in which 3 items can be deranged: 3! { 1 – 1/1! + 1/2! – 1/3!} = 2
Number of ways in which 4 items can be deranged: 4! { 1 1/1! + 1/2! – 1/3! + 1/4!} = 9
Number of ways in which 5 items can be deranged: 5! { 1 – 1/1! + 1/2! – 1/3! + 1/4! – 1/5!} = 44The number of ways in which 5 letters can be placed in 10 marked envelopes, so that no letter is in the right envelope is
Answer : D(5) = 44Seven people leave their bags outside a temple and picked one bag at random after returning from worship. In how many ways can at least 1 and at most 3 of them get their correct bags?
Answer : Number of ways in which 1 get his own bag
= 7C1 6! [ 1 – 1/1! + 1/2! – 1/3! + … + 1/6!]
= 7C1 x 265Number of ways in which 2 get their own bag
= 7C2 5![1 1/1! + 1/2! – 1/3! + 1/4! – 1/5!]
= 7C2 x 44Number of ways in which 3 get their own bag
= 7C3 4! [ 11/1! + 1/2! – 1/3! + 1/4!]
= 7C3 x 9Required number of ways = 7C1 x 265 + 7C2 x 44 + 7C3 x 9
Six cards and six envelopes are numbered 1,2,3,4,5,6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same number and moreover the card numbered 1 is always placed in envelope number 2. Then the number of ways it can be done is
Answer : If 2 goes in 1, then it is derangement of 4 things which can be done in 4!(11/1!+1/2!1/3!+1/4!)= 9 ways.
If 2 doesn’t go in 1 it is derangement of 5 things which can be done in 5!(11/1!+1/2!1/3!+1/4!1/5!) = 44 ways
Hence total 53 ways are there.