# Combinations - Some important results

- If out of n different things, any number of items can be chosen, it can
be done in
^{n}C_{0}+^{n}C_{1}+^{n}C_{2}+... +^{n}C_{n}ways. Alternatively, any of n items may or may not be chosen. Hence number of selections = 2×2×...n times = 2^{n}

=>^{n}C_{0}+^{n}C_{1}+... +^{n}C_{n}= 2^{n}.

It can be shown that^{n}C_{0}+^{n}C_{2}+^{n}C_{4}+... =^{n}C_{1}+^{n}C_{3}+^{n}C_{4}+... = 2^{n-1}. - Out of n different things, at least one (or more) can be chosen in 2
^{n}-1 ways. - Number of combinations of n different things taken r at a time when p
particular things always occur is
^{n -p}C_{r -p}. Number of permutations of these is^{n -p}C_{r -p}.r! - Number of combinations of n different things taken r at a time when p
particular things never occur is
^{n-p}C_{r}. Number of permutations of these is^{n -p}C_{r}.r! - The number of ways in which m +n different things can be divided into two
groups containing m and n things respectively is (m +n)!/[m!n!]. The reason
is that whenever you choose a group of m out of m +n, a group of n is
automatically left behind. Number of combinations of m +n things taken m at a
time is

^{n +m}C_{m}= (m +n)!/[m! (m +n -1)!] = (m + n)!/[m! n!] - If subgroups are equal i.e. n = m, then 2m things can be divided into two groups of m each in (2m)!/(m!)² ways. If you distribute things to two persons, then this formula gives number of subdivisions. If it is possible to interchange the two groups then number of divisions is (2m)!/[(m!)².2!]
- Number of division of m +n +p things into groups of m, n, p things respectively is (m +n +p)!/[m!.n!.p!]
- If 3m things are divided into 3 equal groups, then number of divisions is (3m)!/(m!)³ and if the groups are interchangeable, the number of divisions is (3m)!/[(m!)³.3!]
- If there are p +q +r things, where p things are alike, q things are alike and r things are alike, a non-empty selection can be made in (p +1)(q +1)(r +1) -1 ways as 0, 1, 2, ..., p items of p may be chosen; 0, 1, 2, ..., q items of q may be chosen etc.
- If there are p +q +r things, where p things are alike, q things are alike and remaining r are all different, then a non-empty selection can be made in (p +1)(q +1). 2r -1 ways. (Prove it!)

## Illustrative Examples

### Example

In how many ways can final eleven be selected from 15 cricket players if

- there is no restriction
- one of them must be included
- one of them, who is in bad form, must always be excluded
- two of them being leg spinners, one and only one leg spinner must be included?

### Solution

- 11 players can be selected out of 15 in
^{15}C_{11}ways

=^{15}C_{4}= (15.14.13.12) / (1.2.3.4) = 1365 ways. - Since a particular player must be included, we have to select 10 more out
of remaining 14 players. This can be done in
^{ 14}C_{10}=^{14}C_{4}= (14.13.12.11)/(1.2.3.4) = 1001 ways. - Since a particular player must be always excluded, we have to choose 11
players out of remaining 14. This can be done in

