[MUSIC] Okay, so let's write down the recurrence relation for catalog numbers. Okay, suppose we have an n + 2 gon. And, let us. Say that one of its edges will be Distinguished, so we draw it in pink. Okay, and let us index the remaining vertices of this polygon. So they will be indexed by 1, 2 etc. k, etc., n. Well here's the vertex n- 1, [INAUDIBLE]. Okay, and we'll take our distinguished edge. And we'll look at the triangle. Well, suppose that our polygon is split into triangles. In certain way. There's something happening here, something on here. Okay, and we had a look at the triangle which is adjacent to this pink edge. So it's, suppose that it's a third vertex has number k. So suppose that The third, Vertex, Of the pink triangle Has the number k. So this is the kth vertex. And we can consider the part of our polygon which is to the left of the pink triangle. So here is it. And there is also something to the right of it. So it will be drawn in orange. So our main triangle sub divides the whole picture into three parts. The yellow one, the orange one and the pink one, which is just one triangle. Okay, let's look at the yellow part. The yellow part is well, how many vertices that it have? It has one, two, three, etc. k plus one vertex. The yellow part is a k plus one gon. Okay, and what about the orange part? So the number of vertices of the orange polygon is equal to n minus k plus 2. Namely, there are, Vertices from k to n and the vertex of the distinguished side. So, it is n minus k plus 2, so the orange part Is an n-k+2 gon. So now suppose that we have [COUGH] drawn these two diagonals. Which are the sides of the pink triangle, and we want to subdivide the yellow part into triangles, and the orange part into triangles in a certain way. How many ways are there to do this? Well, suppose that we know all the Cns for the small values. So suppose we, We know in how many ways can we subdivide the k+n-gon. So the number of ways to do this is Ck-1. Indeed for an n+2-gon, the number of triangulations is Cn, and for (k + 1)-gon, this is Ck- 1. And for the orange polygon, the number of triangulations is Cn- k. So, if we draw these two diagonals, the remaining diagonals can be drawn in Ck-1 times Cn-k ways To Split, The remaining, Part of our polygon into triangles. Okay, so it's interesting to look at some extreme cases. So if, say if k is equal to one, what happens? In this case, the yellow part is just a segment. It is a two-gon. And there are a number of ways to dissect this. It is C0, it is one. And the same thing happens if k is equal to n, so everything seems to be fine here. Okay, and to get the whole number of triangulations, we need to sum up these values over all possible values of k. So, Cn is equal to, C0 times CN- 1 + C1 times CN- 2. The sum of these two indices is always n minus 1 plus C2 x Cn- 3 + etc. up to Cn-1 C0. So this is the sum of, For k from 1 to n of Ck-1 times Cn-k. And this is the recurrence relation for Catalan numbers. So you see that it also expresses the value of Cn for a given n through the previous ones. But as opposed to Fibonacci numbers, this relation is not linear anymore, it this quadratic. You need to multiply pairs of the previous values. So here's the difference between Fibonacci numbers and Catalan numbers. And having this recurrence relation, you can compute some of the next values. We already know that C0=1, C1 is also 1, C2 is 2, C3 is 5, and C4 is 14. So to get the next value, C5, you need to use this formula. So you multiply 1 x 14 +1 x 5 + 2 squared + 5 x 1 + 14 x 1. And this is, well, this is 14 + 5 + 4 + 5 + 14, and this is 42. And you also can see that C6 is equal to 132, and so on. So we have a recurrence relation for Catalan numbers. And later in this lecture, we'll get an explicit closed formula. But before we do that, let us discuss one more problem which seems to be completely unrelated to this one, but in this problem you also get Catalan numbers as an answer. [MUSIC]