Special Lattice Paths

We claim that $P_{x,y}$ is determined uniquely by $n = x+y$ . To see this, we note that the steps $\{(1,1), (1,0),(0,1)\}$ all increase the value of $x+y$ , and the steps $\{(1,-1), (-1,1)\}$ leave it unchanged. Consider a path from $(1,1)$ to $(x,y)$ . There is a point $(a,b)$ on the path which is the first point with $a + b = n$ From this point, there is exactly one way to get to the point $(x,y)$ . Thus, the number of paths from $(1,1)$ to $(x,y)$ is the sum of the number of paths from $(1,1)$ to one of $\{(1,n-1),(2,n-2), \ldots (n-1,1)\}$ having only one point on the path with coordinate sum $n$ . This shows that the number of paths only depends on $n$ .

Let $P_n$ be the number of paths from $(1,1)$ to a point $(x,y)$ with $x + y = n$ . We claim that $P_n = (2(n-2))P_{n-1} + (n-3)P_{n-2}$ . To see this, we note that the number of ways to get a path that terminates on a point with coordinate sum $n$ after using only one such point is to move $(0,1)$ or $(1,0)$ from one of the $n-2$ points with sum $n-1$ or $(1,1)$ from one of the $n-3$ points with sum $n-2$ . We have $P_2 = 1$ and $P_3 = 2$ as our starting values.

Applying the recursive formula gives $P_4 = 9, P_5 = 58, P_6 = 491$ , so the number of paths from $(1,1)$ to $(2,4)$ is $491$ .