Possible path of a fixed length formula

Question

I am looking for a formula that gives me all possible combinations of getting from point A(ax,ay) to point B(bx,by) using a fixed path length n. The only allowed movements are x+1, x-1, y+1 or y-1.

So if n = 3, the number possible paths to get from A to B using 3 steps should be returned.

The function should be like: f(ax,ay,bx,by,n)= ...

Example: A(-8,-7) B(5,2) n=32 Here is one of all possible combinations:

Answer 1

Let $x,\overline{x},y,\overline{y}$ be the moves $x+1$, $x-1$, $y+1$ and $y-1$ respectively.

If $z$ is a move, let $\#z$ be the number of times you used it. What is fixed by your input is $\#x-\#\overline{x}=bx-ax=X$ and $\#y-\#\overline{y}=by-ay=Y$, as well as $ \#x+\#\overline{x}+\#y+\#\overline{y}$.

This means that you are looking for words on alphabet $\{x,\overline{x},y,\overline{y}\}$ which have length $n$ and the constraints on the differences marked above.

If you fix $\#x$, then you do not have the choice for the other numbers: you have $\#\overline{X}=\#x-X$, $\#y+\#\overline{y}=n-\#x-\#\overline{x}$, and $\#y-\#\overline{y}=Y$.

This means you get for $\#x=i$:

• $\#\overline{x}=i-X$
• $\# y=\frac12(n-2i+X+Y)=k$ (for simplicity we call $k$ this new constant).
• $\#\overline{y}=\frac12(n-2i+X-Y)$.

Now for each $i$ such that all these numbers are positive, you can build your word using these letters in any order, it will yield a valid path.

So the number of valid paths with $\#x =i$ is the number of ways to choose positions in the word for these letters, which is $$f(i)={n\choose{i}}{ {n-i}\choose{i-X}}{ {n-2i+X}\choose{k}}=\frac{n!}{i!(i-X)!k!(n-2i+X-k)!}$$.

The first $i\choose n$ corresponds to choosing positions for the $x$ letters, and so on. Once you chose the positions for $x,\overline{x},y$, there is no choice for $\overline{y}$, that is why there are only 3 factors.

Now you just need to compute $N=\sum_{i=0}^n f(i)$ to get the total number you are looking for.