# 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.

Stanley's Enumerative Combinatorics discusses some of these issues, in particular look at Section 4.7.

-
Let me mention that one class of examples includes all recurrences with non-negative integer coefficients and non-negative integer initial conditions; the proof is to take the graph whose adjacency matrix is the companion matrix of the characteristic polynomial. This idea can be used to give a combinatorial proof of the Newton-Girard identities: see qchu.wordpress.com/2009/08/23/… and qchu.wordpress.com/2009/11/04/… . – Qiaochu Yuan Oct 29 '10 at 11:54
@qiaochu-yuan, I believe that they are precisely / exactly the same as regular languages. A perfect correspondence exists between the regular languages and the Finite State Machine representation of these regular languages as directed graphs of a probabilistic automaton. In this case, every node is an accepting node, and replace every undirected edge with a pair of directed edges. Now, in Formal Language Theory, this graph is a representation of the FSM which accepts that regular language. – sleepless in beantown Oct 30 '10 at 5:27

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$.

But again, once one enjoys the fact that every linear recurrence can be interpreted as a weighted path enumeration problem, there is usual not much motivation to actually do so. I suppose that the initial conditions are not really accounted for in this sketch, but they don't really come into solving recurrence relations until the very end.

-