Yet Another Proof for the Enumeration of Labelled Trees

Based on a comment of Herb Wilf (spelled out by D. Zeilberger)

[Exclusive for DZ’s mailing list, and his ftp and www forum.]

In [1], a very short and elementary proof of Abel’s identity was given, using the methods introduced in [2]. For the sake of completeness we reproduce the statement and proof.

Theorem: For n ≥ 0:

∑_{k=0}^{n} \binom{n}{k}(r + k)^{k−1}(s − k)^{n−k} = \frac{(r + s)^{n}}{r}  (1)

Proof ([1]): Let F_{n,k}(r, s) and a_{n}(r, s) denote, respectively, the summand and sum on the LHS of (1), and let G_{n,k} := (s − n)\binom{n−1}{k−1}(r + k)^{k−1}(s − k)^{n−k−1}. Since

F_{n,k}(r, s)−sF_{n−1,k}(r, s)−(n+r)F_{n−1,k}(r+1, s−1)+(n−1)(r+s)F_{n−2,k}(r+1, s−1) = G_{n,k}−G_{n,k+1} ,

(check!), we have by summing from k = 0 to k = n, thanks to the telescoping on the right:

a_{n}(r, s) − sa_{n−1}(r, s) − (n + r)a_{n−1}(r + 1, s − 1) + (n − 1)(r + s)a_{n−2}(r + 1, s − 1) = 0.

Since (r + s)^{n} · r^{−1} also satisfies this recurrence (check!) with the same initial conditions a_{0}(r, s) = r^{−1} and a_{1}(r, s) = (r + s) · r^{−1}, (1) follows.

Now, letting n → n − 2, r := 1, and s := n − 1, and setting b_{n} := n^{n−2}, one obtains the recurrence:

b_{n} = ∑_{k=0}^{n−2} \binom{n − 2}{k}b_{k+1}[(n − k − 1)b_{n−k−1}].  (2)

Let t_{n} be the number of labelled trees on n vertices, then:

t_{n} = ∑_{k=0}^{n−2} \binom{n − 2}{k}t_{k+1}[(n − k − 1)t_{n−k−1}].  (3)

Indeed every labelled tree T on {1, 2, …, n} gives rise to a unique triple (T′, T′′, S), where T′′ is the rooted tree to which the vertex 2 belongs, in the forest resulting from deleting 1 (rooted at the vertex connected to 1), T′ is the tree obtained from T by deleting T′′, and S is the set of labels (in addition to 1) participating in T′. Now sum over all possible k := |S|, to get (3).

Since b_{1} = t_{1}, and b_{n} and t_{n} satisfy the same recurrence, it follows that we have the (n^{n−2})th proof of Cayley’s theorem.

References

1. S. B. Ekhad and J. Majewicz A short WZ-style proof of Abel’s identity, preprint. (available via anonymous ftp to ftp.math.temple.edu in directory pub/jmaj )

2. J. Majewicz WZ-type certification procedures and Sister Celine’s technique for Abel-type sums, preprint (available via anonymous ftp to ftp.math.temple.edu in directory pub/jmaj ).