Krdytkyu

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?

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 toldots to u_k to u_{k+1}=t$ be a directed path. Note that $u_i$ has level $i$. For each $u_i$ ($0le 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_0to u_1to u_2toldots 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$.