---
tag: 017SRZ7NE9
kind: statement
role: theorem
name: Dyck words are counted by Catalan numbers
msc: [05A15]
uses: [092DRBFKMG, 0R9JR0465V]
sources:
  - url: https://en.wikipedia.org/wiki/Catalan_number
    locator: Applications in combinatorics
---

## Statement

Let $n$ be a natural number.
Then the number of [[Dyck words|0R9JR0465V]] of semilength $n$ is the [[Catalan number|092DRBFKMG]] $C_n$.

## Remarks

For $n = 3$ the $5$ Dyck words are $UUUDDD$, $UUDUDD$, $UUDDUD$, $UDUUDD$ and $UDUDUD$.
Proof idea: a nonempty Dyck word has a unique form $U w_1 D w_2$, where $w_1$ and $w_2$ are Dyck words. This gives the [[Catalan recurrence|0Y1MG9R5VN]].

## Explanations

### L1 human

Each nonempty balanced bracket string starts with an opening bracket, and that bracket has a matching closing bracket.
The inside and the part after the match are smaller balanced strings, so the count satisfies the Catalan recurrence.