---
tag: CXC72Q81V9
kind: proof
name: Proof that Dyck words are counted by Catalan numbers, by first return decomposition
msc: [05A15]
proves: 017SRZ7NE9
uses: [0R9JR0465V, 092DRBFKMG, 0EE2V3CHFK, 0VPK4X73Q0, 0GV2573FP4, 0KMVFSHFGZ]
sources:
  - url: https://en.wikipedia.org/wiki/Catalan_number
    locator: Proof of the formula, Fifth proof
---

## Proof

We show that the counts satisfy the Catalan recursion, and conclude by [[strong induction|0KMVFSHFGZ]].

1. For a natural number $m$, let $W_m$ be the set of [[Dyck words|0R9JR0465V]] of semilength $m$, and let $d_m = |W_m|$. These words have length $2m$ over two letters, so $W_m$ is finite.
2. For a word $p$, let $h(p)$ be its number of letters $U$ minus its number of letters $D$. A word $w$ is a Dyck word exactly when $h(w) = 0$ and $h(p) \ge 0$ for every prefix $p$ of $w$.
3. The only word of length $0$ is the empty word, and it is a Dyck word. So $d_0 = 1$.
4. Fix a natural number $n$, and let $w \in W_{n+1}$. Write $w_{\le t}$ for the prefix of $w$ of length $t$. The set of $t \ge 1$ with $h(w_{\le t}) = 0$ contains $2n + 2$, so it has a least element $t_0$.
5. The first letter of $w$ is $U$, since $h(w_{\le 1}) \ge 0$. For $1 \le t < t_0$ we have $h(w_{\le t}) \ge 1$, by step 2 and the choice of $t_0$.
6. Each letter changes $h$ by $1$ or $-1$. Since $h(w_{\le t_0 - 1}) \ge 1$ and $h(w_{\le t_0}) = 0$, letter $t_0$ is $D$ and $h(w_{\le t_0 - 1}) = 1$.
7. So $w = U\, w_1\, D\, w_2$, where $w_1$ consists of the letters $2$ to $t_0 - 1$ and $w_2$ of the letters after $t_0$.
8. The word $w_1$ is a Dyck word. Its prefixes $q$ satisfy $h(q) = h(Uq) - 1 \ge 0$ by step 5, and $h(w_1) = h(w_{\le t_0 - 1}) - 1 = 0$ by step 6.
9. The word $w_2$ is a Dyck word. Its prefixes $q$ satisfy $h(q) = h(U w_1 D q) \ge 0$, because $h(U w_1 D) = 0$. Likewise $h(w_2) = h(w) = 0$.
10. If $w_1$ has semilength $i$, then $w_2$ has semilength $n - i$, because $w$ has $n + 1$ letters $U$. So $0 \le i \le n$.
11. Conversely, let $0 \le i \le n$, $w_1 \in W_i$ and $w_2 \in W_{n-i}$, and let $w = U\, w_1\, D\, w_2$. Its prefixes have $h$ equal to $0$, $1 + h(q)$ for a prefix $q$ of $w_1$, or $h(q)$ for a prefix $q$ of $w_2$.
12. All of these are at least $0$, and $h(w) = 0$. So $w \in W_{n+1}$.
13. In this $w$, the prefixes of lengths $1$ to $2i + 1$ have $h \ge 1$, and the prefix of length $2i + 2$ has $h = 0$. So $t_0 = 2i + 2$, and step 7 recovers $w_1$ and $w_2$.
14. Hence $w \mapsto (w_1, w_2)$ is a bijection from $W_{n+1}$ onto the disjoint union over $0 \le i \le n$ of the sets $W_i \times W_{n-i}$.
15. By the [[bijection principle|0GV2573FP4]], the [[rule of sum|0EE2V3CHFK]] and the [[rule of product|0VPK4X73Q0]], $d_{n+1} = \sum_{i=0}^{n} d_i\, d_{n-i}$.
16. The [[Catalan numbers|092DRBFKMG]] satisfy $C_0 = 1$ and $C_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i}$. We show $d_m = C_m$ for all $m$ by strong induction on $m$.
17. For $m = 0$, $d_0 = 1 = C_0$ by step 3. For $m = n + 1$, assume $d_i = C_i$ for all $i \le n$. Then step 15 gives $d_{n+1} = \sum_{i=0}^{n} C_i\, C_{n-i} = C_{n+1}$.
18. Hence the number of Dyck words of semilength $n$ is $C_n$ for every natural number $n$.

## Idea

A nonempty Dyck word returns to level $0$ for a first time. Cutting it there writes it uniquely as $U w_1 D w_2$ with two shorter Dyck words. So the counts obey the same recursion and start value as the Catalan numbers.