# Which integer recurrence relations can be formulated as counting walks on a graph?

Observation: If we take the graph with two vertices, A and B, with a loop {A,A} and undirected edge {A,B}, then the number of closed walks $W_n$ of length $n \geq 1$ starting from A we get $W_1=1$ (counting AA), $W_2=2$ (counting AAA and ABA) and $W_n=W_{n-1}+W_{n-2}$, i.e. the Fibonacci numbers.

Question: Which types of recurrences can be realised as the number of closed walks from the origin of a graph?

More generally, which types of recurrences can be realised as the number of walks of some type in some graph?

If we can interpret a recurrence relation as the number of walks in a graph in some way, then might be able to use spectral theory to find formulas for the sequence. (see: Frank Harary and Allen J. Schwenk, The spectral approach to determining the number of walks in a graph. Pacific J. Math. Volume 80, Number 2 (1979), 443-449.)

• Duplicate? mathoverflow.net/questions/3939/… – Qiaochu Yuan Oct 29 '10 at 8:04
• Must the graphs be undirected? (Your example has undirected edges, but you don't state that in your question itself.) – Mike Spivey Oct 29 '10 at 17:26
• At this point, I don't care about the specifics, just as long as it's possible to count walks. – Douglas S. Stones Oct 29 '10 at 21:40
• @Mike-Spivey, the undirected graph can be transformed into a directed graph, retaining the "undirectedness" of the original graph by:  replacing each undirected edge between two vertices with a pair of directed edges between the same two vertices. A directed graph version of this allows for a direct correspondence to the class of regular languages accepted by a Nondeterministic Finite Automaton. (see my comment below Qiaochu Yuan's answer on this page) – sleepless in beantown Oct 30 '10 at 8:02

Okay, so it's not quite a duplicate because I guess you're asking about initial conditions as well. The generating functions of the sequences $a_n$ which have this property are called $\mathbb{N}$-recognizable or $\mathbb{N}$-rational in the literature, and they are essentially (precisely?) the generating functions of word lengths in regular languages (star example: the look-and-say sequence). Not all rational functions with non-negative integer coefficients are $\mathbb{N}$-rational; see for example the counterexamples in these slides. These slides also seem relevant.
If the motivation is to use spectral methods, then there is no need to interpret things as a graph. To count walks in a graph one gets a recurrence relation (given by the adjacency matrix) and proceeds using spectral methods. If $A$ is an $n \times n$ matrix and $x_0$ a column vector then setting $x_{m+1}=Ax_m$ leads to a system of $n$ first order linear recurrences in the $n$ positions. In most non-degenerate cases one can get a single $nth$ order recurrence for a particular entry (or linear combination of entries). Similarly for the $r,c$ entry of $A^m$, the trace and other linear combinations. Really one is studying the entries of $A^m$ since $A^mx_0=x_m$. In the case that one starts with an $nth$ order linear recurrence one just has a rather special kind of graph.
That said, if the entries of $A$ are non-negative integers then one can naturally interpret $A^m$ as counting length $m$ walks in a certain $n$-vertex directed graph with multiple edges and loops allowed. For an arbitrary $n \times n$ matrix with entries from a ring one could consider the entries as multiplicitive edge weights on the complete $n$-vertex directed graph (with loops) and $A^m$ as recording in position $u,v$ the total weight of the length $m$ paths starting at $u$ and ending at $v$.