Joyal’s Proof of Cayley’s Tree Formula

I wanted to quickly write this proof up, complete with pictures, so that I won’t forget it again. In this post I’ll give a combinatorial proof (due to Joyal) of the following:

Theorem 1 (Cayley’s Formula)

The number of trees on {n} labelled vertices is {n^{n-2}}.

Proof: We are going to construct a bijection between

  • Functions {\{1, 2, \dots, n\} \rightarrow \{1, 2, \dots, n\}} (of which there are {n^n}) and
  • Trees on {\{1, 2, \dots, n\}} with two distinguished nodes {A} and {B} (possibly {A=B}).

This will imply the answer.

Let’s look at the first piece of data. We can visualize it as {n} points floating around, each with an arrow going out of it pointing to another point, but possibly with many other arrows coming into it. Such a structure is apparently called a directed pseudoforest. Here is an example when {n = 9}.

cayley-pseudoforest

You’ll notice that in each component, some of the points lie in a cycle and others do not. I’ve colored the former type of points blue, and the corresponding arrows magenta.

Thus a directed pseudoforest can also be specified by

  • a choice of some vertices to be in cycles (blue vertices),
  • a permutation on the blue vertices (magenta arrows), and
  • attachments of trees to the blue vertices (grey vertices and arrows).

Now suppose we take the same information, but replace the permutation on the blue vertices with a total ordering instead (of course there are an equal number of these). Then we can string the blue vertices together as shown below, where the green arrows denote the selected total ordering (in this case {1 < 9 < 2 < 4 < 8 < 5}):

cayley-tree

This is exactly the data of a tree on the {n} vertices with two distinguished vertices, the first and last in the chain of green (which could possibly coincide). \Box

Advertisements

One thought on “Joyal’s Proof of Cayley’s Tree Formula

  1. Hey you stupid fucking mathematician cunts would it fucking kill you to write out a goddamn sentence, with actual fucking words, once in a while explaining what the fuck it even is that you just fucking did or what the fuck I’m supposed to actually do with your stupid fucking abstract mathematical objects? I know you have some sick fetish/obsession with trying to explain everything with just numbers and symbols and using the least amount of words possible because you were probably such a fucking socially awkward weirdo your whole life that now you need to try and prove you’re better than anyone at all making your fucking ideas unnecessarily obtuse and inaccessible to anyone but your snide little mathematician friends, but the only reason we keep you on the payroll is to come up with tools for us to use to solve real problems. Sure we let you dick around with your insanely nonsensical 97 dimensional semicuspidal manifolds or your hyperbolic triangles without embedded eigenvalues or whatever the fuck it is you assholes are doing all day. But that’s just to keep you little shits busy so you don’t bother the rest of us with your fucking bullshit periodic approximations of irrational pseudo-rotations using pseudoholomorphic curves. Jesus Fucking Christ. All I’m asking for is ONE (maybe 2) sentences explaining what the fuck this shit even represents. You can blame it on me. Tell your math buddies I snuck it and wrote ‘words’ while you weren’t looking. Just please, for the love of god, tell the rest of us what you are doing and what you want us to do.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s