Identity with binomial coefficients and k^k
Let's denote $T(x)=\sum_{n\geq 1}\frac{n^{n-1}x^n}{n!}$ the exponential generating function of labeled rooted trees, and $U(x)=\sum_{n\geq 1}\frac{n^{n-2}x^n}{n!}$ the corresponding function for unrooted trees. We will use the fact that $xU'=T$ and $xe^T=T$, both of which can be derived algebraically or combinatorially. Your identity follows from the relation $$2\left(T(x)-U(x)\right)=T^2$$ since the coefficient of $x^{k}$ on the left is $\frac{2k^{k-3}}{(k-2)!}$ and the corresponding coefficient on the right is $\sum_{i=1}^{k-1}\frac{i^{i-1}}{i!}\cdot\frac{(k-i)^{k-i-1}}{(k-i)!}$.
To get a quick proof of this notice that both sides only have terms of order $x^2$ or higher. Therefore it is enough to prove the derivative of this relation $$2T'-2U'=2TT'$$ $$\iff xT'-xU'=xTT'\iff xT'(1-T)=T\iff T'(1-T)=e^T$$ $$\iff 1=\frac{d}{dx}\left(\frac{T}{e^T}\right).$$
I hope it's clear from above that in principle all such identities follow from the basic relation $xe^T=T$ and all its derivatives. I know it's usually common to give references to books or surveys, but I really like the video lectures by Zagier available here, under the title "Partitions, Modular Forms, and Moduli Spaces" (these are based on a forthcoming paper by Dubrovin, Zagier and Yang). In a series of talks he presents how quasimodular forms appear in enumerative geometry. However in the first couple of lectures he focuses on what he calls "Lambert space" (nonstandard terminology from what I can tell, coming from the closely related Lambert function) which is essentially the space of series that are linear combinations of $T$ and its derivatives. He shows, for example, how generating functions of maps or Hurwitz numbers belong to this Lambert space.
Here are two proofs of your identity, which I have hinted at in my comments.
The identity
Let me first restate your identity with the letter $k$ renamed as $n$:
Theorem 1. Let $n\geq2$ be an integer. Then, $$ n^{n-3}=\dfrac{1}{2}\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i^{i-2}\left( n-i\right) ^{n-i-2}. $$
First proof: the Abel identity and its friends
The first proof of Theorem 1 will actually show a more general identity:
Theorem 2. Let $n$ be a nonnegative integer. In the polynomial ring $\mathbb{Z}\left[ x,y,z\right] $, we have $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}=\left( x+y\right) \left( x+y-nz\right) ^{n-1}. $$
Note that both sides of the equality in Theorem 2 are well-defined polynomials in $\mathbb{Z}\left[ x,y,z\right] $ (not just rational functions in $\mathbb{Q}\left( x,y,z\right) $): Indeed,
the only denominators that appear on the left hand side arise from the $\left( x-kz\right) ^{k-1}$ term for $k=0$ and from the $\left( y-\left( n-k\right) z\right) ^{n-k-1}$ term for $k=n$; but both of them are cancelled by the $xy$ factor appearing in each addend.
the only denominator that appears on the right hand side arises from the $\left( x+y-nz\right) ^{n-1}$ term for $n=0$; but this denominator is cancelled by the $x+y$ factor.
Theorem 2 is a well-known fact in umbral calculus: It says that the sequence of the Abel polynomials (the sequence $\left( p_{0},p_{1},p_{2} ,\ldots\right) $ whose $n$-th term is $p_{n}=x\left( x-nz\right) ^{n-1}$, where $x$ is considered an indeterminate and $z$ a constant) is of binomial type (i.e., it satisfies $p_{n}\left( x+y\right) =\sum\limits_{k=0}^{n}\dbinom {n}{k}p_{k}\left( x\right) p_{n-k}\left( y\right) $). As such, it is probably proven all across the literature. I also think that Theorem 2 is what the equation (2) in Victor J. W. Guo, Bijective proofs of Gould-Mohanty's and Raney-Mohanty's identities, arXiv:1005.4258v1 is supposed to be (I say "supposed" because equation (2) as it appears in Guo's preprint is false).
Let me derive Theorem 2 from an even better known identity, namely the Abel identity (appearing as equation (1) in the above-cited paper by Victor J. W. Guo):
Theorem 3. Let $n$ be a nonnegative integer. In the polynomial ring $\mathbb{Z}\left[ x,y,z\right] $, we have $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y+kz\right) ^{n-k}=\left( x+y\right) ^{n}. $$
As before, both sides of the equality in Theorem 3 are well-defined polynomials in $\mathbb{Z}\left[ x,y,z\right] $.
The most well-known particular case of Theorem 3 is probably the one obtained by substituting $-1$ for $z$:
Theorem 4. Let $n$ be a nonnegative integer. In the polynomial ring $\mathbb{Z}\left[ x,y\right] $, we have $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x+k\right) ^{k-1}\left( y-k\right) ^{n-k}=\left( x+y\right) ^{n}. $$
Theorem 4 appears in many places, e.g. (with a boring proof) in my solution to Problem 4 on the 6th QEDMO 2009 (scroll down to Theorem 4). Yes, I am that lazy at reference hunting. $\square$
I am going to reverse the cart and derive Theorem 1 back from Theorem 4. The first step is getting Theorem 3:
Proof of Theorem 3. Work in the field $\mathbb{Q}\left( x,y,z\right) $ of rational functions in $x,y,z$. Substitute $\dfrac{x}{z}$ and $\dfrac{y}{z}$ for $x$ and $y$ in Theorem 4. The result is $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}\dfrac{x}{z}\left( \dfrac{x}{z}-k\right) ^{k-1}\left( \dfrac{y}{z}+k\right) ^{n-k}=\left( \dfrac{x}{z}+\dfrac{y} {z}\right) ^{n}. $$ Multiplying this equality by $z^{n}$ and clearing denominators results in $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y+kz\right) ^{n-k}=\left( x+y\right) ^{n}. $$ Thus, Theorem 3 is proven. $\square$
Next, I shall derive Theorem 2 from Theorem 3:
Proof of Theorem 2. Substituting $y-nz$ for $y$ in Theorem 3 yields $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y-nz+kz\right) ^{n-k}=\left( x+y-nz\right) ^{n}. $$ Thus, \begin{align} \left( x+y-nz\right) ^{n} & =\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( \underbrace{y-nz+kz}_{=y-\left( n-k\right) z}\right) ^{n-k}\nonumber\\ \tag{1} & =\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k}. \label{pf.t2.1} \end{align} Multiplying this equality by $y$, we find \begin{align} y\left( x+y-nz\right) ^{n} & =y\sum\limits_{k=0}^{n}\dbinom{n}{k}x\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k}\nonumber\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\underbrace{\left( y-\left( n-k\right) z\right) ^{n-k}}_{=\left( y-\left( n-k\right) z\right) \left( y-\left( n-k\right) z\right) ^{n-k-1}}\nonumber\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) \left( y-\left( n-k\right) z\right) ^{n-k-1} \nonumber\\ \tag{2} & =\sum\limits_{k=0}^{n}\left( y-\left( n-k\right) z\right) \dbinom{n} {k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}. \label{pf.t2.2} \end{align}
On the other hand, substituting $y$ and $x$ for $x$ and $y$ in \eqref{pf.t2.1}, we obtain \begin{align*} \left( y+x-nz\right) ^{n} & =\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( y-kz\right) ^{k-1}\left( x-\left( n-k\right) z\right) ^{n-k}\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{n-k}y\left( y-\left( n-k\right) z\right) ^{n-k-1}\left( x-\left( n-\left( n-k\right) \right) z\right) ^{n-\left( n-k\right) } \end{align*} (here, we have substituted $n-k$ for $k$ in the sum). Since $y+x=x+y$, this rewrites as \begin{align*} & \left( x+y-nz\right) ^{n}\\ & =\sum\limits_{k=0}^{n}\underbrace{\dbinom{n}{n-k}}_{=\dbinom{n}{k}}y\left( y-\left( n-k\right) z\right) ^{n-k-1}\underbrace{\left( x-\left( n-\left( n-k\right) \right) z\right) ^{n-\left( n-k\right) } }_{\substack{=\left( x-kz\right) ^{k}\\=\left( x-kz\right) \left( x-kz\right) ^{k-1}}}\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( y-\left( n-k\right) z\right) ^{n-k-1}\left( x-kz\right) \left( x-kz\right) ^{k-1}\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( x-kz\right) \left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}. \end{align*} Multiplying this equality by $x$, we obtain \begin{align*} x\left( x+y-nz\right) ^{n} & =x\sum\limits_{k=0}^{n}\dbinom{n}{k}y\left( x-kz\right) \left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) \left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\sum\limits_{k=0}^{n}\left( x-kz\right) \dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}. \end{align*} Adding this equality to \eqref{pf.t2.2}, we find \begin{align*} & y\left( x+y-nz\right) ^{n}+x\left( x+y-nz\right) ^{n}\\ & =\sum\limits_{k=0}^{n}\left( y-\left( n-k\right) z\right) \dbinom{n} {k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & \ \ \ \ \ \ \ \ \ \ +\sum\limits_{k=0}^{n}\left( x-kz\right) \dbinom{n} {k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\sum\limits_{k=0}^{n}\underbrace{\left( \left( y-\left( n-k\right) z\right) +\left( x-kz\right) \right) }_{=x+y-nz}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\sum\limits_{k=0}^{n}\left( x+y-nz\right) \dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =\left( x+y-nz\right) \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}. \end{align*} Thus, \begin{align*} & \left( x+y-nz\right) \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}\\ & =y\left( x+y-nz\right) ^{n}+x\left( x+y-nz\right) ^{n}=\left( y+x\right) \left( x+y-nz\right) ^{n}\\ & =\left( x+y\right) \left( x+y-nz\right) ^{n}. \end{align*} Dividing this equality by $x+y-nz$, we obtain $$ \sum\limits_{k=0}^{n}\dbinom{n}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( n-k\right) z\right) ^{n-k-1}=\left( x+y\right) \left( x+y-nz\right) ^{n-1}. $$ This proves Theorem 2. $\square$
Finally, we can get Theorem 1:
First proof of Theorem 1. Theorem 2 (applied to $n-2$ instead of $n$) shows that in the polynomial ring $\mathbb{Z}\left[ x,y,z\right] $, we have \begin{align*} & \sum\limits_{k=0}^{n-2}\dbinom{n-2}{k}xy\left( x-kz\right) ^{k-1}\left( y-\left( \left( n-2\right) -k\right) z\right) ^{\left( n-2\right) -k-1}\\ & =\left( x+y\right) \left( x+y-\left( n-2\right) z\right) ^{n-3}. \end{align*} Substituting $1$, $1$ and $-1$ for $x$, $y$ and $z$ in this equality (and making the obvious simplifications), we find \begin{align*} & \sum\limits_{k=0}^{n-2}\dbinom{n-2}{k}\left( 1+k\right) ^{k-1}\left( 1+\left( \left( n-2\right) -k\right) \right) ^{\left( n-2\right) -k-1}\\ & =2\left( 2+\left( n-2\right) \right) ^{n-3}=2n^{n-3}. \end{align*} Hence, \begin{align*} 2n^{n-3} & =\sum\limits_{k=0}^{n-2}\dbinom{n-2}{k}\left( 1+k\right) ^{k-1}\left( 1+\left( \left( n-2\right) -k\right) \right) ^{\left( n-2\right) -k-1}\\ & =\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}\left( 1+\left( i-1\right) \right) ^{\left( i-1\right) -1}\left( 1+\left( \left( n-2\right) -\left( i-1\right) \right) \right) ^{\left( n-2\right) -\left( i-1\right) -1} \end{align*} (here, we have substituted $i-1$ for $k$ in the sum). After some trivial simplifications, this becomes $$ 2n^{n-3}=\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i^{i-2}\left( n-i\right) ^{n-i-2}. $$ Dividing this equality by $2$, we obtain the claim of Theorem 1. $\square$
Second proof: Cayley's formula and the symmetry of trees
Let me say right away that the above first proof of Theorem 1 is my favorite, since it shows various rather general combinatorial identities in cascade. In contrast, the following second proof is cute and memorable.
A tree shall here mean a simple undirected graph (i.e., a pair $\left( V,E\right) $ in which $V$ is a finite set and $E$ is a set of $2$-element subsets of $V$) that is connected and has no cycles. Of course, various other equivalent characterizations of trees exist. If $n\in\mathbb{N}$, then an $n$-tree means a tree whose vertex set is $\left\{ 1,2,\ldots,n\right\} $. Notice that there exist no $0$-trees, since a graph with no vertices is not connected. If $G=\left( V,E\right) $ is a simple undirected graph, then the edge set $E$ is denoted by $\operatorname*{E}\left( G\right) $.
The following theorem is one of the famous results of 19th century combinatorics -- the Cayley formula (actually discovered by Borchardt in 1860):
Theorem 5. Let $n$ be a positive integer. Then, the number of all $n$-trees is $n^{n-2}$.
The similarity of the $n^{n-2}$ term here with the powers in Theorem 1 suggests a relation, and such indeed exists. First, let me derive a corollary of Theorem 5:
Corollary 6. Let $n\geq2$ be an integer. Let $f$ be a $2$-element subset of $\left\{ 1,2,\ldots,n\right\} $. Then, the number of all $n$-trees $T$ such that $f\in\operatorname*{E}\left( T\right) $ is $2n^{n-3}$.
Proof of Corollary 6. It is well-known that the number of edges in a tree is always its number of vertices minus $1$. Thus, a tree with $n$ vertices must have exactly $n-1$ edges. In other words, any $n$-tree must have exactly $n-1$ edges.
Let $F$ be the set of all $2$-element subsets of $\left\{ 1,2,\ldots ,n\right\} $. Then, for each $n$-tree $T$, we have $\operatorname*{E}\left( T\right) \subseteq F$ (that is, the edges of $T$ are elements of $F$). Also, $f$ is a $2$-element subset of $\left\{ 1,2,\ldots,n\right\} $ and thus belongs to $F$. Also, clearly, $\left\vert F\right\vert =\dbinom{n}{2} =\dfrac{n\left( n-1\right) }{2}$.
Now, we claim that any $e\in F$ satisfies \begin{align} \left( \text{the number of all }n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right) \nonumber\\ \tag{3} =\left( \text{the number of all }n\text{-trees }T\text{ such that } e\in\operatorname*{E}\left( T\right) \right) . \label{pf.c6.1} \end{align}
[Proof of \eqref{pf.c6.1}: Let $e\in F$. Thus, $e$ is a $2$-element subset of $\left\{ 1,2,\ldots,n\right\} $. In other words, $e=\left\{ x,y\right\} $ for two distinct elements $x$ and $y$ of $\left\{ 1,2,\ldots,n\right\} $. Consider these $x$ and $y$.
The elements $x$ and $y$ of $\left\{ 1,2,\ldots,n\right\} $ are distinct. Thus, there exists some permutation $\sigma$ of $\left\{ 1,2,\ldots ,n\right\} $ such that $\sigma\left( 1\right) =x$ and $\sigma\left( 2\right) =y$. (For example, one can find such a permutation $\sigma$ by setting its first two values $\sigma\left( 1\right) $ and $\sigma\left( 2\right) $ to be $x$ and $y$, and setting all its remaining $n-2$ values to be the remaining $n-2$ elements of $\left\{ 1,2,\ldots,n\right\} $ in any order.) Consider such a $\sigma$.
Recall that any permutation $\omega$ of $\left\{ 1,2,\ldots,n\right\} $ also induces a permutation of the set $F$ of all $2$-element subsets of $\left\{ 1,2,\ldots,n\right\} $ (namely, it sends each $g\in F$ to $\omega\left( g \right) =\left\{ \omega\left( u\right) \ \mid\ u\in g \right\} $). In particular, $\sigma$ induces a permutation of the set $F$. This permutation satisfies $\sigma\left( \left\{ 1,2\right\} \right) =\left\{ \underbrace{\sigma\left( 1\right) }_{=x},\underbrace{\sigma\left( 2\right) }_{=y}\right\} =\left\{ x,y\right\} =e$.
If $T$ is an $n$-tree, and if $\omega$ is a permutation of $\left\{ 1,2,\ldots,n\right\} $, then $\omega\left( T\right) $ shall denote the $n$-tree whose edges are the images of the edges of $T$ under $\omega$ (that is, $\operatorname*{E}\left( \omega\left( T\right) \right) =\left\{ \omega\left( e\right) \ \mid\ e\in\operatorname*{E}\left( T\right) \right\} $). It is easy to see that this $\omega\left( T\right) $ is indeed an $n$-tree (indeed, it is just the $n$-tree $T$ with its vertices relabelled by the map $\omega$). Hence, the map $$ \left\{ n\text{-trees}\right\} \rightarrow\left\{ n\text{-trees}\right\} ,\ T\mapsto\sigma\left( T\right) $$ is well-defined. Moreover, this map is a bijection (indeed, the map $\left\{ n\text{-trees}\right\} \rightarrow\left\{ n\text{-trees}\right\} ,\ T\mapsto\sigma^{-1}\left( T\right) $ is easily seen to be inverse to it). This bijection restricts to a bijection \begin{align*} \left\{ n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right\} & \rightarrow\left\{ n\text{-trees }T\text{ such that }e\in\operatorname*{E}\left( T\right) \right\} ,\\ T & \mapsto\sigma\left( T\right) \end{align*} (since $\sigma\left( \left\{ 1,2\right\} \right) =e$). Hence, the sets $\left\{ n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right\} $ and $\left\{ n\text{-trees }T\text{ such that }e\in\operatorname*{E}\left( T\right) \right\} $ are in bijection. Thus, these two sets have the same size. In other words, \eqref{pf.c6.1} holds.]
Now, \begin{align*} & \left( \text{the number of all pairs }\left( T,e\right) \text{ where }T\text{ is an }n\text{-tree and }e\in\operatorname*{E}\left( T\right) \right) \\ & =\sum\limits_{T\text{ is an }n\text{-tree}}\underbrace{\left( \text{the number of all }e\in\operatorname*{E}\left( T\right) \right) }_{\substack{=\left\vert \operatorname*{E}\left( T\right) \right\vert =\left( \text{the number of all edges of }T\right) =n-1\\\text{(since any }n\text{-tree must have exactly }n-1\text{ edges)}}}\\ & =\sum\limits_{T\text{ is an }n\text{-tree}}\left( n-1\right) =\left( n-1\right) \cdot\underbrace{\left( \text{the number of all }n\text{-trees}\right) }_{\substack{=n^{n-2}\\\text{(by Theorem 5)}}}\\ & =\left( n-1\right) \cdot n^{n-2}. \end{align*} Hence, \begin{align*} & \left( n-1\right) \cdot n^{n-2}\\ & =\left( \text{the number of all pairs }\left( T,e\right) \text{ where }T\text{ is an }n\text{-tree and }e\in\operatorname*{E}\left( T\right) \right) \\ & =\sum\limits_{e\in F}\underbrace{\left( \text{the number of all }n\text{-trees }T\text{ such that }e\in\operatorname*{E}\left( T\right) \right) }_{\substack{=\left( \text{the number of all }n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right) \\\text{(by \eqref{pf.c6.1})}}}\\ & \ \ \ \ \ \ \ \ \ \ \left( \text{since }\operatorname*{E}\left( T\right) \subseteq F\text{ for each }n\text{-tree }T\right) \\ & =\sum\limits_{e\in F}\left( \text{the number of all }n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) \right) \\ & =\underbrace{\left\vert F\right\vert }_{=\dfrac{n\left( n-1\right) }{2} } \cdot \underbrace{\left( \text{the number of all }n\text{-trees }T\text{ such that }\left\{ 1,2\right\} \in \operatorname*{E}\left( T\right) \right) }_{\substack{=\left( \text{the number of all }n\text{-trees }T\text{ such that }f\in\operatorname*{E}\left( T\right) \right) \\\text{(by \eqref{pf.c6.1}, applied to }e=f\text{)}}}\\ & =\dfrac{n\left( n-1\right) }{2}\cdot\left( \text{the number of all }n\text{-trees }T\text{ such that }f\in\operatorname*{E}\left( T\right) \right) . \end{align*} Solving this equality for $\left( \text{the number of all }n\text{-trees }T\text{ such that }f\in\operatorname*{E}\left( T\right) \right) $, we obtain \begin{align*} \left( \text{the number of all }n\text{-trees }T\text{ such that } f\in\operatorname*{E}\left( T\right) \right) & =\left( n-1\right) \cdot n^{n-2}/\dfrac{n\left( n-1\right) }{2}\\ & =2n^{n-3}. \end{align*} This proves Corollary 6. $\square$
Here is another trivial corollary of Theorem 5:
Corollary 7. Let $S$ be a finite nonempty set. Then, the number of all trees with vertex set $S$ is $\left\vert S\right\vert ^{\left\vert S\right\vert -2}$.
Proof of Corollary 7. Let $n=\left\vert S\right\vert $. Then, there exists a bijection $\left\{ 1,2,\ldots,n\right\} \rightarrow S$. We can use this bijection to transform any $n$-tree into a tree with vertex set $S$ (by relabelling its vertices) and vice versa. Hence, the number of all trees with vertex set $S$ equals the number of all $n$-trees. But the latter number is $n^{n-2}$ (by Theorem 5). Hence, the former number is also $n^{n-2}$. In other words, the number of all trees with vertex set $S$ is $n^{n-2}=\left\vert S\right\vert ^{\left\vert S\right\vert -2}$ (since $n=\left\vert S\right\vert $). Corollary 7 is proven. $\square$
Now, we can finally reprove Theorem 1:
Second proof of Theorem 1. Corollary 6 (applied to $f=\left\{ 1,2\right\} $) shows that the number of all $n$-trees $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $ is $2n^{n-3}$.
Now, let me show a different way to compute this number.
Indeed, if we remove the edge $\left\{ 1,2\right\} $ from an $n$-tree $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $, then the remaining graph splits into two connected components, one of which contains the vertex $1$ while the other contains the vertex $2$. Both connected components are trees; we denote them by $A_{T}$ and $B_{T}$, respectively (so that $1$ is a vertex of $A_{T}$ and $2$ is a vertex of $B_{T}$). Let $\mathcal{A}_{T}$ be the vertex set of the tree $A_{T}$, and let $\mathcal{B}_{T}$ be the vertex set of the tree $B_{T}$. Then, $\mathcal{A} _{T}$ and $\mathcal{B}_{T}$ are two disjoint subsets of $\left\{ 1,2,\ldots,n\right\} $ whose union is $\left\{ 1,2,\ldots,n\right\} $; thus, $\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A} _{T}$. Note that $1\in\mathcal{A}_{T}$ (since $1$ is a vertex of $A_{T}$) and $2\in\mathcal{B}_{T}$ (since $2$ is a vertex of $B_{T}$), thus $2\in \mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}$, thus $2\notin\mathcal{A}_{T}$.
Obviously, an $n$-tree $T$ satisfying $\left\{ 1,2\right\} \in \operatorname*{E}\left( T\right) $ is uniquely determined by the two trees $A_{T}$ and $B_{T}$. Thus, any $n$-tree $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $ can be constructed by the following procedure:
First, we decide how many elements the set $\mathcal{A}_{T}$ will have (i.e., how many vertices $A_{T}$ will have). The number of elements of $\mathcal{A}_{T}$ has to be an integer from $1$ to $n-1$ (in fact, it cannot be $0$ (since we must have $1\in\mathcal{A}_{T}$); but it cannot be $n$ either (since we must have $2\notin\mathcal{A}_{T}$)). We choose one such integer, and denote it by $i$. We thus want the set $\mathcal{A}_{T}$ to have $i$ elements.
Then, we choose the set $\mathcal{A}_{T}$ itself (i.e., we decide which vertices $A_{T}$ will have). We already know that this set will have $i$ elements, and we know that $1$ will be one of them (since $1\in\mathcal{A} _{T}$) but $2$ will be not (since $2\notin\mathcal{A}_{T}$); thus, we are left to choose the remaining $i-1$ elements of $\mathcal{A}_{T}$ freely among the $n-2$ numbers $3,4,\ldots,n$. There are $\dbinom{n-2}{i-1}$ ways to make this choice.
Having chosen the set $\mathcal{A}_{T}$, we immediately know the set $\mathcal{B}_{T}$: namely, $\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}$ (there are no choices to make here). Notice that $\left\vert \mathcal{A}_{T}\right\vert =i$ (since the set $\mathcal{A}_{T}$ has $i$ elements), and from $\mathcal{B}_{T}=\left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}$ we obtain $\left\vert \mathcal{B}_{T}\right\vert =\left\vert \left\{ 1,2,\ldots,n\right\} \setminus\mathcal{A}_{T}\right\vert =\underbrace{\left\vert \left\{ 1,2,\ldots,n\right\} \right\vert } _{=n}-\underbrace{\left\vert \mathcal{A}_{T}\right\vert }_{=i}=n-i$. Note that both sets $\mathcal{A}_{T}$ and $\mathcal{B}_{T}$ are nonempty (since $1\in\mathcal{A}_{T}$ but $2\in\mathcal{B}_{T}$ (since $2\notin\mathcal{A} _{T}$)).
Now, we choose the tree $A_{T}$. This tree has to be a tree with vertex set $\mathcal{A}_{T}$; the number of all such trees is $\left\vert \mathcal{A} _{T}\right\vert ^{\left\vert \mathcal{A}_{T}\right\vert -2}$ (by Corollary 7, applied to $S=\mathcal{A}_{T}$). In other words, the number of all such trees is $i^{i-2}$ (since $\left\vert \mathcal{A}_{T}\right\vert =i$). Thus, there are $i^{i-2}$ ways to choose $A_{T}$.
Now, we choose the tree $B_{T}$. This tree has to be a tree with vertex set $\mathcal{B}_{T}$; the number of all such trees is $\left\vert \mathcal{B} _{T}\right\vert ^{\left\vert \mathcal{B}_{T}\right\vert -2}$ (by Corollary 7, applied to $S=\mathcal{B}_{T}$). In other words, the number of all such trees is $\left( n-i\right) ^{n-i-2}$ (since $\left\vert \mathcal{B} _{T}\right\vert =n-i$). Thus, there are $\left( n-i\right) ^{n-i-2}$ ways to choose $B_{T}$.
Finally, we assemble the $n$-tree $T$ from $A_{T}$ and $B_{T}$ by adding the edge $\left\{ 1,2\right\} $.
This procedure clearly yields any $n$-tree $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $ in a unique way. Thus, the number of all $n$-trees $T$ satisfying $\left\{ 1,2\right\} \in\operatorname*{E}\left( T\right) $ is $\sum\limits_{i=1}^{n-1}\dbinom{n-2} {i-1}i^{i-2}\left( n-i\right) ^{n-i-2}$ (because this is how many ways we have to make choices in the above procedure). Comparing this with the fact that this number is $2n^{n-3}$ (as shown above), we conclude that $$ 2n^{n-3}=\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i^{i-2}\left( n-i\right) ^{n-i-2}. $$ Dividing this equality by $2$, we obtain the claim of Theorem 1. $\square$
In my (first research) paper, A note on evaluation of Abel's sums, (that appeared second, in 1979) I described another way to evaluate Abel's sum of the form $$A_n(x,y;p,q)=\sum_{k=0}^n {{n} \choose {k}}(k+x)^{k+p}(n-k+y)^{n-k+q},$$ via (simpler) auxiliary sums defined by $$F_n(x,y;p,q)=\sum_{k=0}^n {{n} \choose {k}}(-1)^k (k+x)^{p}(n-k+y)^{q}.$$ The $F_n$ functions have simple evaluations in terms of difference operators. I was inspired by Riordan's book Combinatorial Identities and later corresponded with Riordan, and met him in 78.