Now, rather than write out all the possibilities,

the short form to do this is to just write the unlabeled trees and

then write all the N-words that give those same trees.

So, for example 1 1 2, so that's this first tree here.

1 points to 1, 2 points to 1, so that's 1 1.

And then 3 points to 2, and so forth.

1, 1, 1, and that's 1, 2 and 3 all point to 1.

So that's the N-word, and

that's the tree structure that comes out it for all those cases.

So that's Cayley trees.

So now the answer is the number of Cayley trees,

you might have guessed that there's a power going on.

It turns out to be N to the N minus 1.

But that's not at all an elementary result.

We're going to use a technique called Lagrange inversion, eventually,

to get to this result, and it's described on the next slide.

Lagrange inversion is a classic method for computing a functional inverse.

And it's a very important and deep theorem.

I'm not going to go into all the ramifications because

we use it in a quite as straightforward way.

So, for example, if I have a function f(u) = z like f(u) = 0 over 1- u,

then, the inverse of that is the function u = g(z).

So if I set z = u over 1- u, and solve for

u, I get u = z over 1 + z.

So that's the inverse.