# Spanning trees in a ladder graph

Let $L_n$ be the ladder graph formed from two $n$-vertex paths by joining corresponding vertices. For example $L_4$ is the following

I have to find a recurrence $<t>$ where $t_n$ is the number of spanning trees on $L_n$. Of course if we take a spanning tree on $L_{n-1}$ and attach one of the following

it remains a tree. So we should have a $3t_{n-1}$, but I don't know how to count the number of trees that end with

-
According to the definition in the text, the image seems to show $L_4$? –  joriki Oct 3 '11 at 22:22
you're right, i'll fix it –  Alex M Oct 3 '11 at 22:25

Let the vertices along the top of $L_{n+1}$ be $u_1,\dots,u_{n+1}$ and those along the bottom be $v_1,\dots,v_{n+1}$. There’s a bijection between spanning trees of $L_{n+1}$ that contain the edges $\{u_n,u_{n+1}\}$, $\{u_{n+1},v_{n+1}\}$, and $\{v_n,v_{n+1}\}$ and spanning trees of $L_n$ that contain the edge $\{u_n,v_n\}$. Let $s_n$ be the number of spanning trees of $L_n$ that include $\{u_n,v_n\}$. Then $t_{n+1} = 3t_n + s_n$, and $s_{n+1} =$ ?

Added: I now see how to get a recurrence for the $t_n$ directly, without using an auxiliary sequence. Start with any spanning tree of $L_n$. As you said, you can always add one of the three figures in your second picture to it to get a spanning tree of $L_{n+1}$, and that accounts for $3t_n$ spanning trees. You can add your last picture to it if and only if it contains $\{u_n,v_n\}$, in which case you must erase $\{u_n,v_n\}$; that accounts for another $t_n-k$ spanning trees, where $k$ is the number of spanning trees of $L_n$ that don’t contain $\{u_n,v_n\}$. So when does a spanning tree $T$ of $L_n$ not contain $\{u_n,v_n\}$? Exactly when $T$ does contain both $\{u_{n-1},u_n\}$ and $\{v_{n-1},v_n\}$, which is exactly when the part of $T$ in $L_{n-1}$ is a spanning tree of $L_{n-1}$. In other words, there are $t_{n-1}$ spanning trees of $L_n$ that include the edge $\{u_n,v_n\}$: $k=t_{n-1}$, and $L_{n+1}$ has $t_n-t_{n-1}$ spanning trees that include your last picture. This makes a grand total of $$t_{n+1}=3t_n+(t_n-t_{n-1})=4t_n-t_{n-1}$$ spanning trees of $L_{n+1}$.

But I found the analysis much easier with the auxiliary sequence. As long as your recurrences are linear, it’s not too hard to combine them by very elementary means. For instance, suppose that you have this system: $$\begin{cases} t_{n+1}=at_n+bs_n\tag{1}\\ s_{n+1}=ct_n+ds_n \end{cases}$$

Then $$\begin{cases} dt_{n+1}=adt_n+bds_n\\ bs_{n+1}=bct_n+bds_n, \end{cases}$$

so $dt_{n+1}-bs_{n+1}=(ad-bc)t_n$. As long as $ad-bc\ne 0$, you can solve this for $s_{n+1}$ to get $$s_{n+1}=\frac{d}{b}t_{n+1}-\frac{ad-bc}{b}t_n,$$ or, equivalently, $$s_n=\frac{d}{b}t_n-\frac{ad-bc}{b}t_{n-1}.$$ Substitute this into the first equation of $(1)$ to get $$t_{n+1}=(a+d)t_n+(ad-bc)t_{n-1}.$$

