## 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 ….?

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 = 17P6

Required no. of ways = 16! × 17P6

(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 mPr ways and s persons on m chairs on the other side in mPs ways. We can arrange (2m –r –s ) persons on the remaining (2m –r –s ) chairs in 2m-r-sP2m-r-s ways.

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

2(mPr) (mPs) (2m-r-sP2m-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 ( 2nP2n ) ways. The grandfather can occupy a seat in m-1P1 ways. The remaining seats can be occupied in mPm ways.

Therefore, the required numbers of ways is

= ( 2nP2n ) ( mPm ) (m-1P1)

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

## There are n straight lines in a plane, no two of which are parallel and no three of which pass through the same point….

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)$

## A and B are six digits numbers total numbers of ways of forming A and B so that ….

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

 A x1 x2 x3 x4 x5 x6 B y1 y2 y3 y4 y5 y6

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)5

(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)5.

## Let S = {a1, a2, ….., a12}. 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) …..

Q: Let S = {a1 , a2 , …., a12}. 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 (S1) = 11C0 + 11C1 + 11C2 + …. + 11C11 = 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 (S2) = 5C0 + 5C1 + 5C2 + 5C3 + 5C4 + 5C5 = 25 ways.

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

n (S3) = 23 , n (S4) = 22 , n (S5) = 21 , n (S6) = 21

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

211 + 25 + 23 + 22 + 21 + 21 + 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}$

## 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 ….

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 xr in (1 + x + x2 + … + xn)3

$\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+2Cr = r+2C2 = (r+1)(r+2)/2

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

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

= r+2Cr -3.r-n+1Cr-n-1

=r+2C2 – 3r-n+1C2

$\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+2C2 – 3r-n+1C2 + 3r-2nCr-2n-2

= r+2C2 – 3r-n+1C2 + 3r-2nC2

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)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$

## Let Ai, i = 1, 2, 3, ……., 21 be the vertices of a 21-sided regular polygon inscribed in a circle with center O ….

Q: Let Ai , 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 Ai , Aj , Ak (vertices) is equilateral if Ai , Aj, Ak are equally spaced. Out of A1, A2, ….., A21 we have only 7 such triplets.

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

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

Because proper isosceles triangle with A1 as vertex (non-equilateral) are 9, with each vertex Ai , 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.

## In how many ways can the letters of the word CONCUBINE be arranged so that …

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 8C2.

Hence the total number of ways is (7!/2!) 8C2.

(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.

## A color box has 3 red colors of different shades, 2 white colors of different shades and 7 green colors of different shades….

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 = 3C1

Number. of ways to choose  2 others = 9C2

(ii) No. of ways to choose   2red = 3C2

No. of ways to choose  1 others = 9C1

(iii) No. of ways to choose 3 red = 3C3

No. of ways to choose  0 others = 9C0

Hence the total number of ways is

3C1 x 9C2 + 3C2 x9C13C3 x9C0

## Let n1 = x1 x2 x3 and n2 = y1y2 y3 be two 3 digit numbers. How many pairs of n1 and n2 can be formed so that n1 can be subtracted from n2 without borrowing…

Q:    Let n1 = x1 x2 x3 and n2 = y1y2 y3 be two 3 digit numbers. How many pairs of n1 and n2 can be formed so that n1 can be subtracted from n2 without borrowing.

Solution.:  Clearly  n1 can be  subtracted from n2 without  borrowing  if yi ≥ xi  for  i = 1, 2, 3.

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

and  r = 1 to 9  for  i = 1.

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

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

Hence total ways of choosing yi  and  xi

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

= 45 .(55)2

## Number of even divisions of 504 is

Q: Number of even divisions of 504 is

(A) 12

(B) 24

(C) 6 3C2

(D) 18