Number of distinct paths in directed graph visiting all vertices?

Question

The following child's homework problem states:

Jo is going on an 8-day activity holiday. Each day she can choose one of the water sports: kayaking or sailing, or land-based sports. She never does different water sports on consecutive days. She also wants to try all three options on at least one day of her holiday. How many different schedules are possible?

This is effectively "How many distinct walks of length 7 visiting each node at least once are there on the following directed graph?":

Or alternatively, "How many sequences of length 8 on the alphabet $\{L,K,S\}$ exist not containing the subsequence $SK$, or $KS$, and which feature each letter at least once?".

How would one solve such a problem, without exhaustively enumerating all paths?

---

• Note: If the 'must visit all vertices' condition were removed it would just be $|A^7|$, the sum of the entries of the 7th power of the adjacency matrix of the graph: British Olympiad; Combinatorics Recursion

• Note: this is not the number of Hamiltonian paths since vertices can (and at least one must) be visited more than once.

Answer 1

If we temporarily forget about the condition that requires Jo to try all three options once, then this is indeed the number of walks of length seven (not eight!) in the directed graph, which can be counted by summing the entries of $$ \begin{bmatrix}1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1\end{bmatrix}^7 = \begin{bmatrix} 120 & 169 & 119 \\ 169 & 239 & 169 \\ 119 & 169 & 120 \end{bmatrix}. $$ (It's a bit faster to compute this if instead we sum the middle row of $A^8 = ((A^2)^2)^2$.)

Then, it is easiest to eliminate the cases we don't like by inclusion-exclusion:

• Subtract the $2^8$ walks which only visit Land or Kayak;
• Subtract the $2^8$ walks which only visit Land or Sail;
• Add back the $1$ walk which only visits Land.

This gives us $1393 - 2 \cdot 256 + 1 = 882$ as the final answer.