The n^{n−2}^{th} Proof Of The Formula For The Number Of Labelled Trees

Doron Zeilberger^{1}

There are probably already more than 4^{2} different proofs of the Cayley-Borchardt formula, n^{n−2}, for the number of labelled trees on n vertices([K],[M].) The one I present here is not the prettiest,this honor goes to Joyal’s[J] (see also [L]), and not the ugliest, but it is mine (although it has some similarities with Clarke’s proof[C].) Let R(e, b) be the number of ways of organizing e employees and b bosses, such that every employee has exactly one immediate supervisor (who may be another employee or a boss), in such a way that no employee is her own (immediate or non-immediate) superior. The ways of deciding the organization can be split into four independent decisions:

(i) How many employees, s, 1 ≤ s ≤ e, will report directly to bosses? Let’s call them little bosses. (ii) Which s of the e employees will be named little bosses: \binom{e}{s} ways. (iii)How to organize the s little bosses and remaining e−s employees amongst themselves: R(e−s, s) ways. (iv) For each of the s little bosses, which big boss should she report to?: b^{s} ways. Hence:

R(e, b) = ∑_{s=1}^{e} \binom{e}{s}b^{s}R(e − s, s) ,  (∗)

which together with the trivial initial condition R(0, b) = 1, uniquely determines R. Since the recurrence (*), and the initial condition, are also satisfied by b(b + e)^{e−1}, by the binomial theorem, it follows that R(e, b) = b(b + e)^{e−1}. In particular, R(n − 1, 1), the number of labelled trees on n vertices, equals n^{n−2}.

References

[C] L.E. Clarke, On Cayley’s formula for counting trees, J. London Math. Soc. 33(1958), 471-475.

[J] A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42(1981), 1-82.

[K] D.E. Knuth, “The Art Of Computing Programming”, v.1: “Fundamental Algorithms”, 2nd edition, Addison-Wesley, Reading, 1973. (p. 406).

[L] G. Labelle, Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange, Adv. in Math. 42(1981), 217-247.

[M] J.W. Moon, “Counting Labelled Trees”, Canad. Math. Congress, Montreal, 1970.

1 Department of Mathematics,  Temple University,  Philadelphia,  PA 19122,  USA.

zeilberg@euclid.math.temple.edu . Supported in part by the NSF.