Paths Within a Lattice

Lemma 4.2. The Schröder numbers $(r(n):n\geq0))$ satisfy $$r(n)=r(n-1)+\sum_{k=0}^{n-1}r(k)r(n-1-k)\text{ for }n\geq1,\text{ with } r(0)=1$$ Proof. The Schröder number $r(n)$ equals the number of lattice paths $\gamma$ that begin at $(0,0)$ and end at $(n,n)$ which use steps of the type $(1,0)$, $(0,1)$, and $(1,1)$, and never pass above the line $y=x$. There are $r(n-1)$ such paths $\gamma_1$ that begin with the diagonal step $(1,1)$. The remaining paths $\gamma_2$ begin with the horizontal step $(1,0)$. There is a first value of $x$ between $1$ and $n$ such that a path $\gamma_2$ crosses the line $y=x-1$, necessarily by a vertical step $(1,0)$. The number of such paths $\gamma_2^k$ that cross at $x=k$ equals $r(k-1)r(n-1-(k-1))$. Hence \begin{align}|\{\gamma\}| &=|\{\gamma_1\}|+\sum_{k=1}^n|\{\gamma_2^k\}|\\ &=r(n-1)+\sum_{k=1}^nr(k-1)r(n-1-(k-1))\\ &=r(n-1)+\sum_{k=0}^{n-1}r(k)r(n-1-k).\quad\square \end{align}

I want to know where the guy got the expression $$r(k-1)r(n-1-(k-1)).$$

• OK, I think I've got the idea now. At $(k, k-1)$ there are $r(k-1)$ paths for each $r(n-k)$ paths, namely $r(k-1)\cdot r(n-k)$ paths. Yeah, I don't know why the author put the obscure expression $n-1-(k-1)$. I think $n-k$ is straightforward and more revealing. – Trancot Jul 28 '13 at 6:42
• It is essential for $r(0):=1$. – Trancot Jul 28 '13 at 6:46

We’re looking at a path $\gamma_2$ that starts with a step from $\langle 0,0\rangle$ to $\langle 1,0\rangle$ and first cross the line $y=x-1$ at $x=k$. This can only happen if $\gamma_2$ stays on or below the line $y=x-1$ from $\langle 1,0\rangle$ to the point $\langle k,k-1\rangle$ and then takes a step north to $\langle k,k\rangle$. For now consider only this part of the path, from $\langle 0,0\rangle$ to $\langle k,k\rangle$; call it $\gamma_2'$.
There is one of these paths $\gamma_2'$ for each way lattice path that starts at $\langle 1,0\rangle$, ends at $\langle k,k-1\rangle$, uses only steps of the types $\langle 1,0\rangle,\langle 0,1\rangle$, and $\langle 1,1\rangle$, and never rises above the line $y=x-1$. But these paths are in one-to-one correspondence with the Schröder paths from $\langle 0,0\rangle$ to $\langle k-1,k-1\rangle$: just shift each of them one unit to the left. (Alternatively, just pretend that the point $\langle 1,0\rangle$ is the origin, and the line $x=1$ is the $y$-axis.) Thus, there are $r(k-1)$ possible choices for $\gamma_2'$.
The rest of $\gamma_2$ is the part from $\langle k,k\rangle$ to $\langle n,n\rangle$; call it $\gamma_2''$. The possible choices for $\gamma_2''$ are in one-to-one correspondence with Schröder paths from $\langle 0,0\rangle$ to $\langle n-k,n-k\rangle$: just shift them $k$ units down and to the left (or relocate the origin to $\langle k,k\rangle$). Thus, there are $r(n-k)$ choices for $\gamma_2''$. Once $k$ is chosen, $\gamma_2'$ and $\gamma_2''$ can be chosen independently, so there are $r(k-1)r(n-k)$ Schröder paths $\gamma_2$ that first cross $y=x-1$ at $x=k$. Finally, $n-k=(n-1)-(k-1)$, and you have the quoted result.
• @Trancot: It might help actually to sketch the paths for $n=4$ and $k=2$: there are only $12$ of them, with $2$ choices for $\gamma_2'$ and $6$ for $\gamma_2''$. – Brian M. Scott Jul 28 '13 at 6:03
• When it is said that $x$ is between $1$ and $n$ it is meant that $1\leq x \leq n$, is it not? – Trancot Jul 28 '13 at 6:50
• @Trancot: Yes, that’s right. If the path started out with a step to the east and then a step to the north, you’d have the first crossing at $x=1$. On the other hand, if the path started with a step to the east followed by $n-1$ steps to the northeast, the first crossing would come at $x=n$. – Brian M. Scott Jul 28 '13 at 6:53