-
Interesting -- I guess those are two different ways of describing the same elephant. By the way, I think it should be $u_n$ in the first line? –  joriki Oct 3 '11 at 23:01
@joriki: Sure looks like it. (It was actually supposed to be $v_{n+1}$: I was thinking of $L_{n+1}$, not $L_n$.) –  Brian M. Scott Oct 3 '11 at 23:08
From the other answer it seems that $s_{n+1}=s_n+2t_n$ but I can't understand why, could you explain this, please? In addiction I'd like to have a recurrence that I can solve with standards methods. I don't see how to solve $t_n$ with that recurrence. –  Alex M Oct 4 '11 at 5:47
@Alex: You get a spanning tree in $L_{n+1}$ that includes $\{u_{n+1},v_{n+1}\}$ when you add either of the first two pictures in your second set to a spanning tree of $L_n$; that’s $2t_n$ spanning trees. The other $s_n$ come when you add your last picture to one of the $s_n$ spanning trees of $L_n$ that contain $\{u_n,v_n\}$ and then delete $\{u_n,v_n\}$. So now you have $t_{n+1}=3t_n+s_n$ and $s_{n+1}=2t_n+s_n$. Subtract the second from the first to get $t_{n+1}-s_{n+1}=t_n$. This implies that $t_n-s_n=t_{n-1}$, so $s_n=t_n-t_{n-1}$. Substitute this into the first recurrence to get ... –  Brian M. Scott Oct 4 '11 at 7:18
@Alex: ... $t_{n+1}=3t_n+s_n=4t_n-t_{n-1}$. –  Brian M. Scott Oct 4 '11 at 7:20

I don't know whether this is the simplest solution, but this is how I'd go about it:

Let $s_n$ be the number of spanning subgraphs of $L_n$ that have two connected components each containing one of the two right-most vertices; let's call such subgraphs $2$-graphs for short. Then we can write down a joint recurrence for $s_n$ and $t_n$: To each $2$-graph of $L_n$ we can add two horizontal edges to extend it to a $2$-graph of $L_{n+1}$, and we can add the three-edge figure in your last image to extend it to a spanning tree of $L_{n+1}$. To each spanning tree of $L_n$, we can add one of two horizontal edges to extend it to a $2$-graph of $L_{n+1}$, and we can add one of the three figures in your second image to extend it to a spanning tree of $L_{n+1}$. Thus we have the joint recurrence

$$\pmatrix{s_{n+1}\\t_{n+1}}=\pmatrix{1&2\\1&3}\pmatrix{s_n\\t_n}\;.$$

[Edit:]

I see you had a question in a comment about how to solve this recurrence. Brian showed how to do this by converting it into a second-order recurrence for $t$. That's analogous to converting a system of two linear first-order differential equations into one second-order equation. As for systems of linear differential equations, you can also solve the system directly by diagonalizing it. The eigenvalues of $\pmatrix{1&2\\1&3}$ coincide with the characteristic values of Brian's second-order recurrence. Using the eigensystem of the matrix, you can transform to

$$\pmatrix{s_n\\t_n}=\pmatrix{\sqrt3-1&-\sqrt3-1\\1&1}\pmatrix{u_n\\v_n}$$

with $u_n$ and $v_n$ satisfying the recurrences $u_{n+1}=(2+\sqrt3)u_n$ and $v_{n+1}=(2-\sqrt3)v_n$, respectively. The initial values are $s_1=t_1=1$, so $u_1=(2+\sqrt3)/(2\sqrt3)$ and $v_1=-(2-\sqrt3)/(2\sqrt3)$. The solutions are $u_n=(2+\sqrt3)^n/(2\sqrt3)$ and $v_n=-(2-\sqrt3)^n/(2\sqrt3)$, so

$$t_n=\frac{(2+\sqrt3)^n-(2-\sqrt3)^n}{2\sqrt3}=2^{n-1}\sum_{\scriptstyle k=0}^{\lfloor\frac{n-1}2\rfloor}\binom n{2k+1}\left(\frac34\right)^k\;.$$

-

A similar case was studied by Ares Ribo in her doctoral thesis. Here, spanning trees of ladder graphs with diagonals were counted. The ideas can be easily modified for the non-diagonal case. The approach boils down to what joriki was computing. In particular, the values for $t_n$ can be described by the largest Eigenvalue of the matrix $\begin{pmatrix} 1 & 2 \\ 1 & 3 \end{pmatrix}$. The approach can be generalized to count spanning trees on grids, cylinders and the twisted cylinder. This method is known as transfer-matrix method.

-