Which integer recurrence relations can be formulated as counting walks on a graph? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T10:31:12Z http://mathoverflow.net/feeds/question/44068 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44068/which-integer-recurrence-relations-can-be-formulated-as-counting-walks-on-a-graph Which integer recurrence relations can be formulated as counting walks on a graph? Douglas S. Stones 2010-10-29T06:04:38Z 2010-10-30T04:23:38Z <p><strong>Observation</strong>: 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.</p> <blockquote> <p><strong>Question</strong>: Which types of recurrences can be realised as the number of closed walks from the origin of a graph?</p> <p>More generally, which types of recurrences can be realised as the number of walks of some type in some graph?</p> </blockquote> <p>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, <a href="http://projecteuclid.org/DPubS?verb=Display&amp;version=1.0&amp;service=UI&amp;handle=euclid.pjm/1102785717&amp;page=record" rel="nofollow">The spectral approach to determining the number of walks in a graph</a>. Pacific J. Math. Volume 80, Number 2 (1979), 443-449.)</p> http://mathoverflow.net/questions/44068/which-integer-recurrence-relations-can-be-formulated-as-counting-walks-on-a-graph/44084#44084 Answer by Qiaochu Yuan for Which integer recurrence relations can be formulated as counting walks on a graph? Qiaochu Yuan 2010-10-29T08:12:07Z 2010-10-29T08:20:52Z <p>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 <a href="http://en.wikipedia.org/wiki/Regular_language" rel="nofollow">regular languages</a> (star example: the <a href="http://en.wikipedia.org/wiki/Look-and-say_sequence" rel="nofollow">look-and-say sequence</a>). Not all rational functions with non-negative integer coefficients are $\mathbb{N}$-rational; see for example the counterexamples in <a href="http://people.brandeis.edu/~gessel/homepage/papers/nonneg.pdf" rel="nofollow">these slides</a>. <a href="http://www.risc.jku.at/people/ckoutsch/research/datalk.pdf" rel="nofollow">These slides</a> also seem relevant. </p> <p>Stanley's <em>Enumerative Combinatorics</em> discusses some of these issues, in particular look at Section 4.7.</p> http://mathoverflow.net/questions/44068/which-integer-recurrence-relations-can-be-formulated-as-counting-walks-on-a-graph/44218#44218 Answer by Aaron Meyerowitz for Which integer recurrence relations can be formulated as counting walks on a graph? Aaron Meyerowitz 2010-10-30T04:23:38Z 2010-10-30T04:23:38Z <p>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. </p> <p>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$. </p> <p>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. </p>