Graph Theory, the amount of labeled trees Let us consider all labeled trees with nodes $\{1, 2, 3,...,n\}$. The question is how many of them contains the edge $\{1, 2\}$.
I would really appreciate an answer with some explanation.
 A: A tree on $n$ vertices has $n-1$ edges. There are $n(n-1)/2$ pairs of
distinct vertices. In a random tree the probability that a pair, say $\{1,2\}$ is an edge is therefore $2/n$. There are $n^{n-2}$ labelled
trees (Cayley). The number with $\{1,2\}$ as an edge is $2/n$ times
this, namely $2n^{n-3}$.
A: Combinatorially  we can  construct these  trees by  choosing a  set of
trees  to attach  at the  node labeled  one, and  another at  the node
labeled two.  These must together contain a total of $n-2$ nodes. Note
also that we must choose the labels  that go into the first set, where
the rest goes into  the second set. The two labeled  sets of trees are
then re-labeled with the chosen  labels respecting the ordering in the
source, which is the standard  construction. Therefore with $Q(z)$ the
EGF of sets of rooted labeled trees where
$$Q(z) = \sum_{n\ge 0} q_n \frac{z^n}{n!}$$
the desired quantity is given by
$$\sum_{k=0}^{n-2} {n-2\choose k} q_k q_{n-2-k}.$$
We use rooted trees  because we attach the root nodes  of the trees in
the two sets to the corresponding  node (labeled one or two). Here the
parameter $k$ gives  the number of nodes in the  set of trees attached
to node  one, with $n-2-k$  nodes in the  second set attached  to node
two.  
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 exponential
generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
This means that in the present case our answer is
$$(n-2)! [z^{n-2}] Q(z)^2.$$
Recall  the  combinatorial  species   of  labeled  rooted  trees  with
specification
$$\mathcal{T} = \mathcal{Z} \mathfrak{P}(\mathcal{T})$$
which gives for the corresponding EGF the functional equation
$$T(z) = z \exp T(z).$$
We thus have for sets of trees $\mathfrak{P}(\mathcal{T})$ that
$$Q(z) = \exp T(z) = \frac{1}{z} T(z).$$
It follows that
$$(n-2)! [z^{n-2}] Q(z)^2
= \frac{(n-2)!}{2\pi i} 
\int_{|z|=\epsilon} \frac{1}{z^{n-1}} Q(z)^2 \; dz
\\ = \frac{(n-2)!}{2\pi i} 
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z)^2 \; dz.$$
Now putting $T(z)=w$ the functional equation yields $w = z \exp(w)$ or
$z = w \exp(-w)$ and $dz =  (\exp(-w) - w \exp(-w)) \; dw.$ Here $z=0$
gives  $w=0$ and  since  $T(z) =  z  + \cdots$  the  image contour  of
$|z|=\epsilon$ in $w$  may be deformed to a circle  being traced once,
giving
$$\frac{(n-2)!}{2\pi i} 
\int_{|w|=\gamma} \frac{\exp((n+1)w)}{w^{n+1}} 
w^2 \exp(-w) (1-w) \; dw
\\ = \frac{(n-2)!}{2\pi i} 
\int_{|w|=\gamma} \frac{\exp(nw)}{w^{n-1}} 
(1-w) \; dw.$$
Extracting the residue we find
$$(n-2)! \times
\left( [w^{n-2}] \exp(nw) - [w^{n-3}] \exp(nw)\right)
\\ = (n-2)! \times
\left( \frac{n^{n-2}}{(n-2)!} - \frac{n^{n-3}}{(n-3)!}\right)
\\ = n n^{n-3} - (n-2) n^{n-3}
= 2 n^{n-3}.$$
This matches the result from the probabilistic argument that was first
to appear.
