Permutation & Combination

Q: (a) In how many ways can 7 men and 7 women be seated around a circular table so that no two men/no two women sit next to each other ?

(b) Suppose that at a sports dinner we have 16 cricketers and 6 tennis players. In how many ways can we seat them at a long table if (i) none of the tennis players is seated next to another tennis player and (ii) all tennis players are seated together.

(c) There are 20 persons among whom two are brothers. Find the number of ways in which we can arrange them around a circle so that there is exactly one person between the two brothers.

(d) A tea party is arranged for 2m people along two sides of a long table with m chairs on each side. r men wish to sit on one particular side and s on the other. In how many ways can they be seated? (Assume that r, s ≤ m.)

(e) A family consists of a grandfather, m sons and daughters and 2n grandchildren. They are to be seated in a row for dinner. The grandchildren wish to occupy the n seats at each end and the grandfather refuses to have a grandchild on either side of him. In how many ways can the family be made to sit?

Solution: (a) First arrange the 7 men in 6! ways. Then there are 7 places in between the men which will be occupied by 7 women in 7!, ways. So total no. of ways = 6! × 7!

(b) (i) First, 16 cricketers can be seated in 16! ways. There are 17 places in between them out of which 6 have to be occupied by tennis players.

No. of ways = ¹⁷P₆

Required no. of ways = 16! × ¹⁷P₆

(ii) All tennis players can be treated as one set. So now we have a total of 17 players. Their no. of permutations = 17 !

Also 6 tennis players can be arranged in 6! ways.

No. of ways = 17 ! × 6!

(c) We can arrange 18 persons around a circle in (18 –1)! = 17! ways. Now, there are exactly 18 places where we can arrange the two brothers. Also the two brothers can be arranged in 2! ways.

Thus, the number of ways of arranging the persons subject to the given condition is (17!) (18) (2!) = 2(18!).

(d) We can arrange r persons on m chairs on a particular side in ^mP_r ways and s persons on m chairs on the other side in ^mP_s ways. We can arrange (2m –r –s ) persons on the remaining (2m –r –s ) chairs in ^2m-r-sP_2m-r-s ways.

Thus, the number of ways of arranging the persons subject to the given conditions is

2(^mP_r) (^mP_s) (^2m-r-sP_2m-r-s ).

(e) The total number of seats required at the table is 1 + m + 2n . The grand children can occupy the n seats on either side of the table in ( ²ⁿP_2n ) ways. The grandfather can occupy a seat in ^m-1P₁ ways. The remaining seats can be occupied in ^mP_m ways.

Therefore, the required numbers of ways is

= ( ²ⁿP_2n ) ( ^mP_m ) (^m-1P₁)

= (2n!) m! (m –1)

Q: There are n straight lines in a plane, no two of which are parallel and no three of which pass through the same point. How many additional lines can be generated by means of points of intersections of the given lines.

Sol. Let AB be any one of the n straight lines and let it be intersected by some other line CD at point E.

Note that line AB contains (n – 1) such points. It follows that there are n (n – 1) such points of intersection. Since each of the points of intersection occurs in two of the n lines, the number of such points is $\displaystyle \frac{1}{2}n(n-1)$

We shall now find the number of additional lines passing through these points. The number of additional lines passing through points of the type E is equal to the number of points lying outside the line AB and CD, because a new line is obtained through E only if the other point lies outside AB and CD. Since AB and CD each contain (n – 2) new points, the number of new points outside AB and CD is
$\displaystyle \frac{1}{2}n(n-1) – [(n-2) + (n-2) + 1]$

$\displaystyle = \frac{1}{2}n(n-1) – (2n-3)$

Thus, the number of lines through E is $\displaystyle \frac{1}{2}n(n-1) – (2n-3)$ .

Since there are $\displaystyle \frac{1}{2}n(n-1)$ new points, the number of new lines is $\displaystyle \frac{1}{2}n(n-1) [\frac{1}{2}n(n-1) – (2n-3)] $

