combinatoricsgraph theorytrees
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 $\langle t\rangle$ where $t_n$ is the number of spanning trees on $L_n$.
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 other graphs.
You can think of each connected component as a graph by itself and talk about its associated spanning trees.
What it is saying is that you build a spanning forest by choosing a spanning tree from each connected component, therefore the number of trees in a spanning forest is the same as the number of connected components.
So we have to count all the ways to delete two edges such that remaining graph is connected. If we remove $a_{k + 1} b_{k + 1}$, then we can also remove any other edge. This gives us $2n$ spanning trees.
So now assume that we do not remove $a_{k + 1} b_{k + 1}$. Instead we have to remove two other edges. Notice that if we remove one edge to the left of $a_{k + 1}b_{k + 1}$ and one edge to the right, our graph will still be connected. Otherwise it will be disconnected. This gives us $n \cdot n$ spanning trees.
In total we have $2n + n^2$.
Best Answer
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}.$$