Combinations

COMBINATIONS

Meaning of combination is selection of objects.

Selection of Objects without Repetition:

The number of selections (combinations or groups) that can be formed from n different objects taken r (0 $\le$r $\le$n) at a time is ${}^n{C}_r=\frac{n!}{r!\left(n-r\right)!}$

Selection of objects with repetition:

The number of combinations of n distinct objects, taken r at a time when each may occur once, twice, thrice,….. upto r times in any combination is ⁿH_r = ^n+r-1C_r .

Illustration-1: Let 15 toys be distributed among 3 children subject to the condition that any child can take any number of toys. Find the required number of ways to do this if

(i) toys are distinct. (ii) toys are identical.

Solution: (i) Toys are distinct

Here we have 3 children and we want the 15 toys to be distributed to the 3 children with repetition. In other words, it is same as selecting and arranging children 15 times out of 3 children with the condition that any child can be selected any no. of time, which can be done in 3¹⁵ ways (n = 3, r = 15).

(ii) Toys are identical

Here we only have to select children 15 times out of 3 children with the condition that any child can be selected any number of times which can be done in ^{3 + 15 - 1}C₁₅ = ¹⁷C₂ ways (n = 3, r = 5).

RESTRICTED SELECTION / ARRANGEMENT

(1) The number of ways in which r objects can be selected from n different objects if k particular objects are

(a) always included = ^n-k C_r-k

(b) never included = ^n-k C_r

(2) The number of arrangements of n distinct objects taken r at a time so that k particular objects are

(a) always included = ^n-k C_r-k .r!

(b) never included = ^n-k C_r .r!

Illustration-2: A delegation of four students is to be selected from a total of 12 students. In how many ways can the delegation be selected

(a) If all the students are equally willing.

(b) If two particular students have to be included in the delegation.

(c) If two particular students do not wish to be together in the delegation.

(d) If two particular students wish to be included together only.

(e) If two particular students refuse to be together and two other particular student wish to be together only in the delegation.

Solution: (a) Formation of delegation means selection of 4 out of 12. Hence the number of ways = ¹²C₄ = 495.

(b) If two particular students are already selected. Here we need to select only 2 out of the remaining 10. Hence the number of ways = ¹⁰C₂ = 45.

(c) The number of ways in which both are selected = 45. Hence the number of ways in which the two are not included together = 495 – 45 = 450.

(d) There are two possible cases

(i) Either both are selected. In this case, the number of ways in which the selection can be made = 45.

(ii) Or both are not selected. In this case all the four students are selected from the remaining ten students.

This can be done in ¹⁰C₄ = 210 ways.

Hence the total number of ways of selection = 45 + 210 = 255.

(e) We assume that students A and B wish to be selected together and students C and D do not wish to be together. Now there are following 6 cases.

(i) (A, B, C) selected, (D) not selected

(ii) (A, B, D) selected (C) not selected

(iii) (A, B) selected (C, D) not selected

(iv) (C) selected (A, B, D) not selected

(v) (D) selected (A, B, C) not selected

(vi) A, B, C, D not selected

For (i) the number of ways of selection = ⁸C₁ = 8

For (ii) the number of ways of selection = ⁸C₁ = 8

For (iii) the number of ways of selection = ⁸C₂ = 28

For (iv) the number of ways of selection = ⁸C₃ = 56

For (v) the number of ways of selection = ⁸C₃ = 56

For (vi) the number of ways of selection = ⁸C₄ = 70

Hence total number of ways = 8 + 8 + 28 + 56 + 56 + 70 = 226.

Some Results Related to ⁿC_r:

(i) ⁿC_r = ⁿC_n-r

(ii) If ⁿC_r = ⁿC_k , then r = k or n-r =k

(iii) ⁿC_r + ⁿC_r-1 = ⁿ⁺¹C_r

(iv) ⁿC_r = $\frac{n}{r}$.^n-1C_r-1

(v) $\frac{{}^n{C}_r}{{}^n{C}_{r-1}}=\frac{n-r+1}{r}$

(vi) (a) If n is even , ⁿC_r is greatest for r = n/2

(b) If n is odd, ⁿC_r is greatest for r = $\frac{n-1}{2}$ , $\frac{n+1}{2}$

Illustration-3: (a) How many diagonals are there in an n-sided polygon (n> 3).

(b) How many triangles can be formed by joining the vertices of an n- sided polygon. How many of these triangles have

(i) exactly one side common with that of the polygon

(ii) exactly two sides common with that of the polygon

(iii) no sides common with that of the polygon

Solution: (a) The number of lines formed by joining the n vertices of a polygon

= number of selections of 2 points from the given n points

= ⁿC₂ = $\frac{n(n-1)}{2.1}$

Out of ⁿC₂ lines , n lines are the sides of the polygon.

Hence the number of diagonals = ⁿC₂ –n

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

(b) Number of triangles formed by joining the vertices of the polygon = number of selections of 3 points from n points.

=ⁿC₃ = $\frac{n\left(n-1\right)\left(n-2\right)}{\mathrm{3.2.1}}...$..

Let the vertices of the polygon be marked as A₁, A₂,A₃,------A_n.

(i) Select two consecutive vertices A₁, A₂ of the polygon. For the required triangle, we can select the third vertex from the points A₄,A₅, -----A_n-1 . This can be done in ^n-4C₁ ways. Also two consecutive points (end points of a side of polygon) can be selected in n ways. Hence the total number of required triangles =n. ^n-4C₁ = n(n-4).

(ii) For the required triangle, we have to select three consecutive vertices of the polygon. i.e. (A₁ A₂ A₃), (A₂ A₃ A₄), (A₃ A₄ A₅),----------- ,(A_n A₁ A₂). This can be done in n ways.

(iii)Triangles having no side common + triangles having exactly one side common + triangles having exactly two sides common (with those of the polygon) = Total number of triangles formed

$\Rightarrow$ Triangles having no side common with those of the polygon

= ⁿC₃ – n(n-4) –n = $\frac{n\left(n-1\right)\left(n-2\right)}{6}$.-n(n-4)-n

= $=\frac{n}{6}\left[n^2-3n+2-6n+24-6\right].$

$=\frac{n}{6}\left[n^2-9n+20\right]=\frac{n\left(n-4\right)\left(n-5\right)}{6}$

ALL POSSIBLE SELECTIONS

Selection from Distinct Objects:

The number of selections from n different objects, taken at least one

= ⁿC₁ + ⁿC₂ + ⁿC₃ + ------ + ⁿC_n = 2ⁿ - 1.