But in this way each line is counted twice. Therefore, the required number of lines is

$\displaystyle = \frac{1}{2} .\frac{1}{2}n(n-1) [\frac{1}{2}n(n-1) – (2n-3)] $

$\displaystyle = \frac{1}{8}n(n-1) (n-2) (n-3) $

Q: A and B are six digits numbers total numbers of ways of forming A and B so that
(i) these numbers can be added without carrying at any stage,
(ii) n2 can be subtracted from n1 without borrowing at any stage,
is equal to

Solution: A and B can be added without carrying at any stage if xi + yi ≤ 9
for position 6

x6 = 0, 1, 2, 3, …., 9

⇒ y6 ≤ 9 – r

⇒ y6 = 0, 1, 2, …., 9 – r

i.e. y6 can be selected in (10 – r) ways.

Hence total number of ways selecting x6 and y6 suitable

$\displaystyle \Sigma_{r=0}^{9} (10-r) = 10 + 9 + 8 + ….+1 = 55 $

Similarly total number of ways selection (x5, y5), (x4, y4), (x3, y3), (x2, y2), will be 55.

For position 1 (x1 , y1 ≠ 0)

x1 = r = 1, 2, 3, …., 9

⇒ y1 ≤ 9 – r

⇒ y1 = 1, 2, 3, ….., 9 – r i.e. y1 can be selected in 9 – r ways

hence total number of ways of selecting x1 and y1 suitable =

= 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36.

Thus total ways = 36 × (55)⁵

(ii) B can be subtracted from A without borrowing at any stage if xi ≥ yj
for position 6

Let x6 = r (r = 0, 1, 2, …., 9)

⇒ y6 ≤ r ⇒ y6 = 0, 1, 2, …., r

That mean y6 can be selected in (r + 1) ways

⇒ total number of ways selecting x6 and y6 suitable $\displaystyle = \Sigma_{r=0}^{9} (r+1) $

= 1 + 2 + …. + 10 = 55

Similarly total number of ways of selecting (x5, y5), (x4, y4), (x3, y3), (x2, y2) is 55.
For position 1.

Let x1 = r (r = 1, 2, 3, …., 9)

⇒ y1 ≤ r ⇒ y1 = 1, 2, 3, …., r that mean y1 can be selected in r ways.

⇒ total number of ways of selecting x1 , y1 suitable $\displaystyle = \Sigma_{r=1}^{9} r $ = 1 + 2 + 3 + …. + 9 = 45.

Thus total ways = 45 × (55)⁵.

Q: Let S = {a₁ , a₂ , …., a₁₂}. Find the total number of sets which contain one or more of the elements of set S (including the possibility of using all the elements of S) so that the element in a specific set must be an integral multiple of the smallest number in the set. Also generalize the result.

Sol. When the smallest number in the set is 1.

There are 11 elements other than 1. So the set with ‘ a ‘ are, alone with one other element, 2 other element,…. and with all the 11 other elements, that is we have to choose a1 and 0, 1, 2, …., 11 other elements 2, 3, …., 12.

This could be done in n (S₁) = ¹¹C₀ + ¹¹C₁ + ¹¹C₂ + …. + ¹¹C₁₁ = 211 ways.

If a set contain 2 as the smallest numbers, then besides 2, the set can have 4, 6, 8, 10, 12 other elements, none or one or more of them.

This could be done in n (S₂) = ⁵C₀ + ⁵C₁ + ⁵C₂ + ⁵C₃ + ⁵C₄ + ⁵C₅ = 25 ways.

Similarly if a set contain 3, 4, 5 and 6 as the smallest element

n (S₃) = 2³ , n (S₄) = 2² , n (S₅) = 2¹ , n (S₆) = 2¹

for 7, 8, 9, 10, 11 and 12, there is just one subset. This is total upto 6.

