5.3 Combinations
AHL 1.10
- what a combination is: a selection where order does not matter
- the formula \({}^n\mathrm{C}_r = \dbinom{n}{r} = \dfrac{n!}{r!\,(n - r)!}\) and where it comes from
- how to count selections with conditions such as “at least one” or “more boys than girls”
- how to combine selections and arrangements, and how to use counting in probability
Combinations
A combination is a selection of objects where the order does not matter. Choosing \(\{A, B, C\}\) is the same selection as choosing \(\{C, A, B\}\).
Example 1 Which of the following are combinations?
(a) Making a 3-digit number from the digits 1, 2, 3, 4, 5.
(b) Choosing 4 books out of 8 to put in a bag.
(c) Choosing 3 students from a class of 25 to form a team.
(d) Choosing a captain, a vice-captain and a goalkeeper from a squad of 16.
(b) and (c) are combinations. In (a) and (d) the order (or the role) matters, so they are permutations.
The formula
The number of combinations (selections) of \(r\) objects chosen from \(n\) different objects is written \({}^n\mathrm{C}_r\) and read “\(n\) C \(r\)” or “\(n\) choose \(r\)” (C stands for combination). Some books write \(C(n, r)\) or \({}_n\mathrm{C}_r\). It is the same number as the binomial coefficient \(\dbinom{n}{r}\) from 4.1.
To find a formula, take the 7 letters A, B, C, D, E, F, G. The number of arrangements of 3 of them is \({}^7\mathrm{P}_3 = 210\).
Each selection of 3 letters, such as \(\{A, B, C\}\), can be arranged in \(3! = 6\) ways (ABC, ACB, BAC, BCA, CAB, CBA). So every selection is counted 6 times among the arrangements:
\[ {}^7\mathrm{C}_3 \times 3! = {}^7\mathrm{P}_3 \quad\Longrightarrow\quad {}^7\mathrm{C}_3 = \frac{{}^7\mathrm{P}_3}{3!} = \frac{210}{6} = 35 . \]
Combinations of \(r\) objects from \(n\) different objects Partly in the formula booklet
\[ {}^n\mathrm{C}_r = \frac{n!}{r!(n - r)!} \]
In the booklet
Also: \({}^n\mathrm{C}_r = \dbinom{n}{r} = \dfrac{{}^n\mathrm{P}_r}{r!}\).
- \({}^n\mathrm{C}_r\): the number of combinations (selections, order does not matter) of \(r\) objects chosen from \(n\)
- \(n\): the number of different objects to choose from
- \(r\): the number of objects chosen (\(0 \le r \le n\))
- \({}^n\mathrm{P}_r\): the number of permutations (order matters) of \(r\) objects from \(n\)
The link \({}^n\mathrm{C}_r = \dfrac{{}^n\mathrm{P}_r}{r!}\) is not in the booklet.
So now you know what the binomial coefficient counts: the number of ways to choose \(r\) objects from \(n\).
Example 2 In how many ways can a hand of 5 cards be chosen from an ordinary pack of 52 cards?
The order in which the cards are dealt does not matter: \(\dbinom{52}{5} = 2\,598\,960\).
Selections with conditions
Strategy
- Split the selection into groups (for example girls and boys), choose from each group, and multiply.
- For “more … than …” or “at least …”, list the possible cases and add.
- “At least one” is often quickest as: total \(-\) none.
Example 3 A team of 4 is chosen from 6 women and 5 men.
(a) In how many ways can the team be chosen if
(i) there are no restrictions,
(ii) there must be more women than men?
(b) The team is chosen at random. Find the probability that it contains exactly one man.
(a)(i) \(\dbinom{11}{4} = 330\).
(a)(ii) More women than men means 4W 0M or 3W 1M:
\[ \binom{6}{4}\binom{5}{0} + \binom{6}{3}\binom{5}{1} = 15 + 20 \times 5 = 115 . \]
(b) Exactly one man: 3 women and 1 man, \(\dbinom{6}{3}\dbinom{5}{1} = 100\) ways.
\[ P(\text{exactly one man}) = \frac{100}{330} = \frac{10}{33} \]
Example 4 A diagonal of a polygon joins two vertices that are not next to each other. How many diagonals are there in a polygon with (a) 6 sides, (b) \(n\) sides?
Any two vertices make a line segment: \(\dbinom{n}{2}\) segments. Of these, \(n\) are sides, not diagonals.
(a) \(\dbinom{6}{2} - 6 = 15 - 6 = 9\).
(b) \(\dbinom{n}{2} - n = \dfrac{n(n - 1)}{2} - n = \dfrac{n(n - 3)}{2}\).
Example 5 A group of 3 is chosen from 10 people. Two of the people, Ana and Ben, refuse to be in the group together. How many groups are possible?
Total \(-\) (groups with both): \(\dbinom{10}{3} - \dbinom{8}{1} = 120 - 8 = 112\).
(If both are in, only 1 more person is chosen from the other 8.)
Selecting and then arranging
When you must choose some objects and then arrange them, multiply the number of selections by the number of arrangements.
Example 6 Two boys are chosen from 5 boys and three girls from 4 girls. The five chosen children then stand in a row. In how many ways can this be done?
Choose: \(\dbinom{5}{2}\dbinom{4}{3} = 10 \times 4 = 40\). Arrange the five: \(5! = 120\).
\[ 40 \times 120 = 4800 \]
Menu → Probability → Combinations, then nCr(52,5) → 2598960.
Common errors
| ✗ Wrong | ✓ Right | Why |
|---|---|---|
| Using \({}^n\mathrm{P}_r\) for a team or committee | \({}^n\mathrm{C}_r\) | The order of members does not matter. |
| Using \({}^n\mathrm{C}_r\) for president, secretary, treasurer | \({}^n\mathrm{P}_r\) | Different roles make the order matter. |
| Adding the girls’ and boys’ choices | Multiply | Choose girls and then boys. |
| “At least one woman” = \(\binom{6}{1} \times \binom{10}{3}\) | Total \(-\) no women | The first method counts many teams more than once. |
Exercises
1 In how many ways can 3 people be chosen from 10?
\(\dbinom{10}{3} = 120\).
2 In a lottery, 6 different numbers are chosen from 1 to 45. How many different selections are possible?
\(\dbinom{45}{6} = 8\,145\,060\).
3 A committee of 3 is chosen from 7 boys and 5 girls. How many committees have exactly 2 girls?
\(\dbinom{5}{2}\dbinom{7}{1} = 10 \times 7 = 70\).
4 Using the same group as Question 3, how many committees have at least one girl?
Total \(-\) all boys: \(\dbinom{12}{3} - \dbinom{7}{3} = 220 - 35 = 185\).
5 Eight points lie on a circle. How many
(a) chords,
(b) triangles can be drawn using these points as endpoints/vertices?
(a) \(\dbinom{8}{2} = 28\). \(\qquad\) (b) \(\dbinom{8}{3} = 56\).
6 Solve \(\dbinom{n}{2} = 45\).
\(\dfrac{n(n - 1)}{2} = 45 \Rightarrow n^2 - n - 90 = 0 \Rightarrow (n - 10)(n + 9) = 0\), so \(n = 10\).
7 A team of 5 is chosen from 9 players. The captain must be in the team. How many teams are possible?
The captain is in; choose 4 more from the other 8: \(\dbinom{8}{4} = 70\).
8 A group of 4 is chosen from 10 people. Two particular people refuse to be in the group together. How many groups are possible?
\(\dbinom{10}{4} - \dbinom{8}{2} = 210 - 28 = 182\).
9 Three books are chosen from 8 and placed in a row on a shelf. In how many ways can this be done? Compare with \({}^8\mathrm{P}_3\).
\(\dbinom{8}{3} \times 3! = 56 \times 6 = 336 = {}^8\mathrm{P}_3\). Choosing and then arranging is the same as a permutation.
10 Four cards are dealt from a pack of 52. Find the probability that all four are hearts.
\(\dfrac{\binom{13}{4}}{\binom{52}{4}} = \dfrac{715}{270\,725} = \dfrac{11}{4165} \approx 0.00264\).