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< r < n) at a time is nCr = n!/r!(n–r)!
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 nHr = n+r-1Cr .
Example -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 315 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 - 1C15 = 17C2 ways (n = 3, r = 5).
RESTRICTED SELECTION / ARRANGEMENT
(a) 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 Cr-k
(b) never included = n-k Cr
(b) The number of arrangements of n distinct objects taken r at a time so that k particular objects are
(a) always included = n-k Cr-k .r!
never included = n-k Cr .r!
Some Results Related to nCr:
(i) nCr = nCn-r
(c) If nCr = nCk , then r = k or n-r =k
(d) nCr + nCr-1 = n+1Cr
(e) nCr = n-1Cr-1
(v) nCr/nCr–1 = n–r+1/r
(vi) (a) If n is even , nCr is greatest for r = n/2
(b) If n is odd, nCr is greatest for r = n–1/2, 2+1/2
Example -2: (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
= nC2 = n(n–1)/2.1
Out of nC2 lines , n lines are the sides of the polygon.
Hence the number of diagonals = nC2 –n
= n(n–1/2) –n = 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.
=nC3 = n(n–1)(n–2)/3.2.1.
Let the vertices of the polygon be marked as A1, A2,A3,------An.
(i) Select two consecutive vertices A1, A2 of the polygon. For the required triangle, we can select the third vertex from the points A4,A5, -----An-1 . This can be done in n-4C1 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-4C1 = n(n-4).
(ii) For the required triangle, we have to select three consecutive vertices of the polygon. i.e. (A1 A2 A3), (A2 A3 A4), (A3 A4 A5),----------- ,(An A1 A2). 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
=> Triangles having no side common with those of the polygon
= nC3 – n(n-4) –n = n(n–1)(n–2)/6 -n(n-4) –n
= n/6 [n2 – 3n + 2 – 6n + 24 –6]