Graph Theory, the amount of labeled trees

Question

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.

Answer 1

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

Answer 2

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.