Counting & ProbabilityDifficulty 30-90418 tagged problems

Bijections

Bijections is the habit of pairing two classes of objects one-to-one so a hard count becomes an easier count. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\text{If } f : A \to B \text{ is a bijection, then } |A| = |B|.$$

Match the objects you want to count one-to-one with objects you can already count; equal-sized sets have equal counts.

Why It Works

1
A bijection is a pairing in which every element of $A$ matches exactly one element of $B$ and vice versa.
2
No element is left unpaired and none is paired twice, so the two sets have the same number of elements.
3
So to count a hard set $A$, design a reversible rule turning each element of $A$ into a distinct element of an easy set $B$.
4
Verify the rule is reversible (you can recover the original from the image) — that confirms it is a true bijection and the counts match.

Worked Examples

Example 1

How many subsets does a set of $5$ elements have?

1
Pair each subset with a length-$5$ string of $0$s and $1$s: position $i$ is $1$ if element $i$ is in the subset, else $0$.
2
This is a bijection — every subset gives one string, and every string describes exactly one subset.
3
Length-$5$ binary strings number $2^5$ by the multiplication principle ($2$ choices per position).
4
So the subsets number $2^5 = 32$.

Answer:

$32$

Warm-up

How many subsets of $\{1, 2, \ldots, 10\}$ have an even number of elements?

1
Pair each subset $S$ with the subset $S \triangle \{1\}$ (toggle whether element $1$ is in it). This flips the parity of the size and is its own inverse — a bijection between even-sized and odd-sized subsets.
2
So exactly half of all subsets have even size.
3
Total subsets: $2^{10} = 1024$, so even-sized subsets number $\dfrac{1024}{2} = 512$.

Answer:

$512$

Contest level

How many strictly increasing sequences $1 \le a_1 < a_2 < a_3 \le 20$ of integers are there?

1
A strictly increasing sequence is determined by the SET of its values, so this counts $3$-element subsets of $\{1, \ldots, 20\}$ — the bijection is 'sort the set to get the sequence.'
2
Each $3$-subset corresponds to exactly one increasing triple and vice versa.
3
So the count is $\binom{20}{3} = \dfrac{20 \cdot 19 \cdot 18}{6} = 1140$.

Answer:

$1140$

Olympiad / Challenge

How many ways can $10$ people standing in a circle be split into $5$ pairs of adjacent neighbors (a perfect matching using only adjacent edges of the cycle)?

1
Label the seats $1, \ldots, 10$ around the circle; we pair each person with a neighbor, covering everyone with $5$ non-overlapping adjacent edges.
2
A circle of $2n$ vertices has exactly $2$ such 'all-adjacent' perfect matchings: the edges $\{1,2\},\{3,4\},\ldots$ or the shifted edges $\{2,3\},\{4,5\},\ldots,\{10,1\}$.
3
To see why, fix person $1$: they pair with either neighbor ($2$ choices), and that choice forces every subsequent pairing all the way around the cycle with no freedom left.
4
So there are exactly $2$ matchings.

Answer:

$2$

Going Deeper

The power of a bijection is transferring difficulty: to count $A$, exhibit a reversible rule $f : A \to B$ where $|B|$ is known. Classic transfers include subsets $\leftrightarrow$ binary strings, increasing sequences $\leftrightarrow$ subsets, lattice paths $\leftrightarrow$ multiset arrangements, and the 'toggle one element' involution that proves even- and odd-sized subsets are equinumerous.
Bijective proofs are prized on olympiads because they explain WHY two counts are equal rather than just verifying it algebraically. They appear in Catalan-number identities, partition theorems (Euler's odd = distinct), and any problem where a clever relabeling collapses a messy object into a familiar one.
Pitfall: a valid bijection must be both well-defined (every input maps to a legal output) and invertible (you can uniquely recover the input). The usual failure is a map that is not injective or not surjective — it pairs things up but misses some targets or hits one twice — so always exhibit the inverse explicitly to confirm the counts truly match.

Spot the Signal

Look for problems where the key step is pairing two classes of objects one-to-one so a hard count becomes an easier count.
You can describe the hard part as pairing two classes of objects one-to-one so a hard count becomes an easier count, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the counting object that calls for bijections, then rewrite the givens around it.
Name the relation that makes Bijections legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Bijections just because the surface looks familiar; verify the required condition first.
Applying Bijections because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let bijections reveal the counting structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is pairing two classes of objects one-to-one so a hard count becomes an easier count.