Here is what I got so far.

The idea is to look for a (very complicated) recursion.

I'm going to consider vectors of the form

where

c - the current distance

d - the maximum distance observed so far.

The idea is then to use an extended version of pascals identity:

but clearly

is a recursion on n-1!

In fact you only need to recurse on

, because the other side of the recursion tree is symmetric.

As you expand out the tree for

a miracle happens, all the terms you have computed before start reappearing all over the place, for the exact same values of c (thats important) but possibly different values of d (not important to the recursion, but still important in tallying up the number of paths of maximum length d.) So the entire thing starts to recurse, I haven't yet figured out the exact recursion but only the binomial and c are the important values when determining the recursion.

Well, this isn't complete by any stretch of the imagination but it may give some fuel for some better thoughts. Here is a picture of what the (basic) recursion tree looks like, obviously you would need to expand it out to get a better idea:

edit --- it may be unclear why I'm doing such a recursion, so I'll give an example

if you consider the case n=3 then compute the entire recursion tree using that identity until all leaf nodes in the recursion tree you construct are of the form

or

then that means to get the number of paths of maximum length d you sum up all the leaf nodes (they will all be equal to 1) where d is the desired value. For n = 3 this gives for d=1, 8, d=2, 10 and d = 3, 2.