So, the total number of acceptable set according to the candidate is

2¹¹ + 2⁵ + 2³ + 2² + 2¹ + 2¹ + 6 = 2102

If there are n elements in the set 1, 2, 3, …, n then there

n multiples of 1

$\displaystyle \frac{n}{2} \; multiple \;of\; 2$

$\displaystyle \frac{n}{3} \; multiple \;of\; 3$

.
.
.
$\displaystyle \frac{n}{n} \; multiple \;of\; n$

So total number of sets is given by

$\displaystyle 2^{n– 1} + 2^{[n/2] – 1} + 2^{[n/3] – 1} + …. + 2^{[n/n] – 1} $

Q: If out of 3n letters there are n As, n Bs and n Cs, show that the number of ways of selecting r letters out of these is the same as the number of ways of selecting 3n –r letters out of them. If n < r < 2n + 1, show that the number of ways selecting r letters is given by (n+1)(n+2)+(r–n)(2n –r) and that the maximum number of such selections is $\displaystyle \frac{1}{4}[3(n+1)^2 + 1]$ or $\displaystyle \frac{3}{4}(n+1)^2$ according as n is even or odd.

Solution: Every time we select a total of ‘r’ letters, we are obviously left with (3n – r) letters. Thus number of ways of selecting ‘r’ letters is simply equal to the number of ways of selecting (3n – r) letters.

Let us assume that in the selection of ‘ r ‘ letters we have x1 As, x2 Bs and x3 Cs.

⇒ x1 + x2 + x3 = r … (1)

where 0 ≤ xi ≤ n and ∀ i ∈ {1 , 2 , 3}

That means we have to just find the total number of non-negative integral solutions of (1).

And this number is simply equal to the coefficient of x^r in (1 + x + x² + … + xⁿ)³

$\displaystyle x^r (1-x^{n+1})^3 (1-x)^{-3}$

$\displaystyle x^r (1-3 x^{n+1} + 3 x^{2n+2} – x^{3n+3}) (1-x)^{-3}$

Now, if 0 ≤ r ≤ n

Required coefficient $\displaystyle = x^r (1-x)^{-3} $

= ^r+2C_r = ^r+2C₂ = (r+1)(r+2)/2

If , n+1 ≤ r ≤ 2n + 1

Required coefficient $\displaystyle = x^r (1-3x^{n+1}) (1-x)^{-3} $

= ^r+2C_r -3.^r-n+1C_r-n-1

=^r+2C₂ – 3^r-n+1C₂

$\displaystyle = \frac{(r+2)(r+1)}{2} – \frac{3(r-n+1)(r-n)}{2}$

Finally if 2n+2 ≤ r ≤ 3n , required coefficient

$\displaystyle = x^r (1-3x^{n+1} + 3 x^{2n+2}) (1-x)^{-3} $

= ^r+2C₂ – 3^r-n+1C₂ + 3^r-2nC_r-2n-2

= ^r+2C₂ – 3^r-n+1C₂ + 3^r-2nC₂

If r ∈ (n , 2n +1) . Number of ways

$\displaystyle I = \frac{1}{2} (n+1)(n+2) + (r-n)(2n-r)$

$\displaystyle I = \frac{1}{2} (n+1)(n+2) + \frac{n^2}{4} -(r-\frac{3n}{2})^2 $

If n is even, I is maximum for r = 3n/2

$\displaystyle I_{max} = \frac{1}{2} (n+1)(n+2) + \frac{n^2}{4} $

$\displaystyle I_{max} = \frac{1}{4} (3(n+1)^2 + 1) $

If n is odd, minimum value of (r – 3n/2)² = 1/4

$\displaystyle I_{max} = \frac{1}{2} (n+1)(n+2) + \frac{n^2}{4} -\frac{1}{4} $

$\displaystyle I_{max} = \frac{3}{4} (n+1)^2 $

