# Combinatorial Sum equals $2n^{n-3}$

For $$n \ge 3$$, prove or disprove that

$$$$\sum_{m = 1}^{n-1} {{n-2}\choose{m-1}} m^{m-2} (n-m)^{n-m-2} = 2n^{n-3}.$$$$

I was trying to do this problem, and I managed to reduce it to the above identity but I couldn't prove it.

• This is Theorem 1 in mathoverflow.net/questions/273399/… . Note that my second proof derives it from the problem you were trying to solve. Commented Oct 18, 2018 at 3:15
• This looks like "Abel's identity". Commented Oct 18, 2018 at 3:55
• This question appeared at the following MSE link, with two answers. Commented Oct 18, 2018 at 12:31
• Thanks everyone, those links with all the different approaches are very helpful! Commented Oct 18, 2018 at 23:10

You can solve the original question (number of spanning trees of $$K_{n}$$ with an edge removed) with the Matrix-Tree Theorem. By symmetry, we can assume the edge removed is between first and second vertex. The number you want to calculate is the $$(n-1)\times(n-1)$$ -determinant (take the $$(1,1)$$-cofactor of the Laplacian matrix of the graph)

$$\left| \begin{matrix} n-2 & -1 & -1 & \cdots & -1\\ -1 & n-1 & -1 & \cdots & -1\\ -1 & -1 & n-1 & \cdots & -1\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ -1 & -1 & -1 & \cdots & n-1\\ \end{matrix}\right|$$

Now, subtract the second row once away from the first (this won't change the determinant) and then the second column from the first and you get

$$\left| \begin{array}{c:c:ccc} 2n-1 & -n & 0 & \cdots & 0\\ \hdashline -n & n-1 & -1 & \cdots & -1\\ \hdashline 0 & -1 & n-1 & \cdots & -1\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & -1 & -1 & \cdots & n-1\\ \end{array}\right|$$

Notice those lower blocks, they are $$mI_s-J_s$$ where $$J$$ is a matrix full of $$1$$'s, for $$m=n$$ and $$s=n-2, n-3$$.

Here's a lemma: $$\det(mI_s-J_s) = m^{s-1}(m-s)$$ It can be proved for example by showing the eigenvalues are $$m$$ with multiplicity $$s-1$$ the eigenvectors have the pattern $$(1,0\dots,0-1,0\dots0)$$, and then the eigenvalue $$m-s$$ with the eigenvector of all $$1$$'s.

Now, let's calculate the wanted determinant by going along the first row:

$$(2n-1)\det(nI_{n-2}-J_{n-2}) + (-1)(-n)\left|\begin{array}{} -n&-1&-1&\cdots&-1\\0&n-1&-1&\cdots&-1\\0&-1&n-1&\cdots&-1\\\vdots&&\vdots&\ddots&\vdots\\0&-1&-1&\cdots&n-1\end{array}\right|$$

\begin{align*}=&(2n-1)\det(nI_{n-2}-J_{n-2}) + (-1)(-n)(-n)\det(nI_{n-3}-J_{n-3})\\ =& (2n-1)n^{n-3}(2) - n^2n^{n-4}(3)\\ =& (4n-2)n^{n-3} - (3n)n^{n-3}\\ =& (n-2)n^{n-3} \end{align*}

• Thanks for the detailed answer! Ideally, I was looking for a solution without using graph theory related theorems, since the problem asks for a proof with "Cayley's theorem" which is a special case of "Matrix-Tree Theorem". Commented Oct 18, 2018 at 23:17