Closed form of summation

Question

I was doing graph theory homework. I was counting the spaning trees of graph G. Such that G is two complete graphs on n vertices connected by two edges. I got to this expression: $$2n^{2\left(n-2\right)}+2\left(n^{\left(n-2\right)}\sum_{i=0}^{n-2}\binom{n-2}{i}\left(1+i\right)^{\left(i-1\right)}\left(n-i-1\right)^{\left(n-i-3\right)}\right)$$ I know that this expression gives the correct result, however, I was told by my teacher that it is possible to express that number in closed form e.g. without the summation. However, I have yet to find a solution.

Answer 1

Obviously, $2n^{2(n-2)}$ counts spanning trees which contain exactly one of the bridging edges. All that remains is to count trees which contain both.

Lets say that $a_1,a_2$ are vertices in the first $K_n$ and $b_1,b_2$ are in the second, and that the bridges $(a_1,b_1)$ and $(a_2,b_2)$. If you delete both of the bridges, then the edges remaining in one of the halves will be a spanning tree, and in the other half will be a two-component forest with the two bridging vertices in different components. Say the forest is in the $a$ half. Joining $a_1$ to $a_2$ makes this a spanning tree of $K_n$ containing $(a_1,a_2)$. You can show that the number of spanning trees of a $K_n$ containing a particular edge is $2n^{n-3}$; if $X$ is this number, then a double counting argument shows $X\cdot \binom{n}2=(n-1)\cdot n^{n-2}$; simply count the number of ordered pairs $(T,e)$, where $T$ is a spanning tree and $e$ is an edge of $T$, in two ways.

Putting this all together, the result is $$ 2n^{2(n-2)}+2\times n^{n-2}\times 2n^{n-3}=\boxed{(2n+4)n^{2n-5}.} $$

---

Okay, instead you just want a proof that $$ 2n^{n-3}=\sum_{i=0}^{n-2}\binom{n-2}i(i+1)^{i-1}(n-i-1)^{n-i-3} $$ Here is a combinatorial proof. Let $N=\{1,2,\dots,n\}$. As argued above, $2n^{n-3}$ counts the number of labeled trees with vertex set $N$ in which $1$ and $2$ are joined by an edge. On the other hand, the summation on the right counts the number of ways to,

• for some $0\le i\le n-2$,

• choose a subset $I\subset \{3,4,\dots,n\}$ with size $i$, [in $\binom{n-2}{i}$ ways]

• choose a tree $T_1$ with vertex set $\{1\}\cup I$, [in $(i+1)^{i-1}$ ways]

• choose a tree $T_2$ with vertex set $N\setminus(\{1\}\cup I)$ [in $(n-i-1)^{n-i-3}$ ways].

Here is the bijection between these two combinatorial structures. Given a tree $T$ on $N$ where $1$ is neighbors with $2$, delete the edge connecting $1$ and $2$. What remains is a graph with two connected components. Let $I$ be the rest of the vertices in the connected component containing $1$, let $T_1$ be the subgraph of $T$ on $I\cup \{1\}$, and let $T_2$ be the subgraph of $T$ on $N\setminus(I\cup \{1\})$.