Overview

Advanced counting often uses bijections or recursive structure. The goal is to rephrase the problem into a simpler counting model.

Recursion is especially powerful for tilings, strings with restrictions, and state-based counting processes.

Key Ideas

• Bijection: count a set by mapping it to another set of known size.
• Recursion: count size $n$ objects by splitting into smaller sizes.
• Invariants help track what must remain constant across transformations.
• Characteristic equations solve linear recurrences.

Core Skills

Build a State Recurrence

Define states by the last few choices and build a recurrence with transitions.

Use Inclusion-Exclusion Carefully

When constraints overlap, compute total minus overlaps instead of ad hoc casework.

Identify a Bijection

Map objects to lattice paths or subsets to simplify the count.

Worked Example

Let $a_n$ be the number of binary strings of length $n$ with no consecutive $1$'s. Then $a_n=a_{n-1}+a_{n-2}$ by considering the last digit. This is Fibonacci.

More Examples

Example 1: Tilings

Let $f(n)$ be the number of tilings of a $2\times n$ board with dominoes. $f(n)=f(n-1)+f(n-2)$ with $f(1)=1$, $f(2)=2$.

Example 2: Inclusion-Exclusion

How many permutations of $\{1,2,3,4\}$ have no fixed points?

$!4=4!(1-1+1/2-1/6+1/24)=9$.

Example 3: Bijection

Count binary strings of length $n$ with no consecutive $1$'s.

Map them to tilings of a $1\times n$ board with squares and dominoes.

Strategy Checklist

• Define states clearly for recurrences.
• Look for bijections to standard models.
• Use inclusion-exclusion for overlapping constraints.

Common Pitfalls

• Double-counting when states are not disjoint.
• Forgetting initial conditions in recurrences.
• Applying inclusion-exclusion without checking overlaps.

Recursion Patterns

Tilings

For a $2\times n$ board tiled by dominoes, the final placement is vertical or two horizontals, giving $f(n)=f(n-1)+f(n-2)$.

Strings with Constraints

If a string must avoid a pattern, classify by the last few characters to build states. Each state contributes a recurrence.

Linear Recurrences

If $f(n)=c_1 f(n-1)+c_2 f(n-2)$, solve $r^2-c_1 r-c_2=0$. Then $f(n)=A r_1^n + B r_2^n$ with constants from base cases.

Example 1: Explicit Recurrence

Suppose $f(n)=2f(n-1)-2^n$ with $f(0)=5$. The homogeneous solution is $C\cdot 2^n$. A particular solution is $-n\cdot 2^n$. So $f(n)=(5-n)2^n$.

Example 2: Catalan Bijections

Problem. How many permutations of ${1,2,\ldots,n}$ have no three (not necessarily consecutive) entries in decreasing order from left to right? For example, $154623$ is an example of such a permutation, while $254713$ is not, because of $541$.

Solution. We split the permutation into blocks according to its left-to-right maxima. A left-to-right maximum is a number that is larger than everything before it.

For example, in the permutation

the left-to-right maxima are

So we split the permutation right before each new left-to-right maximum:

Each block starts with its maximum. In this example, the block maxima are

Now the key observation is that in a $321$-avoiding permutation, all the numbers that are not left-to-right maxima must appear in increasing order.

For example,

has non-left-to-right maxima

which are increasing.

Why must this happen? Suppose two non-left-to-right maxima appeared in decreasing order, say

Since $a$ is not a left-to-right maximum, there is some earlier number larger than $a$. Then we would have

which forms a $321$ pattern.

For example, the permutation

does not work. The numbers $3$ and $1$ are non-left-to-right maxima, and they appear in decreasing order. Since $5$ comes before them and is larger than both, we get

which is a $321$ pattern.

So in a $321$-avoiding permutation, once we know the left-to-right maxima and the sizes of the blocks, the rest of the permutation is forced.

For example, suppose $n=7$, the block maxima are

and the block sizes are

Then the blocks must look like

The remaining numbers are

They must be placed in increasing order, so the only possible permutation is

As another example, suppose $n=6$, the block maxima are

and the block sizes are

Then the blocks must look like

The remaining numbers are

They must go in increasing order, giving

Now we connect this to Catalan paths. Let the block maxima be

and let

be the ending position of the $i$th block.

For example, in

we have

and the block ending positions are

So we get the points

These points all satisfy

because among the first $p_i$ positions, all numbers must be at most $m_i$. This means the corresponding path stays on or below the diagonal $y=x$.

Thus, each $321$-avoiding permutation gives a path from $(0,0)$ to $(n,n)$ that never goes above the diagonal.

Conversely, given a Catalan path, we can read off the block maxima and block sizes from its corner points. Then we fill in all non-left-to-right maxima in increasing order. Since the filling is forced, this gives exactly one $321$-avoiding permutation.

Therefore, the number of $321$-avoiding permutations of

is the Catalan number

For example, if $n=3$, the answer is

Indeed, the $321$-avoiding permutations are

The only permutation that does not work is

If $n=6$, the answer is

Practice Problems