Catalan Numbers Questions

Question

Show that the number of paths from $(0,0)$ to $(n,n)$ that touch the line $y=x$ only at the points $(0,0)$ and $(n,n)$ is $C_{n - 1}.$

Show that the number of paths from $(0,0)$ to $(n,n)$ that touch the line $y=x$ at the points $(0,0),$ $(n,n),$ and exactly one other point in between, is $C_{n - 1}.$

I've tried drawing out all distinct paths for small values of n, but I haven't noticed much of a pattern. Any help please...?

Answer 1

HINTS:

• A path from $\langle 0,0\rangle$ to $\langle n,n\rangle$ that touches the line $y=x$ only at its endpoints must start with a step to $\langle 1,0\rangle$ and end with a step from $\langle n,n-1\rangle$, and between those points it can touch but must not cross the line $y=x-1$.
• A path that hits the line $y=x$ exactly once between the endpoints is the concatenation of two paths that don’t hit the line between their endpoints; use the first result and a basic Catalan number recurrence.