Generating function for the number of walks in a graph

Question

According to a note for OEIS A052987: "Form the graph with matrix $A=[1,1,1,1;1,0,0,0;1,0,0,0;1,0,0,1]$. Then the sequence $1,1,2,4,\ldots$ with g.f. $(1-x-2x^2)/(1-2x-2x^2+2x^3)$ counts closed walks of length $n$ at the degree $3$ vertex.", if I understand correctly, all closed walks from node $4$ to itself for the graph:

are counted by the generating function:

$$g(x) = \frac{1-x-2x^2}{1-2x-2x^2+2x^3}$$

corresponding to the sequence $1,1,2,4,10,24,60,148,\ldots$ for $n=0,1,2,3,\ldots$

and I can verify the first terms. But how can we prove it? Is there a standard method for deriving that generating fuction? In particular, how can we get the generating function for the number of walks from node $3$ to itself for the following graph:

and in general for a graph of the following form, for a walk from $k$ to itself:

Answer 1

The standard method relies on two facts: (1) The number of length $k$ walks from vertex $i$ to $j$ is given by $(A^k)_{ij}$ (Why? Think in particular about the cases of $k=1$ and $k=2$); and (2) the identity $$\sum_{k\ge0}(A^k)_{ij}z^k =\Bigl(\sum_{k\ge0}A^kz^k\Bigr)_{ij} =\bigl((I-Az)^{-1}\bigr)_{ij},$$ where $I$ denotes the identity matrix of the appropriate size.

For the example you give, we are interested in $\bigl((I-Az)^{-1}\bigr)_{44}$, where $$A=\begin{pmatrix} 1&1&1&1\\ 1&0&0&0\\ 1&0&0&0\\ 1&0&0&1 \end{pmatrix}.$$ Using Cramer's rule to invert the matrix, we are looking for $\operatorname{adj}(I-Az)_{44}/\det(I-Az)$. Since $\det(I-Az)=1-2z-2z^2+2z^3$ and $$\operatorname{adj}(I-Az)_{44}=\det\begin{pmatrix} 1-z&-z&-z\\ -z&1&0\\ -z&0&1 \end{pmatrix} =1-z-2z^2,$$ the result follows.

Answer 2

The reason why we have $$g(x) = \frac{\operatorname{adj}(I-xA)_{kk}}{\det(I - xA)}$$ has already been explained in a different answer.

To solve the general case using this method, we could apply this to a $k \times k$ matrix, but there is a simpler way. As far as closed walks starting and ending at vertex $k$ are concerned, vertices $2,\dots,k-1$ are identical. Instead of having $k-2$ of those vertices, we could replace them by a single vertex with (and this is critical) $k-2$ edges from vertex $1$ to the combined vertex, but only one edge from the combined vertex back to vertex $1$. In this way, there are $k-2$ ways to take a step from vertex $1$ to the combined vertex, then return to vertex $1$ - just as in the original graph.

The resulting directed graph has matrix $$A = \begin{bmatrix}1 & k-2 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1\end{bmatrix},$$ where the combined vertex corresponds to row and column $2$, and the former vertex $k$ corresponds to row and column $3$. This gives us the generating function $$ g(x) = \frac{\begin{vmatrix}1-x & -(k-2)x \\ -x & 1\end{vmatrix}}{\begin{vmatrix}1-x & -(k-2)x & - x \\ -x & 1 & 0 \\ -x & 0 & 1-x\end{vmatrix}} = \frac{1 - x - (k-2)x^2}{1 - 2x - (k-2)x^2 + (k-2)x^3}. $$ In particular, we get $g(x) = \frac{1-x-x^2}{1-2x-x^2+x^3}$ when $k=3$, and the sequence of closed walks is found in OEIS A052534. When $k=4$, we get $g(x) = \frac{1-x-2x^2}{1-2x-2x^2+2x^3}$, as in the question. The sequences for higher $k$ do not appear to be listed in the OEIS.

---

From this generating function, we can also deduce the recurrence relation $$a_{n,k} = 2 a_{n-1,k} + (k-2) a_{n-2,k} - (k-2) a_{n-3,k}$$ with initial conditions $a_{0,k}=1$, $a_{1,k}=1$, $a_{2,k}=2$. Here, $a_{n,k}$ denotes the number of closed walks of length $n$ in the $k$-vertex graph.

(The way to deduce such a recurrence relation is to multiply through by the denominator, then take the $x^n$ coefficient of both sides; the numerator $1-x-(k-2)x^2$ is irrelevant for this calculation, since its coefficient of $x^n$ is $0$ for large $n$. This is the reverse of how we usually go from recurrence relations to generating functions.)