The given identity:
$$2(n-1)n^{n-2} = \sum^{n-1}_{i=1}\binom nii^{i-1}(n-i)^{n-i-1}$$
It seems to be a binomial coefficient problem, but I have tried many ways. There are no more ideas how to prove it.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Does this answer your question? Bijective proof of an Abel-Hurwitz-type identity $\endgroup$– Sam HopkinsCommented Oct 25, 2021 at 21:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
$2(n-1)n^{n-2}$ counts the number of ways to choose a tree on $[n]:=\{1,\dots,n\}$, then select one of the edges, then to choose an orientation for that edge. Say the selected, oriented edge is $v\to w$. Deleting that edge leaves an ordered pair of rooted trees, where $v$ is the root of the first tree and $w$ is the root of the second. On the other hand, we can also a pair of rooted trees by selecting a nonempty, nonfull subset $K$ of $\{1,\dots,n\}$ with cardinality $k$, then choosing a rooted tree for $K$, then choosing a rooted tree for $[n]\setminus K$. This can all be done in $\binom{n}k k^{k-1}(n-k)^{n-k-1}$ ways.
