Combinations - Some important results

  1. If out of n different things, any number of items can be chosen, it can be done in nC0 +nC1 +nC2 +... +nCn ways. Alternatively, any of n items may or may not be chosen. Hence number of selections = 2×2×...n times = 2n
    => nC0 +nC1 +... +nCn = 2n.
    It can be shown that nC0 +nC2 +nC4 +... = nC1 +nC3 +nC4 +... = 2n-1.
  2. Out of n different things, at least one (or more) can be chosen in 2n -1 ways.
  3. Number of combinations of n different things taken r at a time when p particular things always occur is n -pCr -p. Number of permutations of these is n -pCr -p.r!
  4. Number of combinations of n different things taken r at a time when p particular things never occur is n-pCr. Number of permutations of these is n -pCr.r!
  5. 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 +mCm = (m +n)!/[m! (m +n -1)!] = (m + n)!/[m! n!]
  6. 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!]
  7. Number of division of m +n +p things into groups of m, n, p things respectively is (m +n +p)!/[m!.n!.p!]
  8. 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!]
  9. 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.
  10. 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

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

Solution

  1. 11 players can be selected out of 15 in 15C11 ways
    = 15C4 = (15.14.13.12) / (1.2.3.4) = 1365 ways.
  2. Since a particular player must be included, we have to select 10 more out of remaining 14 players. This can be done in
    14
    C10 = 14C4 = (14.13.12.11)/(1.2.3.4) = 1001 ways.
  3. Since a particular player must be always excluded, we have to choose 11 players out of remaining 14. This can be done in
    14C11 ways = 14C3 = (14.13.12)/(1.2.3) = 364 ways.
  4. One leg spinner can be chosen out of 2 in² C1 = 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
    13C10 ways = 13C3 = (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 5C5.4C0 = 1×1 = 1 way only.
We may choose 4 boys and 1 girl in 5C4 .4C1 = 5C1.4C1 = 5×4 = 20 ways.
We may choose 3 boys and 2 girls in 5C3.4C2 = 10×6 = 60 ways.
Hence required number of combinations = 1 +20 +60 = 81.

Example

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

Solution

  1. 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!]
  2. 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

  1. straight lines
  2. triangles formed by joining them.

Solution

  1. If no three points out of 15 points lie on a line, then the number of lines is 15C2 as exactly one line is drawn through two points. Since 4 out of 15 points are collinear, they from only one line instead of 4C2 lines. Hence the number of lines gets decreased by 4C2 -1. Hence the required number of lines
    = 15C2 -(4C2 -1) = 105 -6 +1 = 100
  2. A triangle is formed by joining 3 non-collinear points. So if the 15 points are all non-collinear, 15C3 triangles can be formed. But here 4 points lie on a line and form no triangle instead of 4C3. Thus the required number of triangles
    = 15C3 -4C3 = 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:³C2 = 3 ways
(b) 2 alike, 2 different:³C1×7C2 = 63 ways
(c) all 4 different: 8C4 = 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

  1. 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!)
  2. 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.
  3. 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?
  4. 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?
  5. 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?
  6. Find the number of three digit numbers (repetitions allowed) such that at least one of the digits is 9.
  7. 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?
  8. 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?
  9. 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?
  10. In how many ways can a pack of 52 cards be divided equally among 4 players in order?
  11. Determine the number of ways of obtaining 4 heads and 2 tails in 6 tosses of a coin.
  12. From 4 mangoes, 5 oranges and 6 apples, how many selections can be made by taking at least anyone of them?
  13. 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?
  14. A man has six friends. In how many ways can he invite one or more of them to a tea party?
  15. How many even numbers are there with three digits such that if 5 is one of the digits, then 7 is the next digit?
  16. 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.
  17. Everybody in a room shakes hands with everybody else. The total number of handshakes is 66. How many people are there in the room?
  18. 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?
  19. (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?
  20. How many diagonals are there in a polygon with n sides?
  21. 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