Introduction

Previously at the introductiory level of the AMC 8/10, just applying the formula itself is more prominent than the AMC 12 or early AIME level. However, harder problems are designed so that the method of direct counting is either impossible or significantly tedious. Therefore in this module, we will seek to explain many ways of restructuring an advanced counting problem to become solvable.

In the level of the AMC 12, a similar theme is that most hard counting problems have several representative patterns, transform the objects you are counting so they correspond to something simpler (bijection), count a large set and subtract the bad cases (inclusion-exclusion), or use symmetry to collapse the count (Burnside's Lemma), or using recurrences.

This module covers the core techniques, strategies, and the classical structures that appear, to give an understanding of advanced casework.

First, we recap some basic counting techniques.

Inclusion-Exclusion

Principle

For $n$ finite sets $A_1, A_2, \ldots, A_n$:

Equivalently, to count elements satisfying at least one of $n$ properties, we alternate between adding and subtracting the sizes of all intersections.

Hence, to count elements satisfying none of $n$ properties, otherwise known as the complement, we use

Furthermore, an element in exactly $k$ of the sets gets counted $\binom{k}{1}$ times in the first sum, subtracted $\binom{k}{2}$ times in the second, added $\binom{k}{3}$ times in the third, and so on. The total contribution is

for $k \geq 1$, and $0$ for $k=0$. So every element in at least one set is counted exactly once. Therefore, this explains why inclusion-exclusion works.

Derangements

Another important technique that one should ensure to know is how to solve problems using derangements. A derangement of $\lbrace 1, 2, \ldots, n \rbrace$ is a permutation where no element appears in its original position, or in other words, a permutation with no fixed points.

Let $A_i$ be the set of permutations where element $i$ is fixed. By the principle of inclusion-exclusion:

The values of derangements are hence $D_0=1$, $D_1=0$, $D_2=1$, $D_3=2$, $D_4=9$, $D_5=44$, $D_6=265$.

The recurrence $D_n = (n-1)(D_{n-1}+D_{n-2})$ is often more useful in problems, as it directly comes from casework. Element $1$ goes to some position $k \ne 1$, and then either element $k$ goes to position $1$ ($D_{n-2}$ arrangements) or it does not ($D_{n-1}$).

As $n \to \infty$, $D_n/n! \to 1/e \approx 0.368$. Something that is not necessary to know but is useful information is that for any large $n$, about $36.8\%$ of all permutations are derangements.

Bijections and Double Counting

Bijections

A bijection between two sets $A$ and $B$ means that they have a one-to-one correspondence. Every element of $A$ maps to exactly one element of $B$ and vice versa. Hence if a bijection exists, $|A| = |B|$.

The important idea of bijections is that to count a complicated set $A$, we find a simpler set $B$ you already know how to count, and exhibit a bijection $A \to B$.

The Stars and Bars formula $\binom{n+k-1}{k-1}$ that is used for distributing $n$ identical objects into $k$ bins is itself a bijection between solutions to $x_1 + \cdots + x_k = n$ and $(k-1)$-element subsets of $\lbrace 1, \ldots, n+k-1 \rbrace$.

Double Counting

Double counting means counting the same quantity in two different ways and equating the results accordingly. This often proves combinatorial identities or gives important information for a question that counting alone would not give.

Example. Prove $\displaystyle\sum_{k=0}^n \binom{n}{k}^2 = \binom{2n}{n}$.

We can think of this situation as the number of ways to choose $n$ people from a group of $n$ men and $n$ women. This gives $\binom{2n}{n}$. Alternatively, we choose $k$ men and $n-k$ women for each $k$, giving

Since these are equal, we prove Vandermonde's identity in the symmetric case.

There are many other standard ways to do this.

Catalan Numbers

Catalan numbers are natural numbers that appear in many counting problems involving recursive or non-crossing structures.

The $n$th Catalan number is

The first few values are

Some common appearances of Catalan numbers are:

• The number of sequences of $n$ steps right and $n$ steps up from $(0,0)$ to $(n,n)$ that never go above the diagonal $y=x$ is $C_n$.

• The number of ways to fully parenthesize a product of $n+1$ factors is $C_n$.

• The number of ways to triangulate a convex $(n+2)$-gon is $C_n$.

• The number of ways to connect $2n$ points on a circle with $n$ non-crossing chords is $C_n$.

More generally, the number of paths from $(0,0)$ to $(m,n)$ using unit right and up steps that never go above the diagonal $y=x$, meaning there are always at least as many right steps as up steps, is

One way to prove this is by reflection. Count all paths from $(0,0)$ to $(m,n)$, then subtract the bad paths that go above the diagonal. A bad path must touch the line $y=x+1$. Reflecting the part of the path up to its first touch of this line gives a bijection with paths from $(-1,1)$ to $(m,n)$.

Thus,

For the special case $m=n$, this becomes

Solving Linear Recurrences

Furthermore, linear recurrences with constant coefficients are another type of difficult competition problem.

The characteristic equation is

If its roots are $r_1,\ldots,r_k$, then the general solution is

where the constants $A_i$ are determined by conditions given in the question.

For the Fibonacci recurrence $f(n)=f(n-1)+f(n-2)$, the roots are $\phi=(1+\sqrt5)/2$ and $\hat\phi=(1-\sqrt5)/2$, which gives Binet's formula:

These are often for more complex problems, but it may be fruitful to know.

Examples

Example 1: Inclusion-Exclusion

Problem. How many permutations of $AABBCC$ have no two adjacent identical letters?

Solution. First, we calculate the total arrangements of $AABBCC$:

Let $A_1$ be the arrangements with both A's adjacent, $A_2$ be the arrangements with both B's adjacent, and $A_3$ be the arrangements with both C's adjacent.

For each $i$,

If two pairs are adjacent, then there are

arrangements. Since there are $\binom{3}{2}=3$ choices for the two adjacent pairs, the total contribution is $36$.

If all three pairs are adjacent, then there are

arrangements.

Thus, by inclusion-exclusion,

Arrangements with no two adjacent identical letters are therefore

Example 2: Derangements

Problem. Five students each write their name on a card, then the cards are shuffled and redistributed. What is the probability that no student receives their own card?

Solution. We first find the total amount of permutations: $5!=120$. Hence, the number of derangements is

Probability is therefore

Example 3: Catalan Numbers

Problem. How many sequences of $+1$ and $-1$ of length $10$ have all partial sums nonnegative? In other words, every prefix has at least as many $+1$s as $-1$s.

Solution. This is equivalent to counting sequences of $5$ steps right and $5$ steps up from $(0,0)$ to $(5,5)$ that stay below the diagonal.

Thus, this is the number of paths from $(0,0)$ to $(n,n)$ staying below $y=x$, and the number of sequences of $n$ values $+1$ and $n$ values $-1$ with all partial sums nonnegative, starting from $0$, is the Catalan number

For $n=5$:

Example 4: Recursion

Problem. A frog starts at step $0$ of a staircase. At each jump, it can go up $1$ or $2$ steps. How many ways can it reach step $10$?

Solution. Let $f(n)$ be the number of ways to reach step $n$.

The recurrence is

with $f(0)=1$ and $f(1)=1$.

Then

Practice Problems