Maximum number of simple paths from $s$ to $t$ 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.

 A: 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$.
