Correspondence and Pairing

In one sentence

To count a set $A$ , find a one-to-one correspondence $f : A \to B$ onto a set $B$ that is easy to count. Then $∣ A ∣ = ∣ B ∣$ .

paths ⟷ subsets of up-step numbers, ∣ A ∣ = ∣ B ∣

Pairing is its little sibling: match the objects up in pairs ( $k$ with $n - k$ , $A$ with $∁ A$ , $z$ with $\overset{z}{ˉ}$ ) so that every pair has the same sum or product, and the total is visible at a glance. Both correspondence and pairing need two checks: no repeats (injective) and no gaps (surjective).

Predict first

Walk from $(0, 0)$ to $(4, 4)$ , one cell right or up at each step, and never go above the line $y = x$ (touching is allowed). How many such paths are there?

14

16

20

Choose an answer first; then you can see the result.

Example: counting “bad” paths by reflection (the reflection principle)

Step 1 / 5

A path is a subset
A path from $(0, 0)$ to $(4, 4)$ has $8$ steps and is completely determined by “which $4$ steps go up”. So there are $(4 8) = 70$ paths in all.

$# paths = (4 8) = 70$
What is a bad path?
Reflect
Why it is one-to-one
Subtract

Stop 1 · Mappings and counting (Vol. 2)

The divider method (stars and bars) is the most common correspondence: solution ↔ positions of the dividers.

Example: how many positive integer solutions does x₁ + x₂ + x₃ + x₄ = 12 have?

Step 1 / 4

Turn numbers into balls
Write $12$ as $12$ balls in a row. A solution is a way of cutting the row into $4$ parts from left to right, each part non-empty.

$\circ \circ \circ ∣ \circ \circ ∣ \circ \circ \circ \circ ∣ \circ \circ \circ \leftrightarrow (3, 2, 4, 3)$
A cut is a choice of gaps
Check it is one-to-one
Count

Stop 2 · Families of subsets (Vol. 1)

Take the $2^{n}$ subsets of ${1, 2, \dots, n}$ and pair each subset $A$ with its complement $∁ A$ : $∣ A ∣ + ∣ ∁ A ∣ = n$ .

One problem, several solutions

Over all subsets $A$ of ${1, 2, \dots, n}$ (including the empty set), find $\sum ∣ A ∣$ .

Pair with the complement

The $2^{n}$ subsets form exactly $2^{n - 1}$ pairs ( $A \neq = ∁ A$ always holds), and the sizes in each pair add up to $n$ , so $\sum ∣ A ∣ = n \cdot 2^{n - 1}$ .

CostOne line; you only need to see that “every pair sums to n”.

Sort by size

There are $(k n)$ subsets of size $k$ , so $\sum ∣ A ∣ = \sum_{k = 0}^{n} k (k n)$ . Using $k (k n) = n (k - 1 n - 1)$ gives $n \sum_{k} (k - 1 n - 1) = n \cdot 2^{n - 1}$ .

CostNeeds an identity for binomial coefficients.

Stop 3 · Summing sequences (Vol. 5)

Gauss's trick of pairing first with last works just as well for sums of binomial coefficients: pair $k$ with $n - k$ , and use $(k n) = (n - k n)$ .

Example: find S = Σ k·C(n, k), k = 0, 1, …, n

Step 1 / 3

Write it again, backwards
Replacing $k$ by $n - k$ does not change the sum; then use $(n - k n) = (k n)$ .

$S = k = 0 \sum n (n - k) (k n)$
Add the two
The result

Stop 4 · Conjugate pairs of complex numbers (Vol. 4)

The non-real roots of a polynomial with real coefficients come in pairs, $z$ and $\overset{z}{ˉ}$ . For each pair the sum $z + \overset{z}{ˉ} = 2 Re z$ and the product $z \overset{z}{ˉ} = ∣ z ∣^{2}$ are real.

Example: pairing the four non-real roots of x⁵ = 1

Step 1 / 3

List the roots
The roots of $x^{5} = 1$ are $ω^{k}$ ( $k = 0, 1, 2, 3, 4$ ), where $ω = cos 7 2^{\circ} + i sin 7 2^{\circ}$ . Then $ω^{4} = \overset{ω}{ˉ}$ and $ω^{3} = \overline{ω^{2}}$ .

${ω, ω^{4}}, {ω^{2}, ω^{3}}$
Each pair gives a real quadratic
Compare coefficients

Practice

Exercise 1Basic

How many positive integer solutions does $x_{1} + x_{2} + x_{3} + x_{4} = 10$ have?

Exercise 2Basic

How many non-negative integer solutions does $x + y + z = 8$ have?

Exercise 3Advanced

Over all subsets $A$ of ${1, 2, 3, 4, 5, 6}$ , find the total of their sizes, $\sum ∣ A ∣$ .

Exercise 4Challenge

Among the strings of length $10$ made of $5$ “(” and $5$ “)”, how many are correctly matched (reading from left to right, the number of “)” never exceeds the number of “(” at any moment)?

In one sentence

Example: counting “bad” paths by reflection (the reflection principle)

Stop 1 · Mappings and counting (Vol. 2)

Example: how many positive integer solutions does x₁ + x₂ + x₃ + x₄ = 12 have?

Stop 2 · Families of subsets (Vol. 1)

Pair with the complement

Sort by size

Stop 3 · Summing sequences (Vol. 5)

Example: find S = Σ k·C(n, k), k = 0, 1, …, n

Stop 4 · Conjugate pairs of complex numbers (Vol. 4)

Example: pairing the four non-real roots of x⁵ = 1

Practice

Mistake Museum · Exhibits from this stop

The correspondence is not one-to-one

Reflecting in the wrong line

Stops on this line