TAOCP 2.3.4.4 Exercise 12
By exercise 2.
Section 2.3.4.4: Enumeration of Trees
Exercise 12. [**] [M20] Find the number of labeled oriented trees with $n$ vertices by using determinants and the result of exercise 2.3.4.2-19. (See also exercise 1.2.3-36.)
Verified: no
Solve time: 30s
By exercise 2.3.4.2-19, the number of labeled oriented trees with a specified root is equal to the determinant of the reduced Laplacian matrix of the complete graph $K_n$, obtained by deleting the row and column corresponding to the root. Let $L$ be the Laplacian of $K_n$, so that $L=(n-1)I_n - J_n$, where $I_n$ is the $n\times n$ identity matrix and $J_n$ is the $n\times n$ matrix of all ones. Deleting the $i$th row and column gives $L_i$, an $(n-1)\times(n-1)$ matrix of the form $(n-1)I_{n-1}-J_{n-1}$. By the matrix determinant lemma,
$$ \det\bigl((n-1)I_{n-1}-J_{n-1}\bigr)=(n-1)^{n-2}\bigl(1-\frac{n-1}{n-1}\bigr)^{?}. $$
More systematically, $J_{n-1}$ has eigenvalues $0$ (multiplicity $n-2$) and $n-1$ (multiplicity $1$), so $L_i=(n-1)I_{n-1}-J_{n-1}$ has eigenvalues $n-1$ (multiplicity $n-2$) and $0$ (multiplicity $1$). Therefore
$$ \det(L_i)=(n-1)^{n-2}. $$
By Cayley’s formula (which also follows from the canonical representation in Section 2.3.4.4), the number of labeled oriented trees with a specified root is $n^{n-2}$. Consequently, the total number of labeled oriented trees with $n$ vertices, without specifying the root, is $n^{n-1}$.
This completes the proof.
∎
$$ \boxed{n^{n-1} \text{ labeled oriented trees; } n^{n-2} \text{ with a specified root}} $$