Let $G$ be a simple graph with $k$ connected components, which have $a_{1}, \ldots, a_{k}$ vertices, respectively. Determine the number of ways to add $k-1$ edges to $G$ to form a connected graph, in terms of the numbers $a_{i}$.
The answer is

$$
a_{1} \ldots a_{k}\left(a_{1}+\cdots+a_{k}\right)^{k-2}
$$

which generalizes Cayley's formula!

We will show that

$$
f\left(a_{1}, \ldots, a_{k}\right)=k !\left(a_{1} \ldots a_{k}\right)\left(a_{1}+\cdots+a_{k}\right)^{k-2}
$$

counts the number of ways to pick $k-1$ edges, in order. The proof is by induction on $k$, with $k=1$ being clear. If we add an edge between the first and second
connected components, there are $a_{1} a_{2}$ ways to do so, and the number of ways to finish is $f\left(a_{1}+a_{2}, a_{3} \ldots, a_{k}\right)$. So

$$
\begin{aligned}
f\left(a_{1}, \ldots, a_{k}\right) & =\sum_{1 \leq i<j \leq k} a_{i} a_{j} f(a_{i}+a_{j}, \underbrace{a_{1}, \ldots, a_{k}}_{\text {missing } a_{i} \text { and } a_{j}}) \\
& =(k-1) ! \sum_{1 \leq i<j \leq k}\left(a_{i}+a_{j}\right)\left(a_{1} \ldots a_{k}\right)\left(a_{1}+\cdots+a_{k}\right)^{k-2} \\
& =(k-1) !\left(a_{1} \ldots a_{k}\right)\left(a_{1}+\cdots+a_{k}\right)^{k-2} \sum_{1 \leq i<j \leq k}\left(a_{i}+a_{j}\right) \\
& =k !\left(a_{1} \ldots a_{k}\right)\left(a_{1}+\cdots+a_{k}\right)^{k-1} .
\end{aligned}
$$