One of my favourite proofs is Joyal’s proof of Cayley’s Theorem on trees. Today at the Cochin conference on graph theory and combinatorics, in response to a question from Brendan McKay, I found a nice application of it.
Cayley’s Theorem says that the number of trees (connected graphs without cycles) on the vertex set {1,…,n} is nn-2. There are very many different proofs of this theorem; each proof tells us something new. It is one of the strongest arguments I know for having many proofs of a theorem.
Joyal’s proof works like this. Define a vertebrate to be a tree with a pair of distinguished vertices called the head and the tail. (They may be the same vertex.) If T(n) denotes the number of trees on {1,…,n}, then there are n2T(n) vertebrates, since there are n choices for the head and the same for the tail.
An endofunction is a function from the set {1,…,n} to itself. Clearly there are nn endofunctions, so we are done if we can prove that there are equally many vertebrates and endofunctions.
Now a vertebrate, as its name suggests, has a backbone, the unique path from its head to its tail. This is a path consisting of k vertices, for some k; the rest of the vertebrate consists of rooted trees attached at the vertices of the backbone. It is determined by specifying the value of k, the set of k vertices on the backbone, the order in which they come from head to tail, and the k rooted trees attached at these points.
An endofunction has a set of recurrent points, which are permuted by the function; any other point arrives at a recurrent point after a series of moves, and these moves have a tree structure. So to specify an endofunction, we give the number k of recurrent points, the set of there points, the permutation of them induced by the function, and the rooted trees attached at the points.
Comparing these specifications we see that the only difference is that we choose an ordering of k points in one case and a permutation of k points in the other. But the numbers of orderings and permutations are equal (namely k!), and so the numbers of vertebrates and endofunctions are also equal.
We see, moreover, that the number of vertebrates with k points in their backbone is equal to the number of endofunctions with k recurrent points.
At the conference, I lectured about synchronization. Afterwards, Brendan McKay asked me about the synchronization properties of a random automaton with given number of states and transitions.
Now such an automaton just consists of r endofunctions (transitions) on the set of n states. In the case r=1, we have a single transition, and the automaton is synchronizing if and only if there is a single recurrent point (since you will end up there after sufficiently many applications of the function). The number of these is equal to the number of vertebrates with head equal to tail. This happens in just n of the n2 choices of head and tail for each tree; so the probability is 1/n.
We also see that the expected length of the synchronizing word is equal to the expected height of a random labelled rooted tree. I am sure this is known, though I don’t have the result at my fingertips.
A much more interesting and difficult question is: what happens for two random transitions?
Peter Cameron's Blog 
I also like very much Andre Joyal’s proof. It was the example that impressed me most of the things Andre discussed in 1980, when he was writing up his paper on species in Sydney. The proof expresses the species of endomorphisms, and the species of doubly rooted trees as ‘composites’ of simpler species, the only difference being that the first contains linear orders as a ‘factor’, whereas the second has permutations as a ‘factor’. These two species are not (naturally) isomorphic but are the same at the level of counting.
I am just repeating what you said above, but it is the example which convinced me to take species seriously.
Yes, I first learned about it in Sydney in 1980. I visited the Pure Maths department for a term, and in a corner of my office I found a big pile of preprints of the French version of André’s paper on combinatorial formal power series. I fell under its spell straight away, especially since some of the ideas and formulae were very close to things I had come up with in the context of infinite permutation groups. We were climbing the same mountain from different sides.
Of course, I made no mention of species or categories in the post; I wanted to explain the idea as simply as possible.
Pingback: The symmetric group, 11 « Peter Cameron's Blog
Pingback: Expected number of cycles in random function – Math Solution