How many paths through this "hexagon structure"? How many paths are there from $x_0$ to $v_n$?:

I know its basically just counting, but I don't get it at the moment. Thank you.
edit: whoops I was in a rush sorry :D hexagon structure is what I wanted to write in the title.
 A: So here's a hint. Consider standing in $x_k$, $v_k$, $w_k$, how many roads can you pick from each of those. Maybe you could write it as an equation involving other $x$s $v$s or $w$s.

Ah what the heck, I'll show a way. But usually one is encouraged to show some effort before people will be willing to help.
So consider the matrix $$M = \left[\begin{array}{ccc}
1&1&0\\
1&1&1\\
0&1&1
\end{array}\right]$$
This is like an adjacency matrix in graph theory or something. First position is connected to two other, like $v_k$ is to $v_{k+1}$ and $x_{k+1}$, second row is $x_k$ connections and last row is $w_k$ connections. Ok?
The diagonal elements will be the number of ways. All we need to do is to calculate a matrix exponent with this M matrix and check it's diagonal elements.
so $\text{diag}(M^2) = \left[\begin{array}{c}4\\7\\4\end{array}\right]$ which you can count by hand that it is the same as going all possible ways from $v_2$ etc to $x_1$. Now to calculate this for higher powers we would like to move our matrix $M$ onto some canonical form. This could simplify the calculations a lot. We can find an eigendecomposition 
$$M = VDV^{-1}, V = \left[\begin{array}{ccc}1/2&-\sqrt{1/2}&1/2\\-\sqrt{1/2}&0&\sqrt{1/2}\\1/2&\sqrt{1/2}&1/2\end{array}\right], D = \left[\begin{array}{ccc}1-\sqrt{2}&0&0\\0&1&0\\0&0&1+\sqrt{2}\end{array}\right]$$
Now the rest should be an easy exercise to find an analytic expression for the number of ways.
