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

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

(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} $