I would like to flesh out the connection between finite pointed graphs and recursion relations a little more.

Suppose we have a recursion relation of the form $$a_{n+m}=\sum_{j=1}^m\beta_ja_{n+m-j}\qquad\text{for }\beta_j\in\mathbb{N},\,m>0,\,\beta_m\neq0.$$ I think there is a nice graph with the fewest possible nodes that yields this recurrence relation for its sequence that counts the number of paths of a given length.

This graph can be built up as follows. Start with a loop of length \\(m\\) with a distinguished point \\(x_1\\), name the other nodes \\(x_2,...,x_{m}\\). Add \\(\beta_m-1\\) arrows from \\(x_m\\) to \\(x_1\\), then add \\(\beta_{m-1}\\) arrows from \\(x_{m-1}\\) to \\(x_1\\), then add \\(\beta_{m-2}\\) arrows from \\(x_{m-2}\\) to \\(x_1\\), and so on until you add \\(\beta_1\\) arrows from \\(x_1\\) to itself. This process gives us a pointed graph unique up to arrow labelling.

No graph with fewer than \\(m\\) nodes can have a basic loop (in the sense of a loop not decomposable into loops of shorter length) of length \\(m\\), so if this graph satisfies the recurrence relation, it is a graph with the fewest possible nodes that does so. Following Dr. Baez's idea in [comment #4](https://forum.azimuthproject.org/discussion/comment/18795/#Comment_18795), a loop of length \\(n+m\\) comes from a loop of length \\(n+m-1\\) composed with one of the \\(\beta_1\\) loops of length 1 or from a loop of length \\(n+m-2\\) composed with one of the \\(\beta_2\\) basic loops of length 2, and so on, or a loop of length \\(n\\) composed with one of the \\(\beta_m\\) loops of length \\(m\\). So, this graph produces the desired recursion relation.

Note that the opposite graph, the graph with the same nodes but with the arrows reversed, yields the same recurrence relation.

If \\(\gcd(\\{\beta_j\\}_{1\leq j\leq m})=1\\), then I think this graph (and its opposite) has the fewest possible arrows for a graph with \\(m\\) nodes that gives the above recurrence relation.

Suppose we have a recursion relation of the form $$a_{n+m}=\sum_{j=1}^m\beta_ja_{n+m-j}\qquad\text{for }\beta_j\in\mathbb{N},\,m>0,\,\beta_m\neq0.$$ I think there is a nice graph with the fewest possible nodes that yields this recurrence relation for its sequence that counts the number of paths of a given length.

This graph can be built up as follows. Start with a loop of length \\(m\\) with a distinguished point \\(x_1\\), name the other nodes \\(x_2,...,x_{m}\\). Add \\(\beta_m-1\\) arrows from \\(x_m\\) to \\(x_1\\), then add \\(\beta_{m-1}\\) arrows from \\(x_{m-1}\\) to \\(x_1\\), then add \\(\beta_{m-2}\\) arrows from \\(x_{m-2}\\) to \\(x_1\\), and so on until you add \\(\beta_1\\) arrows from \\(x_1\\) to itself. This process gives us a pointed graph unique up to arrow labelling.

No graph with fewer than \\(m\\) nodes can have a basic loop (in the sense of a loop not decomposable into loops of shorter length) of length \\(m\\), so if this graph satisfies the recurrence relation, it is a graph with the fewest possible nodes that does so. Following Dr. Baez's idea in [comment #4](https://forum.azimuthproject.org/discussion/comment/18795/#Comment_18795), a loop of length \\(n+m\\) comes from a loop of length \\(n+m-1\\) composed with one of the \\(\beta_1\\) loops of length 1 or from a loop of length \\(n+m-2\\) composed with one of the \\(\beta_2\\) basic loops of length 2, and so on, or a loop of length \\(n\\) composed with one of the \\(\beta_m\\) loops of length \\(m\\). So, this graph produces the desired recursion relation.

Note that the opposite graph, the graph with the same nodes but with the arrows reversed, yields the same recurrence relation.

If \\(\gcd(\\{\beta_j\\}_{1\leq j\leq m})=1\\), then I think this graph (and its opposite) has the fewest possible arrows for a graph with \\(m\\) nodes that gives the above recurrence relation.