Show that $ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $

Show that $$ \sum_{r=1}^{n-1}\binom{n-2}{r-1}r^{r-1}(n-r)^{n-r-2}= n^{n-2} $$

I don't know whether such identity already exists, or has been posted here before. I discovered this identity while solving a problem but nor able to prove. And if the problem is correct then this must have to be true. Its coming out to be true for $n$ upto $10$. So please prove or disprove.( I am quite sure it is true)

Solution 1:

Count how many are there triples $(T,e,x)$ where $T$ is a tree on $\{1,2,\dots,n\}$, $e$ is an edge of $T$ and $x$ is a vertex of $T$.

Way 1: $n^{n-2} n (n-1)$ by Cayley's formula.

Way 2:

The edge $e$ splits the tree into two parts, left $L$ and right $R$. We will say $R$ is the one that contains $x$.

First, select two endpoints of $e$: $a \in L$ and $b \in R$, this can be done in $n(n-1)$ ways.

Let $r$ be the cardinality of $R$. Select which of $r$ numbers in $\{1,2,\dots,n\}$ belong to $R$. We already committed to $a \in L$ and $b \in R$; this means $n-2 \choose r-1$.

There are $r$ ways to choose $x$, $r^{r-2}$ ways to choose $R$ and $(n-r)^{n-r-2}$ ways to choose $L$.

Therefore

$n^{n-2} n(n-1) = n(n-1) \sum_{r=1}^{n-1} {n-2 \choose r-1} r \cdot r^{r-2} (n-r)^{n-r-2}$ QED

Solution 2:

Suppose we are trying to show that $$\sum_{r=1}^{n-1} {n-2\choose r-1} r^{r-1} (n-r)^{n-r-2} = n^{n-2}$$ where $n\ge 2.$

Looking to the combinatorial proof for inspiration we present the labelled tree function $T(z)$ with functional equation $$\mathcal{T} = \mathcal{Z} \times \mathfrak{P}(\mathcal{T}) \quad\text{or}\quad T(z) = z \exp T(z)$$

which counts the number of labelled rooted trees on $n$ nodes so that $$n! [z^n] T(z) = n^{n-1}.$$

We now re-write the equation to better match the tree function. Start with $$\sum_{r=0}^{n-2} {n-2\choose r} (r+1)^r (n-r-1)^{n-r-3} = n^{n-2}$$ and continue with $$\sum_{r=0}^{n} {n\choose r} (r+1)^r (n+1-r)^{n-r-1} = (n+2)^n.$$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

In the present case we have $$A(z) = T'(z)$$ by inspection. Note also that $$T(z) = \sum_{n\ge 1} n\times n^{n-2} \frac{z^n}{n!} = \sum_{n\ge 1} n^{n-2} \frac{z^n}{(n-1)!} = z \sum_{n\ge 1} n^{n-2} \frac{z^{n-1}}{(n-1)!}.$$

It follows that $$B(z) = \sum_{n\ge 0} (n+1)^{n-1} \frac{z^{n}}{n!} = \frac{1}{z} T(z).$$

We thus obtain that $$A(z) B(z) = \frac{1}{z} T(z) T'(z).$$

Observe that when we differentiate the functional equation we obtain $$T'(z) = \exp T(z) + z \exp T(z) \times T'(z) = \frac{1}{z} T(z) + T(z) \times T'(z)$$ and hence $$T'(z) = \frac{1}{z} \frac{T(z)}{1-T(z)}.$$

This yields $$A(z) B(z) = \frac{1}{z^2} \frac{T^2(z)}{1-T(z)}.$$

Now to extract coefficients from this we have $$n! [z^n] A(z) B(z) = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{z^2} \frac{T^2(z)}{1-T(z)} \; dz \\ = \frac{n!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+3}} \frac{T^2(z)}{1-T(z)} \; dz.$$

Using a type of Lagrange inversion and putting $w=T(z)$ we get from the functional equation $w = z \exp w$ or $z = w \exp(-w)$ and hence $dz = (\exp(-w) - w\exp(-w)) \; dw$ or $dz = \exp(-w) ( 1 - w ) \; dw,$ yielding for the integral

$$\frac{n!}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(w(n+3))}{w^{n+3}} \frac{w^2}{1-w} \exp(-w)(1-w) \; dw \\ = \frac{n!}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(w(n+2))}{w^{n+1}} \; dw.$$

Extracting the residue we find $$n! \times \frac{(n+2)^{n}}{n!} = (n+2)^n$$

as claimed, QED.