[MUSIC] 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. 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? So paths, how many paths do we have? Well the thing is if I put a little arrow here, 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. 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. 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. 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. 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? Well we have seen such a thing before, n to the n, this is the number of functions from v to v. So maybe we can identify functions and trees. 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. 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. 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. 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, 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. All right, so let Sn be the number of vertebrates, On n vertices. 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. 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? Okay? So now let's again write the vertices, but in a sorted way, 1, 4, 6, 7, 10, 13, 15. So what is this? This is a function from the spine to the spine, and this will be our function f. So let's write it down in this arrow notation, 1 maps to itself, 4 maps to 10, and 10 maps back to 4. And then we have 6, 13, 7, 15, 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. 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 way around, 1, 2, 8. 1 maps to 8, 2 maps to 1, and 8 maps a 2, okay, that's your function, Well that's x, and that's f of x, and this already identifies the head and the butt. So the spine looks like this, 8, 1, 2. 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]