iv. Catalan Numbers and Lattice Paths

Catalan numbers, the reflection principle behind them, its generalisations (ballot problem, shifted and double boundaries, paths around obstacles) and the relatives (Narayana, Motzkin, Schröder, Fuss–Catalan). Binomials come from Comb in Modular Arithmetic; Stirling, Bell and the other special sequences are in Stirling, Bell and Partitions, derangements and surjections in Inclusion–Exclusion.

$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)=\frac{1}{2n+1}\left(\genfrac{}{}{0ex}{}{2n+1}{n}\right),C_0=1,C_{n+1}={\sum }_{i=0}^n{C}_i{C}_{n-i},C_n=\frac{2(2n-1)}{n+1}{C}_{n-1}.$
$1,1,2,5,14,42,132,429,1430,4862,16796,58786,\dots C(x)=\sum C_n{x}^n=\frac{1-\sqrt{1-4x}}{2x},C(x)=1+xC(x{)}^2.$
Asymptotically $C_n\sim \frac{4^n}{n^{3/2}\sqrt{\pi }}$; $C_n$ is odd iff $n=2^k-1$.

Object of size $n$ (all in bijection)	Count
balanced bracket sequences / Dyck words of length $2n$	$C_n$
mountain ranges with $n$ up and $n$ down strokes; monotone paths $(0,0)\to (n,n)$ not crossing the diagonal	$C_n$
binary trees with $n$ internal nodes; full binary trees with $n+1$ leaves	$C_n$
rooted plane (ordered) trees with $n+1$ vertices	$C_n$
ways to parenthesise a product of $n+1$ factors	$C_n$
triangulations of a convex $(n+2)$-gon	$C_n$
non-crossing chord diagrams (perfect matchings) on $2n$ points of a circle; non-crossing partitions of $[n]$	$C_n$
permutations of $[n]$ avoiding any one fixed 3-pattern (e.g. 231); stack-sortable permutations	$C_n$
standard Young tableaux of shape $2\times n$	$C_n$
ways to stack coins with $n$ coins in the bottom row (each upper coin on two below)	$C_n$

Recognising one tells you the answer to all: compute 6 terms by brute force and compare with 1, 1, 2, 5, 14, 42. When an unfamiliar sequence appears, search OEIS with the first 6–8 terms: it usually names the sequence and gives a recurrence or closed form (a legitimate contest technique).

mint catalan(int n, const Comb& cb) { return cb.C(2 * n, n) * cb.iv[n + 1]; }   // cb covers 2n
 
mint ballot(ll a, ll b, const Comb& cb) {                 // a ups, b downs, every prefix #up >= #down (a >= b)
    if (b > a) return 0;
    return cb.C(a + b, a) - cb.C(a + b, a + 1);
}
 
mint ballotStrict(ll a, ll b, const Comb& cb) {           // every non-empty prefix #up > #down: (a-b)/(a+b) C(a+b, a)
    if (a + b == 0) return 1;
    if (b >= a) return 0;
    return mint(a - b) * cb.C(a + b, a) / mint(a + b);
}
 
mint bracketCompletions(int r, int bal, const Comb& cb) { // ways to append r brackets to a prefix of balance bal >= 0
    if (bal < 0 || (r - bal) % 2 || bal > r) return 0;
    int up = (r - bal) / 2;
    return cb.C(r, up) - (up ? cb.C(r, up - 1) : mint(0));
}
 
string kthBalanced(int n, ll k) {                         // 0-indexed k-th balanced sequence of length 2n, '(' < ')', n <= 30
    vector<vector<ll>> d(2 * n + 1, vector<ll>(2 * n + 2, 0)); d[0][0] = 1;   // d[r][b]: completions of length r from balance b
    for (int r = 1; r <= 2 * n; r++) for (int b = 0; b <= 2 * n; b++) d[r][b] = d[r - 1][b + 1] + (b ? d[r - 1][b - 1] : 0);
    string s; int bal = 0;
    for (int i = 0; i < 2 * n; i++) {
        int r = 2 * n - i - 1;
        if (d[r][bal + 1] > k) s += '(', bal++;
        else k -= d[r][bal + 1], s += ')', bal--;
    }
    return s;
}

Proof: the Catalan formulas, the reflection principle and the cycle lemma

