Combinations

Combination: 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

$\large n_{C_r} = \frac{n!}{r! (n-r)!}$

Explanation:

Let the total number of selections (or groups) = x. Each group contains r objects , which can be arranged in r! ways.

Hence the number of arrangements of r objects = x × (r!).

But the number of arrangements = nPr

⇒ x × (r!) = nPr

⇒ $\large x = \frac{n_{P_r}}{r!} = n_{C_r}$

Illustration : There are two boys B1 and B2. B1 has n1 different toys and B2 has n2 different toys. Find the number of ways in which B1 and B2 can exchange their toys in such a way that after exchanging they still have same number of toys but not the same set.

Solution: Total number of toys = n1 + n2

Now let us keep all toys at one place and ask B1 to pick up any n1 toys out of these n1 + n2 toys.

He can do it in n1+ n2 Cn1 ways .

Out of these ways there is one way when he picks up those n1 toys which he was initially having.

Thus required number of ways = n1+ n2 Cn1 – 1

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 n + r − 1Cr

Explanation:

Let the n objects be a1, a2, a3 ….. an. In a particular group of r objects, let

a1 occurs x1 times,

a2 occurs x2 times

a3 occurs x3 times

…………….

…………..

an occurs xn times

such that x1 + x2 + x3 + …. + xn = r …. (1)

0 ≤ xi ≤ r ∀ i ∈ {1 , 2 , 3 , ….., n}

Now the total number of selections of r objects out of n

= number of non-negative integral solutions of equation (1)

= n + r − 1Cn − 1 = n + r − 1Cr

Illustration : 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

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

(i) always included = n-k Cr-k

(ii) 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

(i) always included = n-k Cr-k .r!

(ii) never included = n-k Cr .r!

(c) The number of combinations of n objects, of which p are identical, taken r at a time is

= n-pCr + n-pCr-1 + n-pCr-2+ …… + n-pC0 if r ≤ p and it is:

= n-pCr + n-pCr-1 + n-pCr -2+ ……+ n-pCr-p if r > p

Illustration : 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 = 12C4 = 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 = 10C2 = 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 10C4 = 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 = 8C1 = 8

For (ii) the number of ways of selection = 8C1 = 8

For (iii) the number of ways of selection = 8C2 = 28

For (iv) the number of ways of selection = 8C3 = 56

For (v) the number of ways of selection = 8C3 = 56

For (vi) the number of ways of selection = 8C4 = 70

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

Some results related to nCr

Some results related to nCr

(i) nCr = nCn-r

(ii) If nCr = nCk , then r = k or n-r = k

(iii) nCr + nCr-1 = n+1Cr

(iv) nCr = (n/r) 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 , n+1/2

Illustration : 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:

Number of triangles formed by joining the vertices of the polygon

= number of selections of 3 points from n points = nC3

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−4)(n−5)/6

Also Read :

Counting Principles , Multiplication Principle..
Permutations (Arrangement of objects )
Circular Permutations
All Possible Selections
Multinomial Theorem
Solved Problems : Permutation & combination

Next Page → 

←Back Page

Leave a Reply