Count number of ways kangaroo can jump all points in interval and finish at last point

There is the problem from Flajolet and Sedgewick book "Analytical Combinatorics":

"In how many ways can a kangaroo jump through all points of the integer interval $[1,n+1]$ starting at $1$ and ending at $n + 1$, while making hops that are restricted to $\{-1,1,2\}$?"

I'm trying to derive recurrence relation for that problem. Here's my reasoning.

Kangaroo can arrive at point $n + 1$ (i.e. finish his trip) only from points $n$ and $n - 1$. Let A(a, b) be the number of ways to start at point $1$, visit all $b$ points and arrive at point $a$. So the number of ways to jump all points from $1$ to $n + 1$ equals $A(n + 1, n + 1)$. Then the following recurrence can be formulated: $$A(n + 1, n + 1) = A(n, n) + A(n - 1, n)$$
As described in mentioned book this function is Narayana's cows sequence (OEIS A000930) and its recurrence relation is $a(n) = a(n-1) + a(n-3)$. But how can I convert my recurrence with two variables into an ordinary linear recurrence? By using generating functions? Or maybe something's wrong with my reasoning and there is an easier way to come with linear recurrence?

Thanks!

• Your recurrence relation seems incomplete as it gives only $A(a,b)$ for $a=b$ from smaller arguments. I would try my hand at expanding it, but I'm not sure what to make of "visit all $b$ points". Apparently the kangaroo can jump plus one or two or minus one, and always starts at 1. Then you want to count trips that take a certain number of jumps before reaching $a$. Is $b$ the number of jumps plus one (for starting at 1)? Mar 3 '15 at 15:27
• Assume base cases are given. Assume there is 5 points numbered from 1 to 5. Then A(5,5) is the number of ways to jump all 5 points and stop at point 5; A(3,4) is the number of ways to jump points 1, 2, 4 and stop at point 3. Mar 3 '15 at 15:35
• So it is required to visit every point, but only once per point? Mar 3 '15 at 15:50
• Yes. Every point can be visited exactly once. Mar 3 '15 at 15:51
• The number of ways is infinite to reach $3$ from $1$ you can go $2$ and return to $1$ and go to $2$ return to $1$, go to $2$ return to $1$ and so on and finally you can reach $3$ by making a move of $2$ so either I did not understand your question or you missed something! Mar 3 '15 at 15:57

To make sense as stated, the problem requires that each point only be visited a limited number of times. Probably, once only each.

Let's specify the recurrence $A$ more completely. In general:

$$A(p,c)=A(p+1,c-1)+A(p-1,c-1)+A(p-2,c-1)$$

where $p$ is the position at step $c$. It won't work for this problem because we forget which points have been visited and which haven't.

For example, consider $n=6$. Six steps are needed to pass through all points. But this recurrence would include the path $1\to3\to 5\to 6\to 5\to 6\to 7$, which is not valid.

So an insight is needed. The insight is this: any jump $+2$ must be followed by $-1+2$, and the $-1$ jump is not possible otherwise. This leads us to Narayana's cows sequence almost immediately.

Notice how much simpler this problem is than the other one!

Entering this into Wolfram gives a very complicated answer, but hopefully you'll be able to effectively use it. $$a(n)=a(n-1)+a(n-3)$$ The solution is $$a(n)=c_1{\left(\frac 3k\right)}^{-n}+c_2{(d)}^{n}+c_3{(e)}^{n}$$ where $c_1$ and $c_2$ are arbitrary constants $$k=1+{\left({29}-{3\sqrt{93}} \over 2 \right)}^{1/3}+{\left({29}+{3\sqrt{93}} \over 2 \right)}^{1/3}$$ $$d=\frac 13-{1-i\sqrt3\over 6}{\left({29}-{3\sqrt{93}} \over 2 \right)}^{1/3}-{1+i\sqrt3\over 6}{\left({29}+{3\sqrt{93}} \over 2 \right)}^{1/3}$$ and $$e=\frac 13-{1+i\sqrt3\over 6}{\left({29}-{3\sqrt{93}} \over 2 \right)}^{1/3}-{1-i\sqrt3\over 6}{\left({29}+{3\sqrt{93}} \over 2 \right)}^{1/3}$$

• Are you sure that this recurrence relation is true? Mar 3 '15 at 15:59
• I'm sure wolfram's right. Unless the recurrence relation given by OP is false, or I just typed it wrong, which I invite people to check, I don't think this is a extraneous solution. Notice that the imaginary units have both plus and minus sings so they should cancel out. Nevertheless, here are some values. n=0, a=0; n=3, a=1; n=6, a=3; n=9, a=9 Mar 3 '15 at 16:05
• That's what i'm saying the recurrence relation "$a(n)=a(n-1)+a(n-3)$" is not true if we allow negative moves If I understand well. The solution of any recurrence relation can be found easily but you have to be sure that this is the right relation. Mar 3 '15 at 16:10
• Oh my, your right. I was under the assumption that the relation was correct. Well, at least OP has the solution to Narayana's cow sequence. For anyone interested, the sequence solves this problem. A cow produces one calf every year. Beginning in its fourth year, each calf produces one calf at the beginning of each year. How many cows are there at the end of n years? Mar 3 '15 at 16:17
• The recurrence relation is right since the last move is either +1 (leading to $a_{n-1}$) or +2 (and then the second-to-last and third-to-last moves must be -1 and +2, leading to $a_{n-3}$). Together with the base cases of $a_0=a_1=a_2=1$, the recurrence relation gives an ordinary generating function of $\frac1{1-x-x^3}$. The solution from Mathematica is equivalent to extracting the coefficient of $x^n$ in this gf. Mar 3 '15 at 16:49