Reflection. Write a path to $(n,n)$ as a $\pm 1$ walk (up $=+1$ in the “#up − down” height). A bad walk (one that reaches height $-1$) is reflected after its first visit to $-1$: every later step is negated. This is a bijection between bad walks from 0 to 0 and all walks from 0 to $-2$ (the inverse reflects after the first visit to $-1$, which every walk to $-2$ has), and the latter have $n-1$ ups among $2n$ steps: $\left(\genfrac{}{}{0ex}{}{2n}{n-1}\right)=\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)$. So $C_n=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n+1}\right)=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. The same argument with $a$ ups and $b$ downs gives ballot, and with start height bal and end height 0 gives bracketCompletions (bad walks reach $-1$; reflecting the start across $-1$ gives start $-bal-2$, i.e. $up-1$ ups).

Strict ballot. A strictly positive walk starts with an up step and then never drops below height 1: $\text{ballot}(a-1,b)=\left(\genfrac{}{}{0ex}{}{a+b-1}{a-1}\right)-\left(\genfrac{}{}{0ex}{}{a+b-1}{a}\right)=\frac{a-b}{a+b}\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$.

Cycle lemma. Let $x_1..x_m$ be integers, each $\le 1$, with sum $k>0$; then exactly $k$ of the $m$ rotations have all partial sums positive. Extend the sequence periodically with partial sums $S_j$ ($S_{j+m}=S_j+k$). The rotation starting after position $i$ is good iff $S_j>S_i$ for all $j\in (i,i+m]$, iff $S_j>S_i$ for every $j>i$ (later periods only add $k$). Because each step rises by at most 1 and $S_j\to \pm \infty$ as $j\to \pm \infty$, for every integer $v$ the last index $i_v$ with $S_{i_v}\le v$ satisfies $S_{i_v}=v$, and these are exactly the good indices. Since $i_{v+k}=i_v+m$, a window of $m$ consecutive indices contains exactly $k$ of them. With $n+1$ entries $+1$ and $n$ entries $-1$ ($k=1$), each of the $\left(\genfrac{}{}{0ex}{}{2n+1}{n}\right)$ sequences has exactly one good rotation, and its $2n+1$ rotations are distinct (a sequence with period $p<2n+1$ would have a sum divisible by $\frac{2n+1}{p}>1$). A good rotation starts with $+1$ and the rest stays $\ge 1$ and ends at 1, so removing the leading $+1$ gives a Dyck word: $C_n=\frac{1}{2n+1}\left(\genfrac{}{}{0ex}{}{2n+1}{n}\right)$. (The old statement “entries $\ge -1$” is false: $(3,-1)$ has sum 2 but only one good rotation.) The gas station start uses the same “last minimum of the prefix sums” argument.

Recurrence and GF. A non-empty Dyck word splits uniquely as ( A ) B at the first return to height 0, with $A$, $B$ Dyck words: $C_{n+1}={\sum }_i{C}_i{C}_{n-i}$, i.e. $C(x)=1+xC(x{)}^2$; the root with $C(0)=1$ is $\frac{1-\sqrt{1-4x}}{2x}$. The ratio $\frac{C_n}{C_{n-1}}=\frac{(2n)!n!(n-1)!}{(n+1)!n!(2n-2)!}=\frac{2(2n-1)}{n+1}$. The asymptotic follows from $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\sim \frac{4^n}{\sqrt{\pi n}}$ divided by $n+1$. Parity: by Kummer (Binomial Identities) $v_2\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ is the number of 1 bits of $n$, and $v_2(n+1)$ is the number of trailing 1 bits of $n$; $C_n=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/(n+1)$ is odd iff these are equal, i.e. iff all bits of $n$ are trailing ones: $n=2^k-1$.

Bijections. A binary tree maps to ( left ) right; a plane tree to the bracket word of its DFS (open on entering a child, close on leaving); a triangulation of the $(n+2)$-gon to a binary tree rooted at the triangle on a fixed edge (the other two sides lead to the left and right sub-polygons); parenthesisations are binary trees with the factors as leaves; full binary trees with $n+1$ leaves are binary trees with $n$ internal nodes after deleting the leaves. Chords: label each chord’s first endpoint ( and second ); non-crossing means every chord encloses a balanced word, and conversely the matching of a bracket word is non-crossing. Non-crossing partitions: the block $\{1=b_1<\cdots <b_r\}$ of 1 leaves $r$ gaps (after each $b_i$) holding independent non-crossing partitions, so $F=1+{\sum }_{r\ge 1}(xF{)}^r=1+\frac{xF}{1-xF}$, which simplifies to $F=1+x{F}^2$. 231-avoiding: with $n$ at position $j$, every element before $n$ must be smaller than every element after it (otherwise $a,n,c$ with $c<a$ is a 231), and both sides avoid 231: the Catalan recurrence. Reversal and complement map 231 to 132, 213 and 312; the class $\{123,321\}$ is also counted by $C_n$ (Simion–Schmidt bijection). A permutation is stack-sortable iff it avoids 231 (Knuth). Tableaux: reading $\mathrm{1..2}n$, write ( for an entry in the top row and ) for the bottom row; the column condition is exactly the ballot condition. Coins: rotating by $45°$, a stack with $n$ bottom coins is the set of cells under a Dyck path of semilength $n$.

kthBalanced. d[r][b] counts walks of length $r$ from height $b$ to 0 staying $\ge 0$; at each position, the number of valid sequences that continue with ( is d[r][bal+1], so the lexicographic choice compares $k$ with it. Checked against brute force over all bracket sequences for $n\le 8$.

Lattice paths with boundaries and obstacles

Constraint	Count
$(0,0)\to (a,b)$, steps right and up	$\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)$
never above $y=x+c$ ($c\ge 0$), end below it	$\left(\genfrac{}{}{0ex}{}{a+b}{a}\right)-\left(\genfrac{}{}{0ex}{}{a+b}{b-c-1}\right)$ (reflect across $y=x+c+1$)
strictly between two diagonals $lo<y-x<hi$	${\sum }_{k\in \mathbb{Z}}[W(t+2kd)-W(2hi-t+2kd)]$ with $d=hi-lo$, $t=b-a$ (André, repeated reflections)
Dyck paths of height $\le h$	two-boundary formula with $lo=-1$, $hi=h+1$; also $C_n$ for $h\ge n$
avoiding $k$ blocked cells	$O(k^2)$ inclusion–exclusion over the first blocked cell hit (CF 559C)
steps E, N, NE, unrestricted	Delannoy $D(a,b)={\sum }_k\left(\genfrac{}{}{0ex}{}{a}{k}\right)\left(\genfrac{}{}{0ex}{}{b}{k}\right)2^k$
steps E, N, NE below the diagonal	large Schröder: 1, 2, 6, 22, 90, 394
up / down / flat steps staying $\ge 0$	Motzkin: 1, 1, 2, 4, 9, 21, 51, 127
Dyck paths with $k$ peaks	Narayana $N(n,k)=\frac{1}{n}\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$, ${\sum }_{k}N(n,k)=C_n$
$k$-ary trees with $n$ internal nodes; walks with steps $+(k-1)$, $-1$	Fuss–Catalan $\frac{1}{(k-1)n+1}\left(\genfrac{}{}{0ex}{}{kn}{n}\right)$

mint pathsAvoiding(int R, int C, vector<pair<int, int>> bl, const Comb& cb) {   // (0,0) -> (R,C), steps +row / +col, O(k^2)
    sort(all(bl)); bl.erase(unique(all(bl)), bl.end()); bl.push_back({R, C});
    auto g = [&](int dr, int dc) -> mint { return dr < 0 || dc < 0 ? mint(0) : cb.C(dr + dc, dr); };
    int k = sz(bl); vector<mint> f(k);                     // f[i]: paths to bl[i] avoiding every earlier blocked cell
    for (int i = 0; i < k; i++) {
        f[i] = g(bl[i].first, bl[i].second);
        for (int j = 0; j < i; j++) f[i] -= f[j] * g(bl[i].first - bl[j].first, bl[i].second - bl[j].second);
    }
    return f[k - 1];                                       // 0 if the start or the target is blocked
}
 
mint pathsBetweenLines(int n, int m, int lo, int hi, const Comb& cb) {   // n steps +x, m steps +y, lo < y - x < hi throughout (lo < 0 < hi)
    int N = n + m, t = m - n, d = hi - lo;
    if (!(lo < t && t < hi)) return 0;
    auto W = [&](ll e) -> mint { if (e < -N || e > N || (N + e) % 2) return 0; return cb.C(N, (int)((N + e) / 2)); };
    mint res = 0;
    for (ll k = -(N / d) - 2; k <= N / d + 2; k++) res += W(t + 2 * k * d) - W(2LL * hi - t + 2 * k * d);
    return res;
}
 
mint fussCatalan(int n, int k, const Comb& cb) { return cb.C(k * n, n) / mint((ll)(k - 1) * n + 1); }   // k = 2: Catalan

Complexity: pathsAvoiding $O(k^2)$ after factorials up to $R+C$; pathsBetweenLines $O(\frac{n+m}{hi-lo})$; the others $O(1)$. Notes on computing modulo a prime: the $\frac{1}{n+1}$ needs an inverse (cb.iv); keep alternating signs as mint subtraction; the $O(n^2)$ convolution recurrence is only needed for variants (it becomes $O(n\log n)$ with FFT or online convolution when the recurrence is modified); a whole row of Stirling numbers is one convolution.

Proof: boundaries, obstacles, Fuss–Catalan and Narayana

One boundary. A path that touches $y=x+c+1$ is reflected across that line from its first touch on; the end $(a,b)$ maps to $(b-c-1,a+c+1)$, and the map is a bijection onto all paths to that point, which number $\left(\genfrac{}{}{0ex}{}{a+b}{b-c-1}\right)$.

Two boundaries (André). In the walk picture the height $s=y-x$ starts at 0 and ends at $t$ after $N$ steps of $\pm 1$; $W(e)$ counts unrestricted walks ending at $e$. Let $A$ = touching $hi$, $B$ = touching $lo$. Classify a bad walk by its sequence of boundary touches, compressed to alternating letters ($ABAB\dots$). The walks whose compressed sequence contains a given alternating word $w$ as a subsequence are counted by reflecting the end point successively across the boundaries in $w$ (each reflection is a bijection, as in the one-boundary case), which yields $W$ at a translate $t+2kd$ (even length) or $2hi-t+2kd$ / $2lo-t+2kd$ (odd length). Inclusion–exclusion over these words, with sign $(-1{)}^{|w|}$, counts every bad walk exactly 0 times net, and regrouping the terms gives the stated sum. Terms vanish once $|e|>N$, so only $O(N/d)$ values of $k$ contribute.

Obstacles. Sorting cells lexicographically is a linear extension of the dominance order, so every cell that a path to bl[i] can visit before it has a smaller index. A path to bl[i] that hits blocked cells has a unique first one, bl[j], and is a path to bl[j] avoiding earlier cells ($f_j$ choices) followed by any path to bl[i]: subtracting gives $f_i$. The target is appended last; if it or the start is blocked, the subtraction removes everything.

Fuss–Catalan. Encode a $k$-ary tree with $n$ internal nodes in preorder, internal node $\to k-1$, leaf $\to -1$ (there are $(k-1)n+1$ leaves): proper prefixes have sum $\ge 0$ and the total is $-1$. Reversing and negating gives entries in $\{+1,-(k-1)\}$, all $\le 1$, sum 1, with all prefix sums positive, and every such sequence arises from exactly one tree. By the cycle lemma each of the $\left(\genfrac{}{}{0ex}{}{kn+1}{n}\right)$ arrangements has exactly one good rotation and $kn+1$ distinct rotations: $\frac{1}{kn+1}\left(\genfrac{}{}{0ex}{}{kn+1}{n}\right)=\frac{1}{(k-1)n+1}\left(\genfrac{}{}{0ex}{}{kn}{n}\right)$.

Narayana. Take the words with $n+1$ letters U and $n$ letters D and count cyclic UD factors (the number of cyclic runs of U). Pairs (word, distinguished run) correspond bijectively to (shift, word starting with U and ending with D with $k$ runs of each letter), so $k\cdot \#\text{words}=(2n+1)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. Each word has exactly one good rotation U$w$, $w$ a Dyck word, and its cyclic UD count equals the peak count of $w$ (the final D of $w$ is followed by the leading U, which is a DU). Dividing by the $2n+1$ rotations: $N(n,k)=\frac{1}{k}\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)=\frac{1}{n}\left(\genfrac{}{}{0ex}{}{n}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$.

Delannoy. Choosing which $d$ of the $a+b-d$ steps are diagonal gives $D(a,b)={\sum }_d\frac{(a+b-d)!}{d!(a-d)!(b-d)!}$. For the other form, compare generating functions: the step set gives $\sum D(a,b)x^a{y}^b=\frac{1}{1-x-y-xy}$, and with ${\sum }_a\left(\genfrac{}{}{0ex}{}{a}{k}\right)x^a=\frac{x^k}{(1-x{)}^{k+1}}$, ${\sum }_{a,b,k}\left(\genfrac{}{}{0ex}{}{a}{k}\right)\left(\genfrac{}{}{0ex}{}{b}{k}\right)2^k{x}^a{y}^b=\frac{1}{(1-x)(1-y)}\cdot \frac{1}{1-\frac{2xy}{(1-x)(1-y)}}=\frac{1}{1-x-y-xy}$. Schröder, Motzkin: first-return decompositions as for Catalan; recurrences and proofs are in Stirling, Bell and Partitions. All functions were checked against exhaustive enumeration of paths for small sizes.

Related notes

• Stirling, Bell and Partitions (Eulerian, Motzkin, Schröder, Delannoy tables)
• Generating Functions
• Ballot Problem
• DP Foundations (grid paths)