Lesson 6

There is also a graph interpretation. Think of the letters as vertices of a directed graph. Draw an edge \(\sigma_{i} \to \sigma_{j}\) if the pair \(\sigma_{i}\sigma_{j}\) is allowed. Then a valid word of length \(n\) is exactly a walk of length \(n-1\) in this graph.

If \(A\) is the adjacency matrix of a directed graph, then \((A^{n})_{ij}\) is the number of walks of length \(n\) from vertex \(i\) to vertex \(j\). This can be proved by induction. For a walk of length \(n+1\) from \(i\) to \(j\), choose the previous vertex \(r\) before the last step: \[(A^{n+1})_{ij}=\sum_{r}(A^{n})_{ir}A_{rj}.\] This is the same recurrence relation as before, only written for all starting and ending vertices at once.