2
$\begingroup$

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

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

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

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

1 Answer 1

3
$\begingroup$

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*}$$

$\endgroup$
1
  • $\begingroup$ 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". $\endgroup$ Commented Oct 18, 2018 at 23:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .