0:20

Hello everybody, welcome to our online course on discrete mathematics.

Â In today's lecture,

Â I will show you an especially exciting example of communitorial counting.

Â This is something called Cayley's Formula,

Â it's a formula that tells you how many trees you can find on n vertices.

Â So as an example, let's put your three vertices,

Â let's put four vertices.

Â This is a tree, for example.

Â Note, that all vertices are numbered 1 to n.

Â So this tree here, actually is a different tree from the one to the left.

Â These are different trees.

Â All right, so for example, for k, if n equal 3, how many trees can we get?

Â Well we get this tree, and then we get this tree, and then we get this tree.

Â So for n = 3, we get T3 = 3.

Â 1:31

Right, for four vertices, this is an exercise that I encourage you to do.

Â I want to jump right in to the example of five vertices,

Â because it now gets a little challenging.

Â So what would be a sensible way to count the trees?

Â A special kind of tree is a path, right?

Â 2:06

Then a path is just an ordering of an elements, so I get 5 factorial mini.

Â But by this method I get every path twice,

Â because I get in the once in this directions and once in this direction.

Â And we just take this and divide it by 2, so we get 60.

Â There are 60 paths, okay?

Â So another kind of special tree is the so called star.

Â Star is something we have vertex and then it just has an edge to every other vertex.

Â How many stars do we have?

Â Well you see as soon as I tell you what the center is,

Â you know what star I am talking about, so there are five stars.

Â 2:49

Okay, there is some other tree that is left, which is this.

Â A tree like this is neither path or star, so what can we give it a name.

Â So if we rearrange the vertices, it would look like this.

Â 3:08

So this would be 4, this is 1, this is 5, this is 2, and this is 3.

Â Let's call it the T-shape.

Â How many T-shapes do we have?

Â That's a little bit tricky to count, but let me tell you.

Â If I tell you which vertex this is direct vertex, and

Â if I tell you that the blue vertex here is vertex number 2.

Â And the queen vertex is vertex number 3,

Â well then you already know which T-shape I'm talking about.

Â I can identify them by telling you the reds, the blue, and the green vertex.

Â And you can see this is for 5 times 4 times 3, which is also 60.

Â If we sum it up, we get 125, okay?

Â So T5 is 125.

Â How about 6?

Â Well, here it gets a bit nasty, so I have prepared some computer slides.

Â Again, we have 6 stars.

Â How many paths do we have?

Â Well we have 6 factorial over 2 path.

Â This is 360, and then we have weird shapes.

Â Like this for example, it looks a little bit like T-shape, but

Â how should I call it?

Â Well I call it the Scandinavian cross, because you see here, I put it like this,

Â and it looks a little bit like a flag of Sweden, Denmark and Norway.

Â How many Scandinavian crosses do we have?

Â Well again, if I tell you what the blue, the red, and the green vertex is in

Â the Scandinavian cross then you know which one I am talking about.

Â 4:36

So this is 120, and then we have a trace like this I call

Â this the Star Wars spaceship, and this is kind of tricky to count.

Â Well if I tell you the set of blue vertices, and the set of red vertices

Â then you can identify the trees, so I have 90 choices here.

Â 4:56

This is by no means trivial, it's easy to make mistakes here.

Â But I really double and triple checked it.

Â In this graphic, it called the Euro symbol, and

Â this is especially tricky to count.

Â So I have to tell you the blue vertex, the set of red vertices, and

Â then the green and the violet vertex.

Â So you can see this, I can identify by this, and this gives 360 Euro symbols.

Â And lastly, I have the Y-shape of which we also have 360.

Â So this was fast, go through it again.

Â Convince yourself that this was a correct calculation.

Â If we add up everything we get 1,296, okay?

Â So this is so much fun, let's continue with 7.

Â Actually, let's not do that, I think for 7 there's just no

Â way to do that in one lecture, and it quickly gets extremely complicated.

Â So this way seems hopeless, you can note it by just

Â enumerating all the trees and looking how can they look.

Â It's impossible to determine the total number of trees, but

Â anyway, let's summarize what we have so far.

Â So we can see in this table, on 5 vertices with have 125, and on 6 we have this.

Â And the rest you can do by yourself, it's not too difficult.

Â And you see that this is, wait let's go back.

Â You see that this is actually 6 to the 4, this is 5 to the 3,

Â this is 4 to the 2, this is 3 to the 1, and this 2 to the 0.

Â So this of course suggest the following conjuncture

Â that the number of trees is n to the n minus 2.

Â Okay, so n to n minus 2,

Â this is the number of trees on n vertices.

