Permutation & Combination concepts by Gaurav Sharma  Part (3/5)

Number 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?
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! X 5! = 2880
8 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?
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
 Always to sit together
 Never to sit together
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!
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
 12C5 x 6! X 4!
 6! X 4!
 12C5 x 6!
 None of these
7 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 x 6! X 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
 10C4 x 6! X 4!
 10C6 x 6! X 4! X 2
 11C6 X 6! X 4!
 None of these
A 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 x 6! X 4! X 2
12 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
 10C7 x 6! X 2! X 3! + 10C5 x 4! X 5! X 2!
 10C5 x 6! X 3! + 10C7 x 4! X 5!
 10C7 x 6! X 2! + 10C5 x 5! X 2!
 None of these
If 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 x 4! X 5! X 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! Ways
Hence the number of ways for the first table is 10C7 x 6! X 2! X 3!
Answer = 10C7 x 6! X 2! X 3! + 10C5 x 4! X 5! X 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 = 9
Consider a 3x3 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 = 36
General formula for the number of squares for a nxn 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^3
Find the number of squares 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 = 204
Find the number of rectangles in a chess board:
Number of vertical lines = Number of horizontal lines = 9
Number of rectangles = 9C2 x 9C2 = 36 x 36 = 1296
Derangement
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!} = 44
The number of ways in which 5 letters can be placed in 10 marked envelopes, so that no letter is in the right envelope is
 45
 44
 43
 46
D(5) = 44
Seven 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?
Number of ways in which 1 get his own bag
= 7C1 6! [ 1 – 1/1! + ½! – 1/3! + … + 1/6!]
= 7C1 x 265
Number of ways in which 2 get their own bag
= 7C2 5![1 1/1! + ½! – 1/3! + ¼! – 1/5!]
= 7C2 x 44
Number of ways in which 3 get their own bag
=7C3 4! [ 11/1! + ½! – 1/3! + ¼!]
= 7C3 x 9
Required 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
 264
 265
 53
 67
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.