Combinatorics

Lessons

Senior 4 · Mathematics

Combinatorics

5 lessons

Lesson 4 of 5

Combinations: properties and conditions

25 min

When order does not matter

A teacher must send 3 of her 10 best students to a district mathematics quiz. If she were choosing a captain, a vice-captain and a reserve, the count would be the arrangement $A_{10}^3 = 720$ . But a team is just a group: the team {Uwase, Mugisha, Keza} is the same whoever is named first. Each team of 3 appears in the 720 ordered lists exactly $3! = 6$ times, so there are $\frac{720}{6} = 120$ possible teams. A selection in which order does not matter is a combination.

Definition

Combination: a selection of $p$ objects from $n$ different objects, without regard to order (a subset of size $p$ ). The number of combinations is

C_n^p = \binom{n}{p} = \frac{A_n^p}{p!} = \frac{n!}{p!\,(n - p)!}, \qquad 0 \le p \le n .

Notation: read $\binom{n}{p}$ as " $n$ choose $p$ "; calculators have an $n C r$ key.

Example: $\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$ .

Important

Properties of combinations. For natural numbers $0 \le p \le n$ :

$\binom{n}{0} = \binom{n}{n} = 1$ : there is one way to choose nothing, and one way to choose everything.
Symmetry: $\binom{n}{p} = \binom{n}{n - p}$ . Choosing the $p$ who go is the same as choosing the $n - p$ who stay.
Pascal's rule: $\binom{n}{p} = \binom{n - 1}{p - 1} + \binom{n - 1}{p}$ for $1 \le p \le n - 1$ . Fix one object, say Keza. The $p$ -groups that contain Keza number $\binom{n - 1}{p - 1}$ (choose the other $p - 1$ ); those without her number $\binom{n - 1}{p}$ . Every group is of one kind or the other.
Sum: $\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n$ . Both sides count all the subsets of an $n$ -set: the right side decides "in or out" for each of the $n$ objects.

Worked example 1: committees with conditions

A committee of 5 is to be chosen from 7 girls and 6 boys. In how many ways can it be chosen (a) with no condition, (b) with exactly 3 girls, (c) with at least 3 girls?

Solution

$\binom{13}{5} = 1287$ .
Choose the girls and then the boys: $\binom{7}{3}\binom{6}{2} = 35 \times 15 = 525$ .
"At least 3 girls" means 3, 4 or 5 girls, three separate cases, so add: $\binom{7}{3}\binom{6}{2} + \binom{7}{4}\binom{6}{1} + \binom{7}{5}\binom{6}{0} = 525 + 210 + 21 = 756 .$

Worked example 2: must include, must not include

Four volunteers are chosen from 9 students, among them Ishimwe and Gatete. How many choices (a) include Ishimwe, (b) leave out Ishimwe, (c) do not include both Ishimwe and Gatete?

Solution

Put Ishimwe in, then choose 3 more from the other 8: $\binom{8}{3} = 56$ .
Choose all 4 from the other 8: $\binom{8}{4} = 70$ . Check: $56 + 70 = 126 = \binom{9}{4}$ , which is Pascal's rule.
Complement: groups containing both are $\binom{7}{2} = 21$ , so $126 - 21 = 105$ .

Worked example 3: points and polygons

Eight points lie on a circle. How many (a) chords, (b) triangles can be drawn with these points as ends or vertices? (c) How many diagonals does a polygon with 10 sides have?

Solution

A chord is fixed by 2 points, in either order: $\binom{8}{2} = 28$ .
No three points on a circle are in a line, so every 3 points make a triangle: $\binom{8}{3} = 56$ .
Pairs of vertices give $\binom{10}{2} = 45$ segments; 10 of them are sides, so there are $45 - 10 = 35$ diagonals.

Warning

Arrangement or combination? Ask: "if I swap two of the chosen objects, do I get something different?" Officers, codes, rankings and words: yes, so use arrangements. Teams, committees, handfuls and hands of cards: no, so use combinations. A common error in "at least" problems is to fix the minimum and then choose the rest from everybody ( $\binom{7}{3}\binom{10}{2}$ ), which counts many committees more than once. Split into separate cases instead.

