Math Core

Many AIME counting problems look messy until you find a second set of objects that is easy to count and matches the first set one-to-one. That matching is called a bijection. Once you have it, the two sets have the same size, and the hard count becomes an easy one.

What a bijection buys you

Suppose you want $|A|$ , the number of objects in some awkward set $A$ . If you can describe a rule that turns each object of $A$ into an object of a nicer set $B$ , and a rule that turns each object of $B$ back into exactly one object of $A$ , then $|A| = |B|$ .

Definition

Bijection

A bijection between sets $A$ and $B$ is a pairing in which every element of $A$ is matched with exactly one element of $B$ and every element of $B$ is matched with exactly one element of $A$ . If a bijection exists, then $|A| = |B|$ .

To prove a rule is a bijection, check two things: the rule always lands in $B$ (it is well defined), and you can undo it (every object of $B$ comes from exactly one object of $A$ ). On the AIME you rarely write this out, but you should always ask yourself, "Can I run this backwards?"

Stars and bars

The most useful bijection in contest counting turns solutions of an equation into arrangements of symbols.

A solution to $x_1 + x_2 + x_3 = 7$ in nonnegative integers, such as $(2, 0, 5)$ , can be written as a row of $7$ stars split by $2$ bars:

$\star\star \mid \; \mid \star\star\star\star\star$

The stars before the first bar give $x_1$ , the stars between the bars give $x_2$ , and the stars after the second bar give $x_3$ . Every row of $7$ stars and $2$ bars gives exactly one solution, and every solution gives exactly one row. So the number of solutions is the number of ways to choose which $2$ of the $9$ positions hold bars: $\binom{9}{2} = 36$ .

Stars and bars

The number of solutions of $x_1 + x_2 + \dots + x_k = n$ in nonnegative integers is $\dbinom{n + k - 1}{k - 1}$ .

The number of solutions in positive integers is $\dbinom{n - 1}{k - 1}$ (choose $k - 1$ of the $n - 1$ gaps between stars).

Lower bounds are handled by another bijection: a shift. If $x_1 \ge 3$ , set $y_1 = x_1 - 3 \ge 0$ . The map $x_1 \mapsto x_1 - 3$ is a bijection between the solutions you want and solutions of a new equation with a smaller total.

Spreading out: gaps between chosen numbers

Choosing numbers with no two consecutive is another classic. If $a_1 < a_2 < \dots < a_k$ are chosen from $\{1, 2, \dots, n\}$ with no two consecutive, then

$b_i = a_i - (i - 1)$

gives $b_1 < b_2 < \dots < b_k$ chosen from $\{1, 2, \dots, n - k + 1\}$ with no restriction. Subtracting $0, 1, 2, \dots$ squeezes out the forced gaps, and adding them back undoes it. So the count is $\dbinom{n - k + 1}{k}$ .

The same trick works for any required gap: if consecutive chosen numbers must differ by at least $d$ , subtract $(i - 1)(d - 1)$ from $a_i$ .

A close cousin handles non-decreasing sequences. If $1 \le a_1 \le a_2 \le \dots \le a_k \le n$ , then $c_i = a_i + (i - 1)$ is strictly increasing with values in $\{1, \dots, n + k - 1\}$ , so there are $\dbinom{n + k - 1}{k}$ such sequences.

Common mistake

Always check the range of the new objects. After $b_i = a_i - (i - 1)$ , the largest possible $b_k$ is $n - (k - 1)$ , not $n$ . Getting the endpoint wrong by one is the most common error with these shifts.

Lattice paths and reflection

A path of unit steps right ( $R$ ) and up ( $U$ ) from $(0, 0)$ to $(a, b)$ is the same thing as a word with $a$ letters $R$ and $b$ letters $U$ , so there are $\dbinom{a + b}{a}$ of them.

Harder questions forbid paths from crossing a line. The reflection principle counts the bad paths by a bijection: take a bad path, find the first point where it touches the forbidden line, and reflect the rest of the path across that line. Bad paths to $(a, b)$ match exactly with all paths to the reflected endpoint.

For paths from $(0, 0)$ to $(n, n)$ that never go above the line $y = x$ , the bad paths first touch $y = x + 1$ . Reflecting the rest of the path across that line sends the endpoint $(n, n)$ to $(n - 1, n + 1)$ . So the good paths number

$\binom{2n}{n} - \binom{2n}{n - 1} = \frac{1}{n + 1}\binom{2n}{n},$

the Catalan numbers $1, 1, 2, 5, 14, 42, 132, \dots$

A related fact, the ballot theorem: if candidate $A$ gets $p$ votes and $B$ gets $q$ votes with $p > q$ , and the votes are counted in random order, the probability that $A$ is strictly ahead the whole time is $\dfrac{p - q}{p + q}$ .

Worked example: Stars and bars with positive parts

How many ordered triples $(a, b, c)$ of positive integers satisfy $a + b + c = 12$ ?

Line up $12$ stars. There are $11$ gaps between them, and choosing $2$ gaps for bars splits the stars into three nonempty groups. The answer is $\dbinom{11}{2} = 55$ .

Worked example: No two consecutive

In how many ways can you choose $3$ numbers from $\{1, 2, \dots, 20\}$ so that no two chosen numbers are consecutive?

Write the chosen numbers as $a_1 < a_2 < a_3$ and set $b_1 = a_1$ , $b_2 = a_2 - 1$ , $b_3 = a_3 - 2$ . Because $a_{i+1} \ge a_i + 2$ , the $b_i$ are strictly increasing, and they lie in $\{1, \dots, 18\}$ . Conversely, any $3$ numbers from $\{1, \dots, 18\}$ give a valid choice by adding back $0, 1, 2$ . The answer is $\dbinom{18}{3} = 816$ .

Worked example: Non-decreasing sequences

How many sequences $0 \le a_1 \le a_2 \le a_3 \le a_4 \le 9$ of integers are there?

A non-decreasing sequence is the same as a multiset: it only records how many times each value $0, 1, \dots, 9$ appears. Let $x_j$ be the number of terms equal to $j$ . Then $x_0 + x_1 + \dots + x_9 = 4$ with each $x_j \ge 0$ , which has $\dbinom{4 + 9}{9} = \dbinom{13}{4} = 715$ solutions.

Worked example: Paths that stay below the diagonal

How many paths of unit steps right and up go from $(0, 0)$ to $(6, 6)$ and never pass above the line $y = x$ ?

All paths: $\dbinom{12}{6} = 924$ . A bad path touches $y = x + 1$ ; reflecting its remainder after the first touch gives a path to $(5, 7)$ , and every path to $(5, 7)$ arises this way. There are $\dbinom{12}{5} = 792$ of those. So the answer is $924 - 792 = 132$ , the sixth Catalan number.

Tip

When a problem says "find the number of ordered tuples with a product condition," factor into primes. Distributing the exponent of each prime among the variables is a separate stars-and-bars count, and you multiply the results.

Practice

Practice 1

Find the number of ordered quadruples $(a, b, c, d)$ of integers with $a \ge 2$ , $b \ge 0$ , $c \ge 5$ , $d \ge 1$ , and $a + b + c + d = 20$ .