^{14}C_{11}ways =^{14}C_{3}= (14.13.12)/(1.2.3) = 364 ways. - One leg spinner can be chosen out of 2 in² C
_{1}= 2 ways. Then we have to select 10 more players out of 13 (because second leg spinner can't be included). This can be done in

^{13}C_{10}ways =^{13}C_{3}= (13.12.11)/(1.2.3) = 286 ways.

Thus required number of combinations = 2×286 = 572

### Example

Out of 5 boys and 4 girls, a committee of 5 is to be formed so as to include no more than 2 girls. In how many ways can it be done?

### Solution

We may choose 5 boys and no girl in ^{5}C_{5}**.**^{4}C_{0}
= 1×1 = 1 way only.

We may choose 4 boys and 1 girl in ^{5}C_{4} **.**^{4}C_{1}
= ^{5}C_{1}**.**^{4}C_{1} = 5×4 = 20 ways.

We may choose 3 boys and 2 girls in ^{5}C_{3}**.**^{4}C_{2}
= 10×6 = 60 ways.

Hence required number of combinations = 1 +20 +60 = 81.

### Example

- Find the number of ways in which 18 different objects can be divided into three groups each containing 6 objects.
- Find the number of ways in which 18 different objects can be distributed equally among 3 persons.

### Solution

- If 18 different objects are to be divided into 3 groups of 6 each and the order of groups is not important, number of ways of doing so = 18!/[(6!)³.3!]
- If 18 different objects are to be distributed 6 each to 3 persons, it can be done in 18!/(6!)³ ways.

### Example

There are 15 points in a plane, no three of which are in the same straight line except 4 which are collinear. Find the number of

- straight lines
- triangles formed by joining them.

### Solution

- If no three points out of 15 points lie on a line, then the number of
lines is
^{15}C_{2}as exactly one line is drawn through two points. Since 4 out of 15 points are collinear, they from only one line instead of^{4}C_{2}lines. Hence the number of lines gets decreased by^{4}C_{2}-1. Hence the required number of lines

=^{15}C_{2}-(^{4}C_{2}-1) = 105 -6 +1 = 100 - A triangle is formed by joining 3 non-collinear points. So if the 15
points are all non-collinear,
^{15}C_{3}triangles can be formed. But here 4 points lie on a line and form no triangle instead of^{ 4}C_{3}. Thus the required number of triangles

=^{15}C_{3}-^{4}C_{3}= 455 -4 = 451

### Example

Find the number of (i) combinations (ii) permutations of four letters taken from the word EXAMINATION.

### Solution

The word examination consists of 11 letters -

(AA), (II), (NN), E, X, M, T, O.

The following combinations are possible:

(a) 2 alike, 2 alike:³C_{2} = 3 ways

(b) 2 alike, 2 different:³C_{1}×^{7}C_{2} = 63 ways

(c) all 4 different: ^{8}C_{4} = 70 ways

Hence required number of combinations = 3 +63 +70 = 136.

To find the number of permutations:

In (a), the number of permutations = 3×4!/[2!2!] = 18

In (b), the number of permutations = 63×4!/2! = 756

In (c), the number of permutations = 70×4!= 1680

Hence required number of permutations = 18 +756 +1680 = 2454.

## Exercise

- A roller coaster has 3 seats and 4 children want to ride. How many ride combinations are possible? (Make an impossible assumption that little children don't fight over who sits where!)
- A baseball team has 13 members. How many lineups of 9 players are possible? The position of each member in the lineup is not important.
- In an examination, a candidate is required to answer 6 out of 10 questions which are divided into two groups, each containing 5 questions, and he is not permitted to attempt more than 4 questions from each group. In how many ways can he make up his choice?
- A box contains two white balls, three black balls and four red balls. In how many ways can three balls be drawn from the box if at least one black ball is to be included in the draw?
- Out of 3 books on Economics, 4 books on Political Science and 5 books on Geography, how many collections can be made if each collection consists of (i) exactly one book on each subject (ii) at least one book on each subject?
- Find the number of three digit numbers (repetitions allowed) such that at least one of the digits is 9.
- A committee of 6 is chosen from 10 men and 7 women so as to contain at least 3 men and 2 women. In how many different ways can it be done if two particular women refuse to serve on the same committee?
- There are 6 boys and 3 girls in a class. A committee of 5 is to be
selected such that 3 boys and 2 girls are on the committee.

(i) In how many ways can the committee be selected?

(ii) What is the number of ways if there is at least one girl on the committee? - In how many ways can a lawn-tennis mixed doubles be made up from 7 married couples if no husband and wife play in the same set?
- In how many ways can a pack of 52 cards be divided equally among 4 players in order?
- Determine the number of ways of obtaining 4 heads and 2 tails in 6 tosses of a coin.
- From 4 mangoes, 5 oranges and 6 apples, how many selections can be made by taking at least anyone of them?
- A committee of 6 is to be formed from 6 boys and 4 girls. In how many ways can this be done if the committee contains (i) 2 girls (ii) at least two girls?
- A man has six friends. In how many ways can he invite one or more of them to a tea party?
- How many even numbers are there with three digits such that if 5 is one of the digits, then 7 is the next digit?
- Find the number of ways in which 5 white balls and 4 black balls can be arranged in a row so that no two black balls are together.
- Everybody in a room shakes hands with everybody else. The total number of handshakes is 66. How many people are there in the room?
- At a party, each person shook hands with everyone else. Mr. Lee shook hands with 3 times as many men as women. Mrs Lee shook hands with 4 times as many men as women. How many men and women were there at the party?
- (i) There are 12 points in a plane of which 5 are collinear. These points
are joined in pairs. Find the number of straight lines formed.

(ii) How many triangles can be formed by joining the vertices of a hexagon? - How many diagonals are there in a polygon with n sides?
- How many words can be formed by taking 4 letters at a time out of the letters of the word

(i) MATHEMATICS

(ii) EXAMINATION

## Answers

**1.**4

**2.**715

**3.**200

**4.**6

**5.**(i) 60 (ii) 3255

**6.**252

**7.**7800

**8.**(i) 60 (ii) 120

**9.**420

**10.**52!/(13!)

^{4}

**11.**15

**12.**209

**13.**(i) 90 (ii) 185

**14.**63

**15.**365

**16.**15

**17.**12

**18.**16 men, 5 women

**19.**(i) 57 (ii) 20

**20.**[n (n -3)]/2

**21.**(i) 2454 (ii) 2454