Combinations with repetition

At a fruit stall you buy 5 fruits, each a mango, an avocado or an orange. Fruits of one kind are identical, so only how many of each kind matters, and a kind may be chosen several times. Draw each fruit as a dot, and separate the kinds with 2 bars (mangoes | avocados | oranges). Every purchase becomes a row of 7 places containing 5 dots and 2 bars, and every such row is a purchase:

So the number of purchases is the number of ways to choose which 2 of the 7 places hold bars: $\binom{7}{2} = 21$ .

Important

Combinations with repetition. The number of ways to choose $p$ objects from $n$ kinds, when repetition is allowed and order does not matter, is

\binom{n + p - 1}{p} = \binom{n + p - 1}{n - 1} .

Reason: $p$ dots and $n - 1$ bars fill $n + p - 1$ places; choose the places of the dots (or of the bars).

Example: 4 bottles of soda from 6 flavours: $\binom{9}{4} = 126$ .

Tip

Write "at least" and "at most" as a list of exact cases before you calculate. When the list of cases is long, count the opposite and subtract: "at least one girl" = all committees − committees with no girls.

Anil Kumar: Number of Combinations for Girls and Boys to Form Sub-Committees. Watch how 'exactly' and 'at least' conditions are split into cases and multiplied.

✦

Practice

Try each one before opening the answers. They get harder as you go.

Evaluate $\binom{12}{4}$ and $\binom{12}{8}$ and explain why they are equal.
Fifteen people shake hands, each with every other person once. How many handshakes are there?
From 6 teachers and 4 parents, a school committee of 2 teachers and 2 parents is chosen. How many committees are possible?
From the same 10 people, how many committees of 4 contain at least one parent?
How many diagonals does a polygon with 12 sides have?
In how many ways can 8 identical exercise books be shared among 5 students (a student may get none)?
Show that $\binom{n}{2} + \binom{n}{1} = \binom{n + 1}{2}$ , and check it for $n = 6$ .

Show answersHide answers

Both equal 495, by symmetry: choosing 4 to take is choosing 8 to leave.
$\binom{15}{2} = 105$ .
$\binom{6}{2}\binom{4}{2} = 15 \times 6 = 90$ .
All committees minus those with no parent: $\binom{10}{4} - \binom{6}{4} = 210 - 15 = 195$ .
$\binom{12}{2} - 12 = 66 - 12 = 54$ .
Choose 8 from 5 kinds (the students), with repetition: $\binom{5 + 8 - 1}{8} = \binom{12}{8} = 495$ .
Pascal's rule with $n + 1$ in place of $n$ and $p = 2$ : $\binom{n + 1}{2} = \binom{n}{1} + \binom{n}{2}$ . For $n = 6$ : $15 + 6 = 21 = \binom{7}{2}$ . ✓

Quick check

Which of these counts is a combination, not an arrangement?

Key points

$\binom{n}{p} = \frac{n!}{p!\,(n - p)!} = \frac{A_n^p}{p!}$ : selections where order does not matter.
$\binom{n}{p} = \binom{n}{n - p}$ ; Pascal's rule $\binom{n}{p} = \binom{n - 1}{p - 1} + \binom{n - 1}{p}$ ; $\sum_{p=0}^{n} \binom{n}{p} = 2^n$ .
"Exactly": multiply the choices from each group; "at least": add separate cases or subtract the complement.
$p$ from $n$ kinds with repetition: $\binom{n + p - 1}{p}$ .

Sources and credits

Written by Ganzaa: the explanations, the diagram, the worked examples, the practice items and the questions.
Photo: Rwanda fruits, Antoshananarivo, Wikimedia Commons, CC BY-SA 4.0.
Video: Number of Combinations for Girls and Boys to Form Sub Committees, Anil Kumar, embedded from YouTube.
This lesson adapts CC BY-SA material and is shared under CC BY-SA 4.0.

1When order does not matter

2Combinations with repetition

When order does not matter

Combinations with repetition