All the routes from $(0,0)$ to $(6,6)$ such that no route passes $y = x+2$ - Catalan numbers

Question

A "legal" move can be: moving one coordinate up, or one coordinate right on the $X,Y$ axis.

How can I somehow "turn" this question into the regular " a route cannot touch $ y = x$?

I'd love to get some insight.

Answer 1

It is convenient to apply Andre's reflection principle. An example with reflection at the diagonal (and ties allowed) can be found in Bertrand's ballot theorem.

• The number of all paths from $(0,0)$ to $(6,6)$ using $(1,0)$-steps and $(0,1)$-steps only is $\binom{6+6}{6}=\binom{12}{6}$.

• A bad path passing the line $y=x+2$ will touch the line $y=x+3$ the first time at a point $P$.

  Reflecting this bad path from the origin $(0,0)$ to $P$ at $y=x+3$ and leaving the rest of the bad path from $P$ to $(6,6)$ unchanged, results in a new path starting in $(-3,3)$ and going to $(6,6)$ via $P$. In fact this gives a bijection of bad paths to the set of paths starting in $(-3,3)$ and going to $(6,6)$.

  The number of reflected bad paths is $\binom{9+3}{3}=\binom{12}{3}$

We conclude the number of wanted paths is $\color{blue}{\binom{12}{6}-\binom{12}{3}=704}$.

This result can be checked easily by manually calculating the number of valid paths starting from $(0,0)$.