It is known that $C_{n}$ ($n$-th Catalan number) is the number of monotonic lattice paths along the edges of a grid with $n\times n$ square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards.
- Let $n=14$ and $a_{1}\leq a_{2}\leq a_{3}\leq a_{4}$. I want to pass the following points:
$$(4,a_{1}), (8,a_{2}), (11,a_{3}),(13,a_{4})$$ such that $a_{1}<4,a_{2}<8, a_{3}<11, a_{4}<13$. Now,
What is the number of monotonic lattice paths along the edges of a grid with $n\times n$ square cells, which do not pass above the diagonal.
It seems that we use Catalan's triangle. However, I fail to do so. https://en.wikipedia.org/wiki/Catalan%27s_triangle
Best Answer
Your problem decomposes into five separate problems. You need to find the number of paths from $(0,0)\to (4,a_1)$ which do not go above $y=x$, then the number of paths $(4,a_1)\to (8,a_2)$ which do not go above $y=x$, and so on up to $(13,a_4)\to (14,14)$. You then multiply those five numbers together.
Each sub-problem is answered by the following proposition:
This can be proved using the reflection principle. If you take a "bad" path from $P_1$ to $P_2$ which at some point hits the line $y=x+1$, and reflect the subsequent portion of the path through $y=x+1$ after it first hits that line, then you get an arbitrary path from $P_1$ to $P_3:=(y_2-1,x_2+1)$. This process is reversible, so the number of "bad" paths is simply the total number of paths from $P_1$ to $P_3$. Therefore, the number of "good" paths is given by the subtraction displayed above.