Introduction to Combinations

A combination is a selection of a number of objects from a collection, where the order of selection does not matter. This is the key difference from a permutation, which is an arrangement where order is important.

  • Example: Selecting a committee of three people {A, B, C} is one combination. The arrangements ABC, ACB, BAC, BCA, CAB, and CBA are all different permutations but represent the same single combination.

1. Combinations of Distinct Objects (Without Repetition)

The number of combinations (selections) of n distinct objects taken r at a time is denoted by nCr^nC_r or (nr)\binom{n}{r}.

nCr=n!r!(n−r)!^nC_r = \frac{n!}{r!(n-r)!}

  • Relation between Permutations and Combinations: The number of permutations is the number of combinations multiplied by the number of ways to arrange the selected items (r!r!).

nPr=r!×nCr^nP_r = r! \times ^nC_r

2. Important Properties of nCr^nC_r

  • Symmetry: nCr=nCn−r^nC_r = ^nC_{n-r}
  • Boundary Conditions: nC0=1^nC_0 = 1 and nCn=1^nC_n = 1.
  • Pascal's Rule: nCr+nCr−1=n+1Cr^nC_r + ^nC_{r-1} = ^{n+1}C_r
  • Equality Condition: If nCx=nCy^nC_x = ^nC_y, then either x=yx=y or x+y=nx+y=n.

3. Total Number of Selections

  • The number of ways of selecting at least one item from n distinct items is:

nC1+nC2+...+nCn=2n−1^nC_1 + ^nC_2 + ... + ^nC_n = 2^n - 1

  • The number of ways of selecting any number (zero or more) of items from n distinct items is 2n2^n.

Example 1: Forming a Committee

Question: A committee of 3 persons is to be constituted from a group of 2 men and 3 women. In how many ways can this be done? How many of these committees would consist of 1 man and 2 women?

Solution:

  • Total Committees: There are a total of 2+3=52+3=5 people. We need to select 3. The total number of ways is 5C3=5!3!2!=5×42×1=10^5C_3 = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10.
  • Committees with 1 Man and 2 Women: We need to select 1 man from 2 men (AND) 2 women from 3 women. Using the multiplication principle:

Ways=(2C1)×(3C2)=(2)×(3!2!1!)=2×3=6\text{Ways} = (^2C_1) \times (^3C_2) = (2) \times (\frac{3!}{2!1!}) = 2 \times 3 = 6

Example 2: Using Properties of nCr^nC_r

Question: If nC9=nC8^nC_9 = ^nC_8, find nC17^nC_{17}.

Solution: Using the property that if nCx=nCy^nC_x = ^nC_y, then x=yx=y or x+y=nx+y=n. Here, since 9≠89 \ne 8, we must have 9+8=n9+8=n. So, n=17n=17. We need to find nC17^nC_{17}, which is 17C17^{17}C_{17}. The value of nCn^nC_n is 1. Therefore, 17C17=1^{17}C_{17} = 1.

Example 3: Selections with Constraints

Question: From a class of 25 students, 10 are to be chosen for an excursion party. There are 3 students who decide that either all of them will join or none of them will join. In how many ways can the party be chosen?

Solution: There are two mutually exclusive cases (use Addition Principle):

  • Case 1: All 3 students join. If these 3 students are included, we only need to select the remaining 10−3=710-3=7 students from the remaining 25−3=2225-3=22 students. Number of ways = 22C7^{22}C_7.
  • Case 2: None of the 3 students join. If these 3 students are excluded, we need to select all 10 students from the remaining 22 students. Number of ways = 22C10^{22}C_{10}. Total number of ways = 22C7+22C10^{22}C_7 + ^{22}C_{10}.

Example 4: Combination and Permutation Combined

Question: How many words, with or without meaning, each of 2 vowels and 3 consonants can be formed from the letters of the word DAUGHTER?

Solution: The word DAUGHTER has 8 distinct letters: 3 vowels (A, U, E) and 5 consonants (D, G, H, T, R).

  1. Selection (Combination): First, select 2 vowels from 3, and 3 consonants from 5. Ways = (3C2)×(5C3)=3×10=30(^3C_2) \times (^5C_3) = 3 \times 10 = 30. Each selection gives a group of 5 letters.
  2. Arrangement (Permutation): Each group of 5 letters can be arranged in 5!5! ways. 5!=1205! = 120. By the multiplication principle, the total number of words = 30×120=360030 \times 120 = 3600.