Number of Paths on a 2D Grid

Question

Given the points $(x_0, y_0)$ and $(x_1, y_1)$. How many self avoiding paths of length $L$ exist between them. I do not think an exact closed form answer exists for this. However, one could make an asymptotic bound like $O(4^L)$. Can we do better than this? For example, $(0,0)$ to $(0,5)$ has 1 length of length 5.

Answer 1

I assume all the paths are progressive: that means after every step you are closer than the previous step towards the target. Take the difference $m=y_1-y_0$ and $n=x_1-x_0$. One has to make $m$ upward steps and $n$ rightward steps. (assuming for simplicity the target point is to the right and upward of initial point. By rotating axes and swapping initial and target point this can be achieved without affecting the answer). As steps are progressive no downward or leftward steps are allowed.

So this requires $m+n$ steps totally, out of which exactly $n$ of them have to be towards the right. We can schedule the path with rightward and upward steps in any order. Each will lead to one path.

So the answer is a binomial coefficient.