Combinations

6.4 Combinations

When you pick a team, the order in which you name the players does not matter. A team of X and Y is the same as a team of Y and X. This is the core idea of combinations: you are selecting, not arranging.

Consider three lawn tennis players: X, Y, Z. How many different teams of 2 players can you form? The possibilities are XY, YZ, and ZX — just three. Each of these is a combination of 3 different objects taken 2 at a time. In a combination, the order of selection is irrelevant.

The same idea appears in many situations. If twelve people meet and each shakes hands with every other person, how many handshakes occur? A handshake between X and Y is the same as between Y and X — order does not matter. So the number of handshakes equals the number of combinations of 12 different things taken 2 at a time. Similarly, if seven points lie on a circle, the number of chords you can draw by joining them pairwise is the number of combinations of 7 different things taken 2 at a time.

The formula for $^nC_r$

We need a general formula for the number of combinations of $n$ different objects taken $r$ at a time. This number is denoted by $^nC_r$ (also written as $\binom{n}{r}$).

Take 4 different objects: A, B, C, D. The combinations taken 2 at a time are:

AB, AC, AD, BC, BD, CD

That is 6 combinations, so $^4C_2 = 6$. Notice that AB and BA are the same combination — we did not list BA, CA, DA, etc.

Now, each combination of 2 objects can be rearranged in $2!$ ways to give permutations. So the total number of permutations of 4 objects taken 2 at a time is:

$^4C_2 \times 2!$

But we already know that the number of permutations is $^4P_2$. Therefore:

$^4P_2 = ^4C_2 \times 2!$

Since $^4P_2 = \frac{4!}{(4-2)!}$, we get:

$^4C_2 = \frac{4!}{(4-2)! \; 2!}$

Now try with 5 objects: A, B, C, D, E. The combinations taken 3 at a time are:

ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE

That is 10 combinations, so $^5C_3 = 10$. Each combination gives $3!$ permutations. So:

$^5P_3 = ^5C_3 \times 3!$

And since $^5P_3 = \frac{5!}{(5-3)!}$, we have:

$^5C_3 = \frac{5!}{(5-3)! \; 3!}$

These examples lead to the general relationship.

Proof: Corresponding to each combination of $r$ objects, there are $r!$ permutations, because the $r$ objects in any combination can be rearranged in $r!$ ways. So the total number of permutations of $n$ different things taken $r$ at a time is $^nC_r \times r!$. But this total is also $^nP_r$. Hence $^nP_r = ^nC_r \times r!$, for $0 < r \leq n$.

From this, we get the direct formula:

Remarks and properties

1. The case $r = n$: When you select all $n$ objects, there is exactly one way to do it. The formula gives:

$^nC_n = \frac{n!}{n! \; 0!} = 1$

2. The case $r = 0$: Selecting nothing at all is the same as leaving behind all objects — there is exactly one way to do that. So we define $^nC_0 = 1$. The formula also works for $r = 0$ because $0! = 1$:

$^nC_0 = \frac{n!}{0! \; n!} = 1$

3. Symmetry property: Selecting $r$ objects out of $n$ is the same as rejecting $(n-r)$ objects. Therefore:

$^nC_r = ^nC_{n-r}$

Proof:

$^nC_{n-r} = \frac{n!}{(n-r)! \; [n-(n-r)]!} = \frac{n!}{(n-r)! \; r!} = ^nC_r$

4. Equality property: If $^nC_a = ^nC_b$, then either $a = b$ or $a + b = n$ (i.e., $a = n - b$).

This follows directly from the symmetry property. If $a \neq b$, then the only way the two combinations can be equal is if $b = n - a$.

Theorem 6: Pascal's identity

Proof:

$^nC_r + ^nC_{r-1} = \frac{n!}{r! \; (n-r)!} + \frac{n!}{(r-1)! \; (n-r+1)!}$

Take a common factor $\frac{n!}{(r-1)! \; (n-r)!}$:

$= \frac{n!}{(r-1)! \; (n-r)!} \left[ \frac{1}{r} + \frac{1}{n-r+1} \right]$

$= \frac{n!}{(r-1)! \; (n-r)!} \left[ \frac{n-r+1 + r}{r(n-r+1)} \right]$

$= \frac{n!}{(r-1)! \; (n-r)!} \times \frac{n+1}{r(n-r+1)}$

$= \frac{(n+1) \cdot n!}{r \cdot (r-1)! \; (n-r+1)(n-r)!}$

$= \frac{(n+1)!}{r! \; (n+1-r)!} = ^{n+1}C_r$

This identity is the basis of Pascal's triangle and is extremely useful for simplifying sums of combinations.

Worked examples

Example 17: If $^nC_9 = ^nC_8$, find $^{17}C_n$.

Using the equality property, since $^nC_9 = ^nC_8$, we have either $9 = 8$ (impossible) or $9 + 8 = n$. So $n = 17$.

Therefore $^{17}C_n = ^{17}C_{17} = 1$.

Example 18: A committee of 3 persons is to be formed from 2 men and 3 women. How many committees can be formed? How many of these consist of 1 man and 2 women?

Since order does not matter, we count combinations. Total number of committees = number of ways to choose 3 persons from 5:

$^5C_3 = \frac{5!}{3! \; 2!} = \frac{5 \times 4}{2} = 10$

For committees with 1 man and 2 women: choose 1 man from 2 men ($^2C_1$ ways) and 2 women from 3 women ($^3C_2$ ways). By the multiplication principle:

$^2C_1 \times ^3C_2 = 2 \times 3 = 6$

Example 19: How many ways are there to choose 4 cards from a pack of 52 playing cards? Also find the number of ways in which:

1. four cards are of the same suit
2. four cards belong to four different suits
3. four cards are face cards
4. two are red and two are black
5. all four are of the same colour Total ways to choose 4 cards from 52: $^{52}C_4 = \frac{52!}{4! \; 48!} = \frac{49 \times 50 \times 51 \times 52}{2 \times 3 \times 4} = 270725$

(i) There are 4 suits, each with 13 cards. Choose all 4 from one suit: $^{13}C_4$ ways per suit. Since there are 4 suits: …