Â How can we prove that?

Â Well if we look at it, n to the n, what is n to the n?

Â 7:19

So here's the thing, if you have a function from v to itself,

Â you can draw arrows between.

Â So for example, this function, wait, okay.

Â I make an arrow from 1 to 2 from 2 to 8,

Â from 3 to 8, from 4 to 5 from 5 to 2,

Â and from 6 to 5, from 7 to 8 and from 8 to 1.

Â 7:54

So if I put this a little bit more nicely,

Â it looks like this at 8, 1 and 2.

Â 8 points to 1, 1 points to 2, and 2 points back to 8,

Â and then I have the 7 that points into here.

Â And I have the 5 pointing into the 2,

Â the 4 pointing into the 5, and well also the 3

Â pointing into the 8, and 6 pointing into here.

Â 8:27

So this almost looks like a tree, right?

Â Not quite, but it almost looks like a tree.

Â So maybe we can by some clever way, identify functions increase.

Â So for this we actually need a definition, key to the tree on 20 vertices.

Â And now what I do, I identify one vertex as the head and another vertex.

Â Let's say like this, as the butt.

Â 8:58

So formally, here's the definition.

Â If you have a tree, head, and a butt, than this triple is called a vertebrate.

Â So why is it called a vertebrate, because with a lot of fantasy,

Â 9:14

it actually looks like the skeleton of a vertebrate, right?

Â So here, you have the head, here, you have the box and

Â you know the rest, it is actually kind of a tree right?

Â So that's why it called a vertebrate.

Â 9:47

And it's easy to see that Sn equals Tn times n squared, right?

Â How do we get a vertebrate?

Â Well we take a tree, and then we select one point to be the head and

Â one point to be the butt, because both n square choices, we can make.

Â So we want to prove that Tn = n to the n-2.

Â What we actually do, we show that, Sn = n to the n.

Â 10:25

So I want to show that the number of vertebrates is n to the n.

Â How do we do that?

Â Well, I will show you how to take a vertebrate and

Â transform it into a function from V to V.

Â And then I will show you that this process is invertible,

Â you can again take the function and get back the same vertebrate.

Â So in other words,

Â I will construct a bijection between the vertebrates and the functions.

Â And this will show us that their number was actually the same.

Â How do we do that?

Â Here, we have a vertebrate.

Â Actually, we have a tree, so let's make it a vertebrate.

Â Let's choose a head and a butt.

Â And then let's take the path, the unique path from

Â the head to the butt and let's call it the spine, right?

Â So if you have a vertebrate, and then the path from the head back here,

Â this is called the spine of a vertebrate.

Â And let's write down the spine, so the vertices in the spine are 1,

Â 10, 13, 15, 4, 7, 6, okay?

Â 11:39

Okay?

Â So now let's again write the vertices, but

Â in a sorted way, 1, 4, 6, 7, 10, 13, 15.

Â 12:30

Like this, and now what do we do with the rest of our vertices, for example,

Â where do we map 20?

Â Now it suggests itself, 20 is a neighbor of 1, so

Â of course we map it to 1, in the same with 14 and 9.

Â And 3 is a neighbor of 10, so we map it to 10.

Â And 11 is a neighbor of 3, so we map it to 3, right?

Â So the rest of the function will just look exactly like the tree, right?

Â I don't continue here, you can do it yourself.

Â 13:05

So basically, you take the spine,

Â the spine defines a permutation into itself, that's your function.

Â And for the rest, what is attached to the spine,

Â well you just mat it towards the spine and that's your function f.

Â Okay, now I want to show you that this process is actually invertible.

Â So if you give me a function f from V to V,

Â I can construct a vertebrate out of this.

Â Let's do that, this is our function.

Â So first let's identify what should be the spine of the vertebrate,

Â it should be everything that lies on a cycle in our function.

Â So this here, so we see 1,

Â 8, 2, or the other

Â 14:26

Well this is the butt, and this is the head.

Â And 5 max to 8, which means in the vertebrae,

Â it's just a neighbor of 8, and here, you can construct your tree.

Â So here this is the vertebrate.

Â So I have shown you how to take a function, and

Â again translate it into a vertebrate.

Â So here is the summary, a vertebrate is this triple.

Â And we have shown that there are Tn times n squared vertebrates.

Â And then we have shown this 1 to 1 correspondence between vertebrates and

Â functions, which told us that there are n to the n vertebrates.

Â And from this, we derive Cayley's Formula which is the number

Â of trees on n vertices, is exactly n to the n minus 2.

Â Thank you for today.

Â [MUSIC]

Â