Random walk on a pentagon touching all vertices

Question

a particle is confined to jump from one vertex of a pentagon to an adjacent one every second. As a function of the number of jumps $n$, what is the number of walks that eventually touch every vertex? I have tried setting up a recurrence relation or representing the walk as a lattice path to no avail...

Answer 1

Hint: consider a "state" of the system to consist of the number of vertices visited so far and an indicator of whether the current vertex is adjacent to an unvisited vertex. Thus you start at $(1,Yes)$, and the other possible states are $(2,Yes)$, $(3,Yes)$, $(3,No)$, $(4,Yes)$, $(4,No)$ and $(5,No)$.

EDIT: Let $M_{ij}$ be the number of choices the walker can make in state $i$ that lead to state $j$. Thus in state $(1,Yes)$, there are two choices which lead to state $(2,Yes)$, so $M_{12} = 2$ and all other $M_{1j}=0$.
You want $(M^n)_{17}$.