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: 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$.

Practice Problems