[SOUND] >> Here's another problem. Suppose we have 2n people, Who are forming a line to, say to enter a movie theater. And here is the beginning of the line, and here is the cashier, and the ticket costs $5. Okay, I suppose that out of these 2n people, n have exactly one $5 bill. And the remaining n of them have also one bill, and this is a $10 bill. And we also suppose that in the beginning the cash box is empty. So the cashier has no change. So the question is in how many situations everyone will be able to buy a ticket without waiting for change? So, well for example, question, in how many situations everyone will get their tickets, without waiting for change. So, for example, if in the beginning, we have n people with $5 bills and then the remaining persons with $10 bills then everything's fine. So, these and people will get their tickets, well, each ticket costs $5. And then in the cash box there will be n 5ers. And they will begin as change to the remaining n persons who have $10 bills. So, in this case, everything is fine. So here's not a good example. So suppose we have first two people with 5ers, then 10. Then 5, 10, and 10. So the first two people who get their tickets, and there will be two $5 bills in the cash box. Then, the third guy comes and gets their ticket and gets $5 change. And there is one more $5 bill in the cash box left. The fourth guy comes and gets his ticket, and there are two $5 bills left in the cash box. So the fifth and the sixth guys get their change without any problems, so in this case everything is okay. And, suppose that, things are, As follows. So, suppose we have 5, 10, 5, 10, 10, 5. In this case, the first one has a 5er and gets his ticket. The second one gets his ticket at $5 change. Then the third person also gets their tickets and his $5 bill comes as a change for the fourth one, and then the fifth guy comes and there is no change left in the cash box. There are no more 5ers. So this situation is bad. So what we are going to account is the number of good situations for a given n. Okay, as usual we start with small n. So for n equal to 1, there are just two people and only one situation is good, so the first one should have a 5er and the second one should have 10 bucks, okay. So there is only one good situation. For n equal to 2, there are two ways in which everyone will get their change so it's 5, 10, 5, 10, or 5, 5, 10, 10. What about n equal to 3? Well, in this case, we have several good situations. 5, 5, 5, 10, 10, 10, 5, 5, 10, 10, 5, 10, or 5, 10, 5, 5, 10, 10, or 5, 5, 10, 5, 10, 10. We have already seen this one, over here. Or, 5, 10, 5, 10, 5, 10 where people with 5ers and $10 bills common pairs. So the total number of said possibility is 5 and you can easily see that. There are no more good sequences for n = 3. So the answers are 1, 2, 5 and you certainly have already guessed that this sequence is nothing but the Catalan numbers, the sequence that we had in our triangulation problem. So the answer, And the number of good lines, Is equal to Cn to the nth Catalan number. We will show that the number of good lines satisfies the same recurrence relation as the number of triangulations. For doing this, we will need the notion of depth paths. [SOUND]