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

•  Number of ways to arrange n items in a circle is (n-1)!

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 (n-1) items can be arranged are (n-1)!

 Number of ways to arrange n items in a garland is (n-1)!/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 (n-1) items can be arranged are (n-1)! But this is to be divided by 2 as clockwise and anti-clockwise arrangements are same. So total ways in which they can be arranged are (n-1)!/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

1. Always to sit together
2. 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 (19-1)! = 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 (20-1)! = 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

1. 12C5 x 6! X 4!
2. 6! X 4!
3. 12C5 x 6!
4. 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

1. 10C4 x 6! X 4!
2. 10C6 x 6! X 4! X 2
3. 11C6 X 6! X 4!
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

1. 10C7 x 6! X 2! X 3! + 10C5 x 4! X 5! X 2!
2. 10C5 x 6! X 3! + 10C7 x 4! X 5!
3. 10C7 x 6! X 2! + 10C5 x 5! X 2!
4. 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 (n-r) objects occupy their original place, then the number of possible ways:

D(n-r) = nCr D(n-r)

= nCr (n-r)! [ 1 - 1/1! + 1/2! – 1/3! + … + (-1)^(n-r)/(n-r)!]

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

1. 45
2. 44
3. 43
4. 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! [ 1-1/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

1. 264
2. 265
3. 53
4. 67

If 2 goes in 1, then it is derangement of 4 things which can be done in 4!(1-1/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!(1-1/1!+1/2!-1/3!+1/4!-1/5!) = 44 ways

Hence total 53 ways are there.

• @gaurav_sharma sir, for the question -

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

why are we not considering the other way - i.e, firstly selecting five people for the smaller table, and adjusting the remaining in the larger table. Please clarify.

• @rink3676 - Both would give the same results right ? why confused ?

Choosing small table first
5 persons can be selected from 12 for the 5 seater table in 12C5 ways.
Also, these 5 persons can be arranged in 4! ways.
Remaining 7 persons can be arranged in the 7 seater table in 6! ways.
Total number of ways = 12C5 x 4! x 6!

Choosing large table first
7 persons can be selected from 12 for the 7 seater table in 12C7 ways
These 7 persons can be arranged in 6! ways
Remaining 5 persons can be arranged in the 5 seater table in 4! ways
Total number of ways = 12C7 x 6! x 4! = 12C5 x 4! x 6!

[Note - nCr = nC(n-r)]

• @zabeer thanks for your response. Ya agreed that both would be same, but my query is that why don't we add both the values, i.e, aren't the events of chosing smaller table first followed by the larger table, and chosing the larger table first followed by the smaller table, exhaustive events in themselves?

As both the events could be possible, and suit our requirement, so i believe that the total number of ways possible should be 2*12C5 x 4! x 6!

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.