Maximum number of simple paths from $s$ to $t$

Question

In the given diagram below the only possible moves are E, NE or SE. I need to find the total number of simple paths (in which no vertex repeats) from $s$ to $t$.

One such path is shown by arrow.

Answer 1

Let $v_0,v_1,\ldots$ be the vertices on the bottom row, from left to right, so $v_0=s$ and $v_4=t$. Let $w_0,w_1,\ldots$ be the vertices on the second row.

Let $V_n$ be the number of paths to $v_n$ and $W_n$ the number of paths to $w_n$. We are looking for $V_n$, or, more specific, for $V_4$.

We have initial conditions $V_0=W_0=1$ and recursive relations $V_n=V_{n-1}+W_{n-1}$ and $W_n=2W_{n-1}+V_n$ for $n>1$. Substituting $W_{n-1}=V_n-V_{n-1}$ into the second relation gives us $V_{n+1}-V_n=2V_n-2V_{n-1}+V_n$ or $V_{n+1}=4V_n-2V_{n-1}$.

This is a standard homogeneous linear recurrence. Its characteristic equation is $x^2-4x+2=0$, so the characteristic roots are $2\pm\sqrt2$, which provides us with the general solution $V_n=A(2+\sqrt2)^n+B(2-\sqrt2)^n$.

The initial condition $V_0=1$ yields $A+B=1$. You can obtain $V_1=2$ either by inspection or by using the original recursive relations. This yields $A(2+\sqrt2)+B(2-\sqrt2)=2$, so we find $A=B=\frac12$.

The general solution becomes $V_n=\frac{(2+\sqrt2)^n+(2-\sqrt2)^n}2$. Use the binomial formula to write this as $V_n=\sum_{k\mbox{ even,}k=0}^n\binom nk2^{n-\frac k2}$.

The specific answer to this question then becomes $V_4=\binom402^4+\binom422^3+\binom442^2= 16+48+4=68$.