I am currently pondering over the problem of the number of lattice paths:
All of the legal paths (ones which do not cross over $y=x$) must begin with a move to the right and end with a move upwards. Any time the number of upward moves exceeds the number of rightward moves, the path becomes illegal. Thus, it seems that the solution is the total number of paths from $(0,0)$ to $(n,n)$ minus the total number of illegal paths. The number of paths from $(0,0)$ to $(n,n)$ is $\binom{2n}{n}$. However, I'm slightly less clear on how to compute the number of illegal paths.
I am aware of the reflection principle to calculate the illegal paths, but I'm wondering if there are any alternative methods to compute this without using the principle. I've tried to use three examples:
Let $S_n$ represent the number of illegal paths from $(0, 0)$ to $(n, n)$.
For $(0, 0)$ to $(3, 3)$: As depicted in the following diagram, all illegal paths would pass through three marked points ($p_1, p_2, p_3$). Therefore, we can calculate the number of paths as: paths through $p_1$ to $(3, 3)$ + paths through $p_2$ to $(3, 3)$ but not through $p_1$ + paths through $p_3$ to $(3, 3)$ but not through $p_1$ and $p_2$. This gives: $S_3 = 1 * \binom{5}{3} + 1 * \binom{3}{2} + 2 * \binom{1}{1} $. Diagram for $(0, 0)$ to $(3, 3)$
For $(0, 0)$ to $(4, 4)$: Similar to the previous example, all illegal paths would pass through four marked points ($p_1, p_2, p_3, p_4$). Using a similar logic, we get: $S_4 = 1 * \binom{7}{4} + 1 * \binom{5}{3} + 2 * \binom{3}{2} + 5 * \binom{1}{1} $
For $(0, 0)$ to $(5, 5)$: $S_5 = 1 * \binom{9}{5} + 1 * \binom{7}{4} + 2 * \binom{5}{3} + 5 * \binom{3}{2} + 14 * \binom{1}{1} $
However, how can one deduce from these observations that the total number of illegal paths is $\binom{2n}{n+1}$?
Additionally, I would like to inquire if there is a more intuitive way to prove when two paths are considered equal if one can be moved on top of the other by a rotation or a reflection. For instance, as shown in the following diagram, an illegal path from $S$ to $G$ can be reflected from $G$ to $H$, and then we can compute all possible paths from $S$ to $H$. I cannot grasp why this method works. Why does this cover all paths passing through the two encircled points in the diagram and leading to $G$? Diagram for reflection