[MUSIC] Now, let us show that the number of deep path satisfies the same recurrence relation as the number of triangulations for n plus 2 gon. Suppose we have a Dyck path. Which looks like in this. This is 2n and this is 0. So, the number of fiber is equal to 0 at the very first moment and at the very last moment. So this path should start from 0 and get back to point 2n, 0. Let us denote the first moment when this path touches the 0 axis by 2k. So, an easy question to you is why is this number always even? So, why is the cash box always empty only after an even number of tickets is sold? So would you note this first moment when the cash box is empty, 2k and we're looking at the two parts or the Dyck path everything which is happening after this moment. We'll draw this line my orange ink and we look at the piece of Dyck path, which is from the moment 0 to the moment 2k. Although we see that the first person who gets their ticket must have a bill of $5. So, the first segment is always going up and the last segment of this interval is always going down. Because after this guy got his ticket, the cash box has no fiber. So, this means that he had a $10 bill and he got the last $5 in the cash box as change. So, this part of the Dyck path has two pink legs. The first one going up and the second one going down and we see that during this interval, the cad box was never empty. So, it had at least one dollar at every moment. So we see that this part of the graph from 1 to 2k-1 is situated not only above the x-axis, but it's also situated at about the line y=1. So it can be considered as Dyck path of length 2k minus 2 starting here and coming to this point, and we will draw this part with yellow ink. And this is a Dyck path. Of length 2k minus 2. And this orange part is a Dyck path. Of length. 2n-2k. So, you see that if you want to compute the number of Dyck paths who on which touch the x-axis for the first time at the point 2k, you need to multiply the number of Dyck paths of length 2k-2 by the number of Dyck paths of length 2n-2k. So the number of. Dyck paths. A meeting the. The x-axis. For the first time. At 2k-0 equals the number of Dyck paths of length 2k-2. That is Ck-1 times the number of orange Dyck path, namely Cn-k. So, we see that the total number of Dyck paths is obtained by summing these values together k from 1 to n. So, we get the same recurrence relation. Cn is equal to the sum of for k from 1 to n, Ck-1 times Cn-k. We see that the number of Dyck paths satisfy the same recurrence relation as the current numbers. Well, the first value is C0 and C1 coincide with the number of triangulations. So, the number of Dyck paths. Of length. 2n is equal to the n number. And here is a challenge for you. We have shown that these numbers satisfy the same recurrence relation. It is interesting to establish a bijection between them. So a challenge. Established bijection between deep paths and triangulations of n+2 gon. Dyck paths of length. 2n correspond to triangulations. Of an (n+2) gon. [MUSIC]