Q: Let A_i , i = 1, 2, 3, ……., 21 be the vertices of a 21-sided regular polygon inscribed in a circle with center O. Triangles are formed by joining the vertices of the 21-sided polygon. How many of them are

(i) equilateral triangles,

(ii) isosceles triangles.

Solution : (i) A triangle A_i , A_j , A_k (vertices) is equilateral if A_i , A_j, A_k are equally spaced. Out of A₁, A₂, ….., A₂₁ we have only 7 such triplets.

A1A8A15 , A2A9A16 , ……., A7A14A21. Therefore there are only 7 equilateral triangles.

(ii) Consider the diameter A₁OB where B is the point where A₁O meets the circle. If we have an isosceles triangle A₁ as its vertex then A₁B is the altitude and the base is bisected by A₁B. This means that the other two vertices, A_j and A_k, are equally spaced from B. We have 10 such pairs, so we have 10 isosceles triangle with A₁ as vertex of which is equilateral.

Because proper isosceles triangle with A1 as vertex (non-equilateral) are 9, with each vertex A_i , i = 1, 2, …., 21, we have such isosceles triangles.

So, total number of isosceles but non-equilateral triangles are 9 × 21 = 189.

But the 7 equilateral triangles are also to be considered as isosceles.

Hence total number of isosceles triangle are 196.

Q: In how many ways can the letters of the word CONCUBINE be arranged so that

(a) the C’s are never together

(b) C’s are always together.

Solution:  
(a) Ignoring the C’s we have the letter ONUBINE

No. of ways to arrange these is 7!/2!, since there are two Ns here.

Also, since the C’s don’t have to be together, we have the following arrangements:

X O X N X U X B X I X N X E X.

“C” can take the place of any of the positions marked X.
Since, the number of such X positions is 8 and there are 2 C’s, the number of ways we can select them is ⁸C₂.

Hence the total number of ways is (7!/2!) ⁸C₂.

(b) When the C’s are together, we consider them as 1 combined unit, say CC. Thus, we have CC, O, U, B, I, N, E, N.

Number of ways we can arrange them is 8!/2! since there are 2 N’s again.

Q: A colour box has 3 red colours of different shades, 2 white colours of different shades and 7 green colours of different shades. In how many ways can 3 colours be taken from the box if at least one of them is red?

Solution:    We have got 3 red colours , 2 white colours and 7 green colours.

There are 3 ways to take 3 colours from the box.

(i) 1 red   2 other

(ii) 2 red   1 other

(iii) 3 red   0 other

(i) Number of ways to choose 1red = ³C₁

Number. of ways to choose  2 others = ⁹C₂

(ii) No. of ways to choose   2red = ³C₂

No. of ways to choose  1 others = ⁹C₁

(iii) No. of ways to choose 3 red = ³C₃

No. of ways to choose  0 others = ⁹C₀

Hence the total number of ways is

³C₁ x ⁹C₂ + ³C₂ x⁹C₁ +  ³C₃ x⁹C₀

Q:    Let n₁ = x₁ x₂ x₃ and n₂ = y₁y₂ y₃ be two 3 digit numbers. How many pairs of n₁ and n₂ can be formed so that n₁ can be subtracted from n₂ without borrowing.

Solution.:  Clearly  n₁ can be  subtracted from n₂ without  borrowing  if y_i ≥ x_i  for  i = 1, 2, 3.

Let x_i = r, where  r = 0  to 9  for   i = 2 and 3

and  r = 1 to 9  for  i = 1.

Now as per our requirement y_i = r, r +1,…. , 9.

Thus we have (10 – r) choices for  y_i.

Hence total ways of choosing y_i  and  x_i

$\large = (\Sigma_{r=1}^{9}(10-r)) (\Sigma_{r=0}^{9}(10-r))^2$

= 45 .(55)²

Q: Number of even divisions of 504 is

(A) 12

(B) 24

(C) 6 ³C₂

(D) 18