How would one show, without appealing to a bijection with a well known problem, that Dyck Paths satisfy the Catalan recurrence?
[Math] Showing Directly that Dyck Paths Satisfy the Catalan Recurrence
catalan-numberscombinatoricsrecurrence-relations
Related Solutions
I find it easier to work with up-down paths, defined as sequence of up-steps (e.g., from $\langle m,n\rangle$ to $\langle m+1,n+1\rangle$) and downsteps (e.g., from $\langle m,n\rangle$ to $\langle m+1,n-1\rangle$). A Dyck path is then an up-down path that does not go below the $x$-axis, and there are $C_n$ Dyck paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$.
If $n,n'\ge 0$, $m<m'$, and $t\ge 0$, let $\mathscr{D}(m,n,m',n',t)$ be the set of Dyck paths from $\langle m,n\rangle$ to $\langle m',n'\rangle$ that hit the $x$-axis exactly $t$ times, and let $d(m,n,m',n',t)=|\mathscr{D}(m,n,m',n',t)|$. Thus, $d(0,0,2n,0,2)=C_n$.
Suppose that $t\ge 1$, and $0\le k<t$. Let $P\in\mathscr{D}(m,n,m',n',t)$. Let the points where $P$ hits the $x$-axis be $\langle\ell_i,0\rangle$ for $i=1,\ldots,t$, where $\ell_1<\ldots<\ell_t$. Since $P$ is a Dyck path, $P$ has an up-step immediately after each of these points except possibly the last. Remove the first $k$ of these up-steps, and translate the resulting path upwards $k$ units to get a path $\hat P$; it’s straightforward to check that $\hat P\in\mathscr{D}(m,n+k,m'-k,n',t-k)$: the path has been shortened by $k$ steps, and the first $k$ hits have been eliminated.
This procedure is reversible. If $P\in\mathscr{D}(m,n+k,m'-k,n',t-k)$, we first shift $P$ down by $k$ units to get an up-down path $P'$. For $i=1,\ldots,k$ let $\ell_i$ be minimal such that $\langle\ell_i,1-i\rangle$ is on $P'$. Let $Q$ be the up-down path obtained from $P'$ by inserting an up-step immediately after each of the points $\langle\ell_i,1-i\rangle$. Then $Q\in\mathscr{D}(m,n,m',n',t)$, and $Q=\hat P$. It follows that
$$d(m,n,m',n',t)=d(m,n+k,m'-k,n',t-k)\;.$$
In particular,
$$d(0,0,2n,0,k+1)=d(0,k,2n-k,0,1)=d(0,0,2n-k,k,1)\;.$$
This bijection between paths $P$ and $\hat P$ is the up-down version of the correspondence that is very, very badly described at your CodeChef link, where its author writes ‘This mapping is same as decreasing value of $y$ for a path when it touches a diagonal’.
Each path in $\mathscr{D}(0,0,2n-k,k,1)$ must begin with an up-step; if we remove this up-step and shift the path one unit down and to the left, we get a Dyck path from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$. Conversely, any Dyck path from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ becomes a path in $\mathscr{D}(0,0,2n-k,k,1)$ if we shift it one unit up and to the right and prepose an up-step. Thus,
$$d(0,0,2n-k,k,1)=\sum_{t\ge 1}d(0,0,2n-k-1,k-1,t)\;.$$
Each up-down path from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ corresponds to a possible sequence of $2n-k-1$ votes, $n-1$ of them for candidate $A$ and $n-k$ of them for candidate $B$. On this interpretation the Dyck paths in $\mathscr{D}(0,0,2n-k-1,k-1,1)$ correspond to the sequences in which candidate $A$ is never behind candidate $B$. Calculating the number of such paths is essentially the ballot problem.
Clearly there are $\binom{2n-k-1}{n-1}$ up-down paths from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$. If $P$ is one of these paths that is not a Dyck path, there is a least $\ell$ such that $\langle\ell,-1\rangle$ is on the path $P$. Reflect the initial segment of $P$ between $\langle 0,0\rangle$ and $\langle\ell,-1\rangle$ in the line $y=-1$; the result is a path $P'$ from $\langle 0,-2\rangle$ to $\langle 2n-k-1,k-1\rangle$ that first hits the line $y=-1$ at $x=\ell$. Note that if this initial segment has $u$ up-steps, then it has $u+1$ down-steps, and the rest of $P$ has $n-1-u$ up-steps. As a result, $P'$ has $(n-1-u)+(u+1)=n$ up-steps and $n-k-1$ down-steps.
Conversely, if $P$ is an up-down path from $\langle 0,-2\rangle$ to $\langle 2n-k-1,k-1\rangle$ that first hits the line $y=-1$ at $x=\ell$, reflecting the first $\ell$ steps of $P$ in the line $y=-1$ produces an up-down path $Q$ from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ that first hits the line $y=-1$ at $x=\ell$, and it’s clear that $Q'=P$. Every up-down path from $\langle 0,-2\rangle$ to $\langle 2n-k-1,k-1\rangle$ hits the line $y=-1$, and there are $\binom{2n-k-1}{n}$ such paths (since each has $n$ up-steps and $n-k-1$ down-steps). Thus, the number of up-down paths from $\langle 0,0\rangle$ to $\langle 2n-k-1,k-1\rangle$ that are not Dyck paths is $\binom{2n-k-1}n$, and
$$\begin{align*} d(0,0,2n,0,k+1)&=\binom{2n-k-1}{n-1}-\binom{2n-k-1}n\\ &=\binom{2n-k-1}{n-k}-\binom{2n-k-1}{n-k-1}\\ &=\binom{2n-k-1}{n-k}\left(1-\frac{n-k}{n}\right)\\ &=\binom{2n-k-1}{n-k}\frac{k}n\;. \end{align*}$$
The Dyck paths in $\mathscr{D}(0,0,2n,0,k+1)$ correspond naturally to the paths in the plane from $\langle 0,0\rangle$ to $\langle n,n\rangle$ using only right-steps and up-steps that hit the diagonal exactly $k-1$ times between the two endpoints, or $k+1$ times including the endpoints.
I find it a bit easier to think in terms of paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$ that consist of $n$ up-steps (steps from $\langle k,\ell\rangle$ to $\langle k+1,\ell+1\rangle$) and $n$ down-steps (steps from $\langle k,\ell\rangle$ to $\langle k+1,\ell-1\rangle$). An up-step in this version corresponds to a step to the right in your version, and a down-step corresponds to a step upwards in your version. Your boundary condition becomes a requirement that my path not drop below the line $y=-z$.
We can use a slight modification of one of the usual arguments for counting the paths that don’t drop below the line $y=0$.
As in your version, there are altogether $\binom{2n}n$ paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$, and the problem is to count the ‘bad’ ones, i.e., the ones that do drop below the line $y=-z$. Suppose that we have a bad path $\pi$. There is a first point at which $\pi$ reaches the line $y=-z-1$; if it has made $u$ up-steps at that point, it must have made $u+z+1$ down-steps and so have reached the point $\langle 2u+z+1,-z-1\rangle$. Reflect the remainder of $\pi$ (i.e., the part to the right of this point) in the line $y=-z-1$. That part of $\pi$ has $n-u$ up-steps and $n-u-z-1$ down-steps, so its reflection has $n-u$ down-steps and $n-u-z-1$ up-steps. This means that it must end at the point
$$\langle 2u+z+1,-z-1\rangle+\langle2n-2u-z-1,-z-1\rangle=\langle 2n,-2z-2\rangle\;.$$
Conversely, any path from $\langle 0,0\rangle$ to $\langle 2n,-2z-2\rangle$ must hit the line $y=-z-1$, and if we reflect the part of it to the right of that intersection in the line $y=-z-1$, we get a path from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$ that drops below the line $y=-z$. Thus, we have a bijection between our bad paths and all paths from $\langle 0,0\rangle$ to $\langle 2n,-2z-2\rangle$. Each of these paths has $n-z-1$ up-steps and $n+z+1$ down-steps, so there are $\binom{2n}{n+z+1}$ of them. Thus, there are
$$\binom{2n}n-\binom{2n}{n+z+1}=\binom{2n}n-\binom{2n}{n-z-1}$$
good paths from $\langle 0,0\rangle$ to $\langle 2n,0\rangle$.
Best Answer
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}\;.$$