Originally Posted by

**gmatt** 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

$\displaystyle

\left[ \binom{a}{b}, c, d \right]

$

where

c - the current distance

d - the maximum distance observed so far.

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

$\displaystyle

\left[ \binom{2n}{n}, 0, 0 \right] = \left[ \binom{2n-1}{n}, -1, 1 \right] + \left[ \binom{2n-1}{n-1}, 1, 1 \right]

$

$\displaystyle

= \left[ \binom{2n-2}{n}, -2, 2 \right] + \left[ \binom{2n-2}{n-1}, 0, 1 \right] + \left[ \binom{2n-2}{n-1}, 0, 1 \right] + \left[ \binom{2n-2}{n-2}, 2, 2 \right]

$

but clearly

$\displaystyle \left[ \binom{2(n-1)}{n-1}, 0, 1 \right]$ is a recursion on n-1!

In fact you only need to recurse on $\displaystyle \left[ \binom{2n-2}{n}, -2, 2 \right]$, because the other side of the recursion tree is symmetric.

As you expand out the tree for $\displaystyle \left[ \binom{2n-2}{n}, -2, 2 \right]$ 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 $\displaystyle \left[ \binom{k}{k}, c, d \right]$ or $\displaystyle \left[ \binom{k}{0}, c, d \right]$ 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.