Recurrence-Based Counting — Mathematics Knowledge System

Overview

Many combinatorial quantities are easier to count by relating a problem of size n to smaller instances of the same problem than by writing a direct closed-form formula. Recurrence-based counting sets up a recurrence relation — an equation expressing the n-th term of a sequence in terms of earlier terms — by carefully splitting the objects being counted into cases based on what happens to a distinguished element (often the last or first one). Classic examples include the derangement numbers D_n (permutations with no fixed points), which satisfy D_n = (n-1)(D_{n-1} + D_{n-2}), and the Catalan numbers, which satisfy a convolution recurrence C_n = sum of C_i C_{n-1-i}. Once the recurrence and base cases are established, the sequence can be computed efficiently even when no simple closed form is obvious.

Intuition

The derangement recurrence comes from tracking where element n goes in a derangement of {1,...,n}. Element n must go to some position k ≠ n, say position k. Now ask what happens at position n itself in the remaining assignment: either element k goes there too (a transposition swapping n and k, leaving a derangement of the other n-2 elements: D_{n-2} ways), or element k goes anywhere else except position n (which is itself equivalent to deranging n-1 elements where k plays the role of the 'extra' element: D_{n-1} ways). Since there are n-1 choices for k, the total is (n-1)(D_{n-1}+D_{n-2}). The Catalan recurrence instead splits a balanced sequence (like balanced parentheses, or a triangulated polygon) at its first return to the baseline, giving an independent left part of size i and right part of size n-1-i for each split point i, and summing over all possible splits — a convolution.

Formal Definition

Definition

A counting recurrence expresses a_n, the number of combinatorial objects of 'size' n, in terms of a_k for k < n, together with base cases fixing the smallest values. Two workhorse examples:

D_n = (n-1)\big(D_{n-1} + D_{n-2}\big), \qquad D_0 = 1,\ D_1 = 0

Derangement recurrence

C_n = \sum_{i=0}^{n-1} C_i\, C_{n-1-i}, \qquad C_0 = 1

Catalan number recurrence

C_n = \frac{1}{n+1}\binom{2n}{n}

Catalan closed form (derivable from the recurrence via generating functions)

Worked Examples

n=2: D_2 = (2-1)(D_1+D_0) = 1·(0+1).
$D_2 = 1(0+1) = 1$
n=3: D_3 = (3-1)(D_2+D_1) = 2·(1+0).
$D_3 = 2(1+0) = 2$

Answer: D_2 = 1, D_3 = 2.

Practice Problems

Difficulty 4/10

Given D_3=2 and D_4=9, use the recurrence to find D_5.

Difficulty 5/10

Verify the Catalan closed form for n=3: compute C_3 both via the recurrence (using C_0=1,C_1=1,C_2=2) and via C_n=(1/(n+1))C(2n,n).

Difficulty 6/10

A hat-check clerk has 5 hats belonging to 5 people and returns them completely at random. How many ways can NO ONE get their own hat back (i.e. what is D_5)?

Quiz

Summary

Recurrence-based counting expresses a_n in terms of smaller a_k by casing on what happens to a distinguished element or split point.
Derangements satisfy D_n = (n-1)(D_{n-1}+D_{n-2}), derived by tracking where the n-th element goes and whether it swaps back.
Catalan numbers satisfy the convolution recurrence C_n = Σ_{i=0}^{n-1} C_i C_{n-1-i}, from splitting a balanced structure at its first return point.
Once a recurrence and base cases are known, terms can be computed efficiently even without (or before deriving) a closed form.

References

WebsiteWikipedia — Derangement
WebsiteWikipedia — Catalan number
BookGraham, Knuth, Patashnik. Concrete Mathematics, 2nd ed., Ch. 7 (Recurrences).