Combinations

Definition

As we have seen earlier, if we have to pick out any two letters from the three letters a, b, c, we can do so in three different ways: ab, ac, bc. These are called combinations.

n, r are integers. If n ≥ r, for the set of n elements, a subset of r elements is called a combination.

Therefore, a combination is an unordered selection of r elements from a set of n elements.

The number of combinations of n dissimilar things taken r at a time is denoted by nCr or n or C(n, r).

Theorem

To find the number of combinations of “n” dissimilar things taken “r” at a time is

                  n!
     nCr =  ———
              r! (n–r)!

Theorem

(n–1)C(r–1) + (n–1)Cr = nCr

Corollary

If m and n are positive integers with m ≠ n, then the total m + n distinct objects can be divided into two groups of m objects and n objects in

 (m+n)!
———    ways
  m! n!

Note

(m + n + p) objects can be divided into three groups of m objects, n objects and p objects in

(m + n + p)!
—————   ways.
  m! n! p!

Examples

  1. If nCr = 126 find n Solution: Since nCr is a positive integer, we have nCr = 126 = 63 ∗ 2 = 9∗7∗2
            987       9876        
        =  ———   =  ——————  
               4                 46
                               9876
                         =  ——————
                               4321
                          = 9C4  
                     ∴n = 9
  2. If nC6 = nC8, then what is nC6 ?
    Solution:
    Since nC6 = nC8 , we have n = 6 + 8 = 14
        14C9 = 14C6
             14131211 10
        =  —————————–    = 2002
                 54321
  3. In how many ways can a committee of 5 members be formed from 8 men and 5 women such that at least 2 women should be in each committee?
    Solution:
    If there are at least 2 women in each five-member committee, then the committees are
    1. 3 men, 2 women
    2. 2 men, 3 women
    3. 1 man, 4 women
    4. No man, 5 women
    5. The number of selections related to = 8C35C2= 56∗10 = 560
    6. The number of selections related to = 8C25C3 = 28∗10 = 280
    7. The number of selections related to = 8C15C4 = 8∗5 = 40
    8. The number of selections related to = 8C05C5 = 1∗1 = 1
    9. ∴ The number of ways of selecting a five-member committee is 560 + 280 + 40 + 1 = 881.
  4. There are 3 questions in the first section, 3 questions in the second section and 2 questions in third section on an exam. In how many ways can a student who appeared for the exam choose to answer any 5 questions of the paper, choosing at least 1 question from each section?
    Solution:
    Out of 8 questions, the student can select 5 questions in following ways,
    The number of ways of selecting in 1st way
    = 3C23C12C1 = 6

    The number of ways of selecting in 2nd way
    = 3C23C22C1 = 18

    The number of ways of selecting in 3rd way
    = 3C23C12C2 = 9

    The number of ways of selecting in 4th way
    = 3C13C22C2 = 9

    The total number of ways of selection = 6 + 18 + 9 + 9 = 42.
  5. Find the number of divisors of 21600.
    Solution
    The canonical form for 21600 is 21600 = 25∗33∗52
    Among the divisors of the given number, the divisor 2 may not be there, or one 2 or two 2’s or three 2’s or four 2’s or five 2’s may be there. Therefore, five 2’s can be treated as 5 + 1 = 6 ways. Similarly, treat the divisor 3 in 4 ways, 5 in 3 ways. Hence, the required number of divisors = 6∗ 4∗3 = 72. Out of these, deleting 1 and 21600, the required number of divisors is 72 - 2 = 70.

Try these questions

  1. Find the following:
    How many ways can 5 men and 3 women be seated in a row so that two women cannot sit side by side?
    Answer:
    Since there is no restriction on men, they can sit in a row in 5! = 120 ways
    Since women cannot sit side by side they can sit in between two men or in the first place or in the last place.
    X M X M X M X M X M X
    If the sign ‘X’ shows the women place, there are 6 vacancies for women to sit,
    In these 6 vacancies 3 women can sit in 6P3 = 120 ways
    ∴ The number of ways where 5 men and 3 women can sit with the
    given condition is
    120∗120 = 14400
  2. Which of the following is the correct answer? a.    If nP6 = 30 nP4 find the value of n ?
    1. n = 10
    2. n = 2
    3. n = 8
    b.    If in a factory, for 5 jobs the members A, B, C, D, E are eligible.
    Then in how many ways all jobs can be filled?
    1. 25
    2. 20
    3. 120
    c.    In how many ways can 5 people sit at a round table?
    1. 24
    2. 120
    3. 60
    d.    In how many ways 7 people can sit at a round table?
    1. 5040
    2. 7!
    3. 720

a.   Solution:

a.  n = 10

b.   Solution:

c.   120

c.   Solution:

a.   24

d.   Solution:

c.   720