[MUSIC] We have discussed two different appearances of Catalan numbers. As the number of triangulations of an N+ have gone and as the number of deep paths of length to n so in fact, there are many more of them. And you can find many, many more interpretations of Catalan numbers and a wonderful book called Enumerative Combinatorics. And it's volume two. This book is written by Richard Stanley. In this book you can find 66 descriptions of Catalan numbers. And if it's not enough, you can Google Stanley's webpage and there is a file called the Catalan addendum. With even more interpretations of Catalan numbers and it's always increasing and now the number of varied description is i think about 200. Okay, and we will discuss only one more. And this interpretation of Catalan numbers is called the binary trees. Okay, this are graphs embedded into plane, so the vertices of our graph have, Now that's 301. If the masses is 1 and they're called leaves and- These pictures look like Like this. And we have one distinguished vertex, which is called the root of this tree. And these are leaves, so. Each branch can be separated by two, or it can, each branch of out tree can be either separated into two parts or it can end up with a leaf. So there are one, two, three, four, five, six leaves, a binary tree, With six leaves. As an example let us list our binary tree with four leaves. And they can be as follows. So, Is one of them. So, each branch going right is ending up with a leaf. Well not very interesting. Okay there is another one symmetric to this one. With four leaves, or there can be symmetric tree or there are two more. Namely this one, And a symmetric one, it's mirror image. Okay, so number of binary trees with four leaves is five and you already know, we're aware that five is the third Catalan number. So, here is a theorem, the number, Of binary trees, With n+1 leaves, Is equal to nth catel number Cn. Okay, I won't give a complete proof of this theorem i will always cash it. But the proof will be bijective I will construct a bijection of the set of binary trees with the set of triangulations of an n plus 2 gone. And we already know that the number of triangulations is equal to the nth Catalan number. Okay, I will draw a picture which will show how does this bijection look like. And maybe as an exercise that this is a ND and bi section. Okay, let me draw some polygon. So, this polygon will have one, two, three, four, five, six, seven, eight, nine, ten vertices. So, and so ten sides. Okay, and suppose we have a triangulation of this polygon. Namely, we have something like this. So, you see that this is split enter is ten-gon is split into eight triangles. Okay, let me now draw a tree, binary tree correspondent to this triangulation. How do I do this? Okay, suppose I have a triangle. Let me draw a letter Y on this triangle, as follows. I put dots on it's sides. Then i join them by the following. Figure looking like a letter Y. Let me now draw such Y's on each of the triangles. Let me start with one side which i will denote. By this big pink dot. And it will correspond to the root of my, Binary tree. And let me draw, just ordinary pink dots on all other edges. They will correspond to leaves on my binary tree. And they will be exactly n plus one of them. n+1 leaves. Okay, now on each, Triangle I draw such a Y as I have shown you here. So, here's this, the other three segments which I have drawn on this triangle. Okay, let me pass to this one, So, I join this vertex in the middle, with this dot on the edge. And I continue my edges into the next triangles. So, in the middle of this triangle I put a dot, which will be a three band vertex of my binary tree. So, here we go and this triangle corresponds to this leaf. And then I put the last dot here, in the middle of this small narrow triangle. And here's my picture. So, now the last thing i'm going to do is to deform it slightly for you to see that this is indeed a binary tree. So, what happens now? I'm going to rewrite this picture here. So, I start with my root, There is an n edge coming out of it and- And vertex, ending with a leaf here. And a trivalent vertex here. Here it is. Okay, it corresponds to, This pink dot is here. And I continue my picture and I, pass to this triangle. This triangle does not, have any, pink nodes on it's edges, so all the members of this vertex, are just dry ban vertices it's not leaves. So, here's this one and this point corresponds to this triangle. And there are two leaves next to this point. And this point is here. And there is one leaf coming out of it. And one more Y point which corresponds to this triangle. And here i need to copy just two branches with two leaves on each of them. So, this is my construction of a tree with one, two, three, four, five, six, seven, eight, nine leaves and one root. Each corresponds to a triangulation of a polygon with ten sides What I leave you to prove is that this correspondence is indeed a bijection. Namely each binary tree is obtained from a unique triangulation and vice versa from each binary tree you can construct. Triangulation of n plus 2, gone. This left here as an exercise, and this is a common thing in combinatorics. It is an example of bijective proof so you want to show that the number of elements in two sets is equal. To do this you establish a bijection between these two sets. So, we have here we have established a bijection between binary trees and triangulation of my N plus two gone. Thank you. [MUSIC]