1
$\begingroup$

How would one show, without appealing to a bijection with a well known problem, that Dyck Paths satisfy the Catalan recurrence?

$\endgroup$
1
  • $\begingroup$ Isn't this the Segner recurrence for Catalan numbers? $\endgroup$ Dec 6 '20 at 17:13
4
$\begingroup$

There are at least two different definitions of Dyck path; I prefer to think of them as mountain ranges, i.e., paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$, using steps $\langle 1,1\rangle$ and $\langle 1,-1\rangle$, that do not drop below the $x$-axis. If you think of them as lattice paths from $\langle 0,0\rangle$ to $\langle n,n\rangle$ that do not rise above the diagonal line $y=x$, it’s not hard to make the conversion: your step to the right is my up-step, your step up is my down-step, and the diagonal line corresponds to my $x$-axis.

Let $P$ be a Dyck path of length $2(n+1)$, and let $\langle 2k,0\rangle$ be the first point to the right of $\langle 0,0\rangle$ at which $P$ hits the $x$-axis. The part of $P$ from $\langle 0,0\rangle$ to $\langle 2k,0\rangle$ is a Dyck path of length $2(k-1)$ preceded by an up-step and followed by a down-step, and the part of $P$ from $\langle 2k,0\rangle$ to $\langle 2(n+1),0\rangle$ is a Dyck path of length $2(n+1-k)$. There are $C_{k-1}$ Dyck paths of length $2(k-1)$, and there are $C_{n+1-k}$ Dyck paths of length $2(n+1-k)$. Finally, $k$ ranges from $1$ through $n+1$, so

$$C_{n+1}=\sum_{k=1}^{n+1}C_{k-1}C_{n+1-k}=\sum_{k=0}^nC_kC_{n-k}\;.$$

$\endgroup$
2
$\begingroup$

The Dyck language $D$ is given by the BNF description $$ D = \epsilon \mid \mathtt( ~ D ~ \mathtt) ~ D \qquad\text{where $\epsilon$ is the empty word}. $$ (the parentheses are literals, and the language consists of balanced strings of parentheses). Interpreting the opening and closing parentheses as up-steps respectively down-steps (both with a fixed sideways component), the total level along the path never drops below $0$, and is $0$ at the end of the path.

This grammar is non-ambiguous: every Dyck word matches it (recursively) in a unique manner. It follows that there is one Dyck word of length $0$, and that the number of Dyck words of length $n+1$ eqals the number of ordered pairs of Dyck words of combined length $n$. That is the Catalan recurrence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.