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.