The Number of Labelled Trees over n Nodes

Yesterday, my colleague Anders Claesson, from the combinatorics group at Reykjavík University, gave a very good talk at the Icelandic Mathematical Society entitled "The Art of Bijective Proofs and the Science of Generating Functions". During the talk, Anders used as a running example a theorem of Cayley's to the effect that the number of labelled trees over n nodes is n^n-2.

Anders presented a bijective proof of this counting result due to André Joyal. (Concurrency theory buffs will recall that Joyal, together with Mogens Nielsen and Glynn Winskel, was one of the authors of the famous paper Bisimulations from Open Maps. Anders tells me that Joyal is also the father of the theory of combinatorial species.)

The proof is truly beautiful, and establishes a bijection between doubly rooted trees over {1,...,n}, and functional digraphs over that set. (A digraph is functional if the out-degree of each of its nodes is 1.) I encourage all of you to have a look at it.

Anders then showed how to obtain a proof of Cayley's theorem using the very general machinery of generating functions. (See this freely available book.) I must admit that I find the latter proof a little "magical", but this is due to my ignorance of the machinery of formal power series, generating functions and Lagrange inversion :-)

Addendum 18/11/2006: I have noticed that the classic textbook A Course in Combinatorics (2nd Edition) by J. H. van Lint and R. M. Wilson presents three different proofs of Cayley's theorem. (I think that the book offers five proofs of that result overall.)

As reading on generating functions, Anders recommends the draft book Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick even more than Herbert Wilf's book.