[SOUND] [MUSIC] Hi, and welcome back to Introduction to Enumerative Combinatorics. This is lecture four, it is entitled Catalan numbers. In our previous lecture, we were dealing with Fibonacci numbers. They gave us an example of a linear recurrence. They were defined by linear recurrence relation. In our today's lecture, we're going to discuss a non-linear recurrence relation. And we will discuss several appearances of Catalan numbers. They show up in really, many, many command Leonhard problems. And we will discuss only maybe three or four of them. And here is the first problem in which they appear. This problem is due to Leonhard Euler. Let us take a polygon with n plus 2 sides. Let's draw an example. So here's an octagon. We can diagonals inside this octagon. And if we draw several diagonals, we can split it into triangles. This can be done in various ways, and here is one of them. Say, we can do it like this. So here are one, two, three, four, five, six triangles. So an (n + 2)-gon can be split by n- 1 diagonal, Into n triangles. So the problem is in how many ways can we do this? So how many triangulations of an (n + 2)-gon are there? Okay, as usual, let's try to play with small n. Would you know this number of triangulations by c sub n? And it is the nth catalog number. Cn, is the number, Of triangulations, Of an (n+2)-gon. Okay, so suppose that n is equal to one, two, three, or four. In this case, it's at least all the triangulations. So if, n is equal to 1, then the problem is trial, we have a triangle, Which is already triangulated. So there is only one triangulations, and there are no diagonals. So in this case, C of n is equal to 1. Okay, what about a square? Inside a square, we can draw two possible diagonals. So there are two possibilities to dissected enter triangles. Okay, and as usual, we start with the trial case n equal to 0. And in this case, (n + 2)-gon is just a segment. And, well, we say that as usual, there are no triangulations but the number is 1, not 0. This will be important for us. So this, we say that there exists a unique triangulation. Okay, what about n equal to 3? This is a pentagon. And it can be triangulated in several ways. Namely, there is a triangulation of this type. Or four more of them. So you see that for any vertex, that any vertex defines a triangulation. So the two diagonals must meet at one of the five vertices. And they completely define the triangulation. So all of them are as follows. So in this case, the cation number is equal to 5. Okay, what about n equal to 4? What about a hexagon? So a hexagon can be split into triangles in several ways. First, we can draw a triangulation analogous to this one with three diagonals meeting at one given vertex. And there are six triangulations of this type, so every vertex defines a triangulation by diagonals meeting at this vertex. Okay, then, And there is one more possibility. And the diagonals may form something like a letter Z. Something like this. And this picture can be rotated in three possible ways. And there's one more possibility that this picture can be, not only rotated, but reflected. So here is, Another possibility. And this picture can be also rotated in 3 ways. And so we already have 6 plus 3 plus 3, this makes 12 triangulations. And there are two more of them as you can easily show. Namely, one of the triangles can be put into the middle of our hexagon. In this way or, Inner central symmetric way. So this gives us 12 plus two, this makes 14 triangulations. C4 = 14. So we have a sequence starting with 1, 1, 2, 5, 14, how to continue this sequence? [SOUND] [MUSIC]
