So, I'm reading this proof:

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)).$$

  • $\begingroup$ 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. $\endgroup$ – Trancot Jul 28 '13 at 6:42
  • $\begingroup$ It is essential for $r(0):=1$. $\endgroup$ – 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.

  • $\begingroup$ @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''$. $\endgroup$ – Brian M. Scott Jul 28 '13 at 6:03
  • $\begingroup$ When it is said that $x$ is between $1$ and $n$ it is meant that $1\leq x \leq n$, is it not? $\endgroup$ – Trancot Jul 28 '13 at 6:50
  • $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Jul 28 '13 at 6:53
  • $\begingroup$ I'm just being pedantic. $\endgroup$ – Trancot Jul 28 '13 at 7:29

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.