The Lumenary · Grades 9–12

Combinatorics

Name: ______________________

Date: ______________________

You will learn to

Distinguish ordered from unordered selections and compute $\binom{n}{k}$ by the factorial formula and by Pascal's triangle
Prove identities such as $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ and $\sum_k \binom{n}{k} = 2^n$ by counting in two ways
Prove the binomial theorem and use it to expand powers and to count
Apply the pigeonhole principle to prove that something exists without finding it
Count unions with inclusion–exclusion, including the derangements of $n$ objects

1.
A youth council in Kigali has $9$ members. In how many ways can a working group of $4$ members be chosen? (All members of the group have the same role.)
2.
Find all whole numbers $k$ with $\binom{10}{k} = 120$ . List them separated by commas.
3.
How many five-card hands from a standard pack of $52$ cards contain at least one ace? (There are $\binom{52}{5} = 2\,598\,960$ hands in all, and $\binom{48}{5} = 1\,712\,304$ .)
4.
What is the coefficient of $x^3$ in the expansion of $(2x + 1)^5$ ?
5.
In the proof of Pascal's rule $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ , the $k$ -person committees chosen from $n$ people are split by whether they contain Amina. Why are there exactly $\binom{n-1}{k-1}$ committees containing Amina?
- A.Removing Amina leaves $k - 1$ members chosen from the other $n - 1$ people, and putting her back undoes this, so the two collections correspond one to one.
- B.Because Amina can sit in any of the $k$ places on the committee.
- C.By the factorial formula $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ .
- D.Because exactly half of all committees contain Amina.
6.
In a class of $40$ students in Accra, $22$ play football, $15$ play basketball and $8$ play both. How many students play neither sport?
7.
What is the smallest number $m$ such that any $m$ different whole numbers chosen from $1, 2, \dots, 100$ must include two whose difference is divisible by $7$ ?
8.
Here s is a finite set of objects, t a finite set of boxes and f assigns a box to each object. Which Lean statement correctly formalises the pigeonhole principle?
- A.(∀ a ∈ s, f a ∈ t) → #t < #s → ∃ x ∈ s, ∃ y ∈ s, x ≠ y ∧ f x = f y
- B.(∀ a ∈ s, f a ∈ t) → #t ≤ #s → ∃ x ∈ s, ∃ y ∈ s, x ≠ y ∧ f x = f y
- C.(∀ a ∈ s, f a ∈ t) → #t < #s → ∃ x ∈ s, ∃ y ∈ s, f x = f y
- D.#t < #s → ∃ x ∈ s, ∃ y ∈ s, x ≠ y ∧ f x = f y
9.
Write derangements(n) returning the number of ways to arrange $n$ hats so that nobody gets their own hat, using the inclusion–exclusion formula $D_n = \sum_{k=0}^{n} (-1)^k \dfrac{n!}{k!}$ . Use exact integer arithmetic (math.factorial and //). Then check: does $D_n / n!$ approach $1/e \approx 0.3679$ ?
Computational — Practice

Answer key — Combinatorics

1.
There are $9 \times 8 \times 7 \times 6 = 3024$ ordered choices, and each group of $4$ appears in $4! = 24$ orders. So there are $3024 / 24 = 126 = \binom{9}{4}$ groups.
2.
$\binom{10}{3} = \dfrac{10 \cdot 9 \cdot 8}{6} = 120$ , and by symmetry $\binom{10}{7} = \binom{10}{3} = 120$ . Row $10$ is $1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1$ , so these are the only two: $k \in \{3, 7\}$ .
3.
Count the complement. A hand with no ace is a $5$ -element subset of the $48$ non-aces: $\binom{48}{5} = 1\,712\,304$ hands. So $2\,598\,960 - 1\,712\,304 = 886\,656$ hands contain at least one ace. (Choosing “the ace first” overcounts, giving $999\,600$ .)
4.
The term with $x^3$ is $\binom{5}{3}(2x)^3 \cdot 1^2 = 10 \cdot 8x^3 = 80x^3$ . The coefficient is $80$ .
5.
Removing Amina from a committee that contains her gives a $(k-1)$ -person committee from the other $n - 1$ people; adding her to such a committee gives back a $k$ -person committee containing her. These two operations undo each other, so they are a one-to-one correspondence, and there are $\binom{n-1}{k-1}$ committees containing Amina.
6.
$|F \cup B| = 22 + 15 - 8 = 29$ students play at least one sport, so $40 - 29 = 11$ play neither. In a Venn diagram: $14$ only football, $7$ only basketball, $8$ both and $11$ outside.
7.
Use the remainders $0, 1, \dots, 6$ as $7$ boxes. Any $8$ numbers put two in the same box, and those two differ by a multiple of $7$ ; so $m = 8$ works. It is the smallest: the $7$ numbers $1, \dots, 7$ have different remainders, so no difference among them is divisible by $7$ . A complete answer to a “smallest” question needs both halves — the pigeonhole argument and an example showing one fewer is not enough.
8.
Statement (a). It needs all three ingredients: the objects go into the boxes (∀ a ∈ s, f a ∈ t), there are strictly more objects than boxes (#t < #s), and the two objects found are different (x ≠ y). Dropping any one of them gives a false statement — (b), (d) — or a trivially true one — (c).
9.
```
import math


def derangements(n):
    return sum((-1) ** k * (math.factorial(n) // math.factorial(k))
               for k in range(n + 1))
```
For $n = 4$ : $24 - 24 + 12 - 4 + 1 = 9$ . The ratio $D_n/n!$ is the partial sum $\sum_{k \le n} (-1)^k/k!$ of the series for $1/e$ , so it approaches $0.367879\ldots$ very quickly; $D_{12}/12!$ agrees with $1/e$ to about nine decimal places.