Sign in to watch this lesson
Algorithms - Recursion, Backtracking and Combinatorics · 4:13
Catalan Numbers
An order book that receives n buys and n fills and may never go negative is a lattice path that never rises above the diagonal. For n = 3, 5 of the 20 paths survive, and the reflection trick explains why: flipping a bad path after its first step above the diagonal pairs it with one of the 15 paths to (2, 4), so C_n = C(2n, n) - C(2n, n-1) = C(2n, n)/(n+1). The survivors become balanced brackets and full binary trees, the (A)B split gives the recurrence, and we finish with the traps (int overflow, 64-bit limits, dividing under a modulus) and the ballot problem.
You will learn
- Recognise Catalan structures: sequences that never dip below zero, balanced brackets, full binary trees, paths below the diagonal
- Derive C_n = C(2n, n) - C(2n, n-1) = C(2n, n)/(n+1) with the reflection argument
- Derive the recurrence C_n = sum C_k C_(n-1-k) from the unique (A)B decomposition
- Compute C_n modulo a prime with factorial tables and a modular inverse, avoiding int and 64-bit overflow