In how many ways we can move from $(0,0)$ to $(10,10)$ without crossing the line where y=x.

Question

Suppose you are in $(0,0)$ you have to go to $(10,10)$ without crossing the line where y = x.
You can only move upwards or rightwards.

I have noticed that it is only asking the $10th$ Catalan number. But how I can prove it?

Answer 1

Identify each path with an ordered sequence of $10$ $H's$ (horizontal movements) and $10$ $V's$ (vertical movements). Thus, the number of paths joining $(0,0)$ to $(10,10)$ (being allowed to touch the line $y=x+1$) is $\displaystyle P_{20}^{10,10}=\binom{20}{10}.$

To get the number of paths that doesn't touch the line $y=x+1$ we will get the number of paths touching it. Let $c$ be a path joining $(0,0)$ and $(10,10)$ that touches the line $y=x+1.$ Then, there exists an integer $i$ such that in the first $i$ steps of $c$ it holds that $\mbox{number of}\: V= \mbox{number of}\: H+1.$ Suppose that $i$ is the smallest integer satisfying this property. So we can write $i=2j+1,$ where $j=\mbox{number of}\: H.$ To $c$ we will associate the path $c'$ defined by:

• $c'$ and $c$ share the first $2j+1$ steps,

• The following $2(10-j)-1$ steps of $c'$ are obtained from those in $c$ changin each $H$ in $c$ by one $V$ and each $V$ by one $H.$

Since the last $2(10-j)-1$ steps of $c$ have $10-j$ $H's$ and $9-j$ $V's,$ the step $c'$ contains $9$ $H's$ and $11$ $V's.$ That is, $c'$ is a paht joining $(0,0)$ y $(9,11).$ It is obvious that to each path $c$ correspond only one $c'.$

Conversely, each path $c'$ joining $(0,0)$ with $(9,11)$ must touch the line $y=x+1.$ In a similar way, we associate to $c'$ only one path, that joins $(0,0)$ with $(10,10)$ and touches $y=x+1.$

So, the number of paths joining $(0,0)$ and $(10,10)$ without touching the line $y=x+1$ is $$\displaystyle \binom{20}{10}- \binom{20}{9}=\frac{1}{11}\binom{20}{10}.$$