# Combinations and the Pigeonhole Principle

> Choose groups where order does not matter, handle restrictions on committees, and use the pigeonhole principle.

From HSC Maths Extension 1 on WhizzNotes, free study notes for NSW students: https://whizznotes.com/mathematics-extension-1/combinations/. Updated 3 November 2026.
Year 11 and Year 12 boxes go deeper than the Year 10 text around them.

### Story time: Picking the team
Coach Rosa needs 5 players from a squad of 12 for a basketball game. She does not care who is picked first. Picking Ana then Ben is the same team as Ben then Ana.

When order does not matter, we are counting **combinations**. Lotto draws, committees and pizza toppings are all combinations.

**In short:** A combination is a selection where order does not matter: choosing $r$ from $n$ gives $\binom{n}{r} = \dfrac{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)\cdots 1$ and $^nP_r = \dfrac{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: $^4P_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 $\dfrac{24}{6} = 4$.

### Key idea: Combinations
The number of ways to choose $r$ objects from $n$ different objects, when order does not matter, is
$$^nC_r = \binom{n}{r} = \frac{n!}{r!\,(n - r)!}$$

### Worked example: Rosa's team
$$\binom{12}{5} = \frac{12!}{5!\,7!} = \frac{12 \times 11 \times 10 \times 9 \times 8}{5 \times 4 \times 3 \times 2 \times 1} = 792$$

### Exam tip: Permutation or combination?
Ask: "If I swap two of the chosen things, is it a different result?" Yes means permutation (a race, a password, seats). No means combination (a team, a hand of cards, a group).

### Calculator tip: The nCr key
$\binom{12}{4}$ is `12 nCr 4` = 495. For committees with restrictions, multiply the parts in one line, for example `5 nCr 3 × 6 nCr 2` = 150, and use `Ans` to subtract the cases you do not want.

## Useful facts

- $\dbinom{n}{0} = \dbinom{n}{n} = 1$: there is one way to choose nothing, and one way to choose everything.
- $\dbinom{n}{1} = n$.
- $\dbinom{n}{r} = \dbinom{n}{n - r}$: choosing who is **in** is the same as choosing who is **out**.

## Committees with restrictions

### Worked example: Mixed committee
A committee of 4 is chosen from 6 men and 5 women. How many committees have exactly 2 women?

Choose 2 women **and** 2 men:
$$\binom{5}{2} \times \binom{6}{2} = 10 \times 15 = 150$$

### Worked example: At least one
How many committees of 4 have **at least one** woman?

All committees minus those with no women:
$$\binom{11}{4} - \binom{6}{4} = 330 - 15 = 315$$

### Watch out: Overcounting "at least one"
Do not pick one woman first and then any 3 others. A committee with two women gets counted twice that way. Use "total minus none" instead.

### Worked example: A particular person
How many committees of 4 include Kim? Put Kim in, then choose 3 more from the other 10: $\dbinom{10}{3} = 120$.

**Mind map**

```text
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 11: The 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 $kn + 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), \ldots, (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 $\binom{7}{3} = 35$ different triangles, so 36 games guarantee a repeated triangle.

### Year 11: Probability with combinations
5 cards are dealt from a standard 52 card pack. Find the probability of exactly 3 hearts.

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

**Diagonals.** Any two corners of a polygon with $n$ sides make a line: $\binom{n}{2}$ 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 $\binom{9}{4} - \binom{7}{2} = 126 - 21 = 105$.

**Groups with no names.** Splitting 9 people into three groups of 3: $\binom{9}{3}\binom{6}{3}\binom{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, $\binom{11}{3} = 165$.

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

### Year 12: Choosing which trials succeed
In the binomial distribution, the number of ways to get $k$ successes in $n$ trials is $\dbinom{n}{k}$, because you choose which $k$ of the $n$ trials are the successes.

## Quick summary

- Combinations count selections where order does not matter: $\dbinom{n}{r} = \dfrac{n!}{r!\,(n - r)!}$.
- $\dbinom{n}{r} = \dbinom{n}{n - r}$, and $\dbinom{n}{0} = \dbinom{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

Try these questions from the chapter quiz.

1. Which situation is a combination?
   - A. awarding gold, silver and bronze
   - B. setting a PIN
   - C. choosing 3 pizza toppings
   - D. seating people in a row
   - Answer: C. choosing 3 pizza toppings. Swapping two toppings gives the same pizza.

2. Evaluate $\dbinom{5}{2}$.
   - A. 20
   - B. 10
   - C. 5
   - D. 60
   - Answer: B. 10. $\dfrac{5 \times 4}{2 \times 1}$.

3. Evaluate $\dbinom{8}{8}$.
   - A. 0
   - B. 1
   - C. 8
   - D. 40320
   - Answer: B. 1. One way to choose everything.

The whole chapter quiz is on the page, for signed-in students: https://whizznotes.com/mathematics-extension-1/combinations/#quiz