Which situation is a combination?

awarding gold, silver and bronze

Combinations and the Pigeonhole Principle

In short: A combination is a selection where order does not matter: choosing $r$ from $n$ gives $(r n) = \frac{n !}{r ! ( n - r )!}$ ways. The pigeonhole principle says that if $n + 1$ items go into $n$ boxes, at least one box holds two.

Starting point: what you already know

The multiplication principle: "and" means multiply.
$n! = n (n - 1) \dots 1$ and $^{n} P_{r} = \frac{n !}{( n - r )!}$ counts arrangements where order matters (previous chapter).

From permutations to combinations

Count teams of 3 chosen from A, B, C, D.

Ordered: $^{4} P_{3} = 24$ . But each team, such as ${A, B, C}$ , appears $3! = 6$ times in different orders (ABC, ACB, BAC, ...). So the number of teams is $\frac{24}{6} = 4$ .

Useful facts

$(0 n) = (n n) = 1$ : there is one way to choose nothing, and one way to choose everything.
$(1 n) = n$ .
$(r n) = (n - r n)$ : choosing who is in is the same as choosing who is out.

Committees with restrictions

Combinations

Meaning

Order does not matter
nCr = n!/(r!(n - r)!)

Facts

nC0 = nCn = 1
nCr = nC(n - r)

Restrictions

Split into groups, multiply
At least one: total minus none
Must include: put them in first

Pigeonhole

n + 1 items in n boxes
Some box has two

Year 11The pigeonhole principle

If $n + 1$ pigeons sit in $n$ holes, at least one hole has two or more pigeons.

Example. In any group of 13 people, two share a birth month, because there are only 12 months.

General form. If $k n + 1$ items go into $n$ boxes, some box has at least $k + 1$ items. With 25 students and 12 months, some month has at least 3 birthdays, since $25 = 2 \times 12 + 1$ .

Choosing the pigeonholes. The trick is to decide what the holes are. To be sure two numbers chosen from 1 to 50 add to 51, pair them up: $(1, 50), (2, 49), \dots, (25, 26)$ . That is 25 pairs (holes), so 26 numbers guarantee a complete pair. With marks 0 to 20 (21 holes) and 85 students, $85 = 4 \times 21 + 1$ , so some mark is shared by at least 5 students.

To guarantee a repeat among all possible results, count the possible results first. 7 points on a circle make $(3 7) = 35$ different triangles, so 36 games guarantee a repeated triangle.

Year 11Probability with combinations

5 cards are dealt from a standard 52 card pack. Find the probability of exactly 3 hearts.

Favourable: $(3 13) (2 39) = 286 \times 741 = 211926$ . Total: $(5 52) = 2598960$ . $P = \frac{211 926}{2 598 960} \approx 0.0815$

Diagonals. Any two corners of a polygon with $n$ sides make a line: $(2 n)$ lines, of which $n$ are sides. A hexagon has $15 - 6 = 9$ diagonals.

Two people who cannot be together. Count all teams, then subtract those with both: from 9 people, teams of 4 without both Ann and Bo number $(4 9) - (2 7) = 126 - 21 = 105$ .

Groups with no names. Splitting 9 people into three groups of 3: $(3 9) (3 6) (3 3) = 1680$ counts named groups (group A, B, C). With no names, divide by the $3!$ orders: 280. If the groups are named rooms, do not divide.

Identical objects. To share 8 identical apples among 4 people (some may get none), line up the 8 apples and 3 dividers: choose where the dividers go, $(3 11) = 165$ .

A neat identity. Choosing $n$ people from $n$ boys and $n$ girls, split by how many boys: $(0 n)^{2} + (1 n)^{2} + \dots + (n n)^{2} = (n 2 n)$ .

Quick summary

Combinations count selections where order does not matter: $(r n) = \frac{n !}{r ! ( n - r )!}$ .
$(r n) = (n - r n)$ , and $(0 n) = (n n) = 1$ .
Split restricted choices into groups and multiply. For "at least one", use total minus none.
Pigeonhole: $n + 1$ items in $n$ boxes means some box holds two.

Quiz

13 questions with instant marking. It is free, and your scores are saved to your account so you can carry on from any device.

Turn on JavaScript to sign in and take the quiz.

Try 3 questions now

Which situation is a combination?
1. A awarding gold, silver and bronze
2. B setting a PIN
3. C choosing 3 pizza toppings
4. D seating people in a row
Show answer
C: choosing 3 pizza toppings
Swapping two toppings gives the same pizza.
Evaluate $(2 5)$ .
1. A 20
2. B 10
3. C 5
4. D 60
Show answer
B: 10
$\frac{5 \times 4}{2 \times 1}$ .
Evaluate $(8 8)$ .
1. A 0
2. B 1
3. C 8
4. D 40320
Show answer
B: 1
One way to choose everything.