I want to find out how many directed simple paths from $s$ to $t$ are in the following directed graph $G=(V,E)$.
$$\begin{align}
V=&\{s, v_1, v_2,\ldots, v_n, t\}, \quad n=2k, k \in \mathbb{N} \\
E=&\{ (s, v_1), (s, v_2), \\
&\;(v_1,v_3), (v_1,v_4), (v_2,v_3),(v_2,v_4), \\
&\;(v_3,v_5), (v_3,v_6), (v_4,v_5), (v_4,v_6), \\
&\;\ldots, \\
&\;(v_{n-5},v_{n-3}), (v_{n-5},v_{n-2}), (v_{n-4},v_{n-3}), (v_{n-4},v_{n-2}), \\
&\;(v_{n-3},v_{n-1}), (v_{n-3},v_{n}), (v_{n-2},v_{n-1}), (v_{n-2},v_{n}), \\
&\;(v_{n-1},t), (v_{n},t) \}
\end{align}$$
In my opinion, there are $n$ directed paths. Is that right?
Best Answer
For each vertex of the graph, the level of the vertex is the length of the shortest directed path from $s$ to that vertex. So $s$ has level $0$, $v_{2l-1}$ & $v_{2l}$ have level $l$, and $t$ has level $k+1$. Note that each directed path from $s$ to $t$ much contain exactly one vertex from each level.
Let $s=u_0 \to u_1 \to u_2 \to\ldots \to u_k \to u_{k+1}=t$ be a directed path. Note that $u_i$ has level $i$. For each $u_i$ ($0\le i \le k-1$), there are always two possible vertices of level $i+1$ and $(u_i,u_{i+1})$ is always a directed edge in $G$. Also there is only one choice after $u_k$. Therefore, the number of such paths is $2^k$.
I also thought about bof's proposition to consider un-directed paths. Here is a proof.
Note that for an un-directed path $s=u_0\to u_1\to u_2\to\ldots \to u_r \to u_{r+1}=t$, there is at most one possible backward movement at each $u_i$ and if $u_{i+1}$ is obtained by a backward movement, $u_{i+1}$ must go to $u_{i+2}$ with a unique forward movement. Then, we cannot make another backward movement, so we have to perform another forward movement. Let's call such a backward-followed-by-forward-twice sequence a looping. Observe that two loopings cannot be done consecutively.
Observe also that if we are not at a vertex where a backward movement has just been performed, there are always two possible choices to move forward (unless you are at $v_{2k-1}$ or $v_{2k}$, where the only forward movement is to go to $t$). Therefore, our path can be represented by a binary sequence of length $k+1$, where $0$ is a forward movement and $1$ is a looping, such that the sequence starts with two $0$, and no two $1$ occur successively.
There are $F_{k+1}$ such binary sequences (since removing the two $0$ at the beginning, you are in the situation of this question). Here $F_k$ is the $k^\text{th}$ Fibonacci number with $F_0=0$ and $F_1=1$. There are $k$ forward movements each having two choices (recalling that the final forward movement has only one possible choice). This gives you a factor $2^k$. Therefore, there are $2^kF_{k+1}$ un-directed paths from $s$ to $t$.