Cayley's formula via generating functions!?

by math_explorer, Nov 10, 2015, 1:35 AM

Cayley's formula for the number of trees is probably my favorite elementary theorem. I got an additional reason around a week ago. As far as I know, generating function solutions are not usually known for elegance, but I thought this was pretty mindblowing.

Theorem. Let $P_n$ be the polynomial in $n$ variables such that the coefficient of $x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}$ in $P_n$ is equal to the number of rooted trees on vertices labeled $1, 2, \ldots, n$ where the vertex labeled $i$ has $\alpha_i$ children. Then $P_n = (x_1 + x_2 + \cdots + x_n)^{n-1}$ .

Proof. We use induction. When $n = 1$ we have $P_1 = 1 = x_1^0$ and there is indeed exactly one rooted tree on one vertex labeled $1$ where it has zero children.

When $n > 1$ , let's consider the rooted trees where $n$ is a leaf. These have a one-to-one correspondence with pairs of rooted trees on $n - 1$ labeled vertices and a specified vertex, since you just attach $n$ as a child to the specified vertex. Therefore, if $\alpha_n = 0$ , the coefficient of $x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}$ in the polynomial $Q = (x_1 + x_2 + \cdots + x_{n-1})P_{n-1} = (x_1 + x_2 + \cdots + x_{n-1})^{n-1}$ is equal to the number of rooted trees on vertices labeled $1, 2, \ldots, n$ where the vertex labeled $i$ has $\alpha_i$ children (by the induction hypothesis).

You might think we now have to count or classify rooted trees where $n$ isn't a leaf... but nope:

In polynomial form, our results above state that, when $\alpha_n = 0$ , the coefficients of $x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}$ in $Q$ and in $P_n$ agree.
By inspection, when $\alpha_n = 0$ , the coefficients of $x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}$ in $Q$ and in $(x_1 + x_2 + \cdots + x_n)^{n-1}$ agree.
$P_n$ and $(x_1 + x_2 + \cdots + x_n)^{n-1}$ are both homogeneous symmetric polynomials with degree $(n-1)$ in the $n$ variables $x_i$ .

Therefore, $P_n$ and $(x_1 + x_2 + \cdots + x_n)^{n-1}$ are the same polynomial! This is because if they had different coefficients for some term $x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}$ , then $\sum \alpha_i = n - 1$ so some $\alpha_i = 0$ . Then by symmetry, they would still have different coefficients for some other term $x_1^{\alpha'_1}x_2^{\alpha'_2}\cdots x_n^{\alpha'_n}$ , where $\alpha_j$ and $\alpha'_j$ are identical except for $\alpha'_n$ and $\alpha'_i$ being swapped. But from our observations above, since $\alpha'_n = 0$ , the coefficients of these terms are the same, contradiction. So $P_n = (x_1 + x_2 + \cdots + x_n)^{n-1}$ .

Corollary 1. There are $n^{n-1}$ rooted trees on $n$ labeled vertices.

Proof. The sum of the coefficients of $P_n$ is computed by $P_n(1, 1, \ldots, 1) = n^{n-1}$ .

Corollary 2. There are $n^{n-2}$ unrooted trees on $n$ labeled vertices.

Proof. Rooted trees are just unrooted trees with one of $n$ vertices specified.

This post has been edited 1 time. Last edited by math_explorer, Dec 10, 2015, 2:40 PM