Dyck Paths

1 Combinatorics of Paths

Definition: A Dyck path of length $2n$ starts at $(0,0)$, ends at $(2n,0)$, using steps $U(1,1)$ and $D(1,-1)$, staying $\ge 0$.
The Catalan Number: The total number of such valid paths is given by
$C_n = \frac{1}{n+1}\binom{2n}{n}$

PART 1 The Universe of Balanced Paths

Explore all $\binom{2n}{n}$ paths with $n$ Up and $n$ Down steps. Most dip below the horizon (Red).

Order ($n$) 3

Total Paths

Index

Navigate

PART 2 Valid Dyck Paths

Paths that never drop below the horizon. The number of these is the $n$-th Catalan Number.

Order ($n$) 3

Catalan Num

Current Path

1 / 5

Navigate

Green Line: Valid Path | Red Zone: Forbidden

PART 3 Proof by Cyclic Lemma

For any path with $n+1$ Up and $n$ Down steps (total $2n+1$), exactly one of its cyclic shifts is a valid "dominant" path (stays $>0$). This explains the $\frac{1}{2n+1}$ factor.

Order ($n$) 3

Path Groups (Orbits)

Size of each group: 7

Cyclic Shifts of Selected Group

PART 4 The Cyclic Lemma

Why does the Catalan number formula include the factor $\frac{1}{n+1}$? This comes from the Cyclic Lemma. Consider all paths of length $2n+1$ with $n+1$ Up steps and $n$ Down steps.

Imagine arranging the $2n+1$ steps in a circle. There are exactly $2n+1$ possible starting positions (cyclic shifts).

Theorem: Among all $2n+1$ cyclic shifts, exactly one is a "dominant" path that stays strictly above its starting level (except at the start).

Result: The number of valid Dyck paths of length $2n$ is exactly the number of such dominant paths of length $2n+1$ (by removing the first Up step), which is $$\frac{1}{2n+1} \binom{2n+1}{n} = \frac{1}{2n+1}\frac{[(2n+1)](2n)!}{(n+1)!n!}=\frac{1}{n+1} \binom{2n}{n}.$$

Start?

1 / (2n+1)

Selection Ratio

Only 1 out of $2n+1$ shifts is valid.