[SOUND] Our next question is how to Dyck Paths. Now we'll give an explicit closed formula for that. For this, we'll use something which is usually called the reflection trick, by Desiree Andrea. Okay, suppose we have. Dyck path of length to n. There's [INAUDIBLE] inside this rectangle. So this. In fact, this is a square with. Each side equal to n times square root of 2, and so the paths should be contained in this square and should be always situated above the X-axis. Okay, what about [COUGH] if we count not just Dyck paths, but all paths going from this point to this point without the condition that they lie about the X-axis? Well, we had this constant problem in one of our first lectures. So the number of search path from 0 to 2N the total number. Of paths from the origin to the point 2n, 0 equals 2n choose n. Because path is formed by two n steps. Like this. And out of these 2n steps, exactly n go up and exactly n goes down. So the number is (2n, n). Okay this is the number of paths without the condition of it being situated above the x-axis. So what about counting dyck paths? To count them, let us first count the number of bad paths, namely those which are. Which at some point descend below the x-axis, like this orange one. And then the number of Dyck paths will be obtained as 2n choose n, minus the number of bad paths. So let us count the bad Paths. Those which descend below the diagonal. And below the x-axis. Okay. And to compute the number of those, we use the reflection trick. Let's take a mud path and let us take the axis x and let us move it by one down. So we get the line. Which I draw in pink here. This line is y y = -1. Okay, I claimed that every bad path at some point meets this pink line. Otherwise, it would be situated above the x-axis. And if not this means it descended at some point, and so it met the pink line. Now let's take the first point where our path meets this pink line, and let us take the part of the path situated to the right of this point. And now let's use the pink line as a mirror and reflect the right part of the path in this mirror. So we get something like this. So these two points are on the same level. And what about this point? The endpoint of this bank or reflected path? It has coordinates (2n, -2). Because it's the reflection of the point 2n, 0 with respect to this axis. Okay. So we have obtained a path from the origin to the point 2n,-2. Each bad path corresponds to a path from 0 to this point. And vice versa, every path from 0 to this point intersects this pink line at some point. So you can reflect the right part of it and get a bad path. So bad paths from zero to 2n. Corresponded objectively to paths from zero to 2n, minus 2 without any supplementary conditions. So bad paths. From the origin to 2n,0 by objectively correspond. To the paths. From the origin to (2n,-2). Okay, and let us compute the number of those paths. It will be equal to the number of bad paths. So we're starting here and we're making 2n steps and finally, we descend by two, below the x-axis. That means that our path is situated inside this rectangle, with sides. N minus one times the square root of two and plus one times square root of two. So, out of two n steps, we need to do n plus one. Step up and, so we need to make n-1 steps up and n+1 step going down. So the number of such steps, the number of such paths is equal to. 2n choose n-1. Or 2n choose n plus one. This is the same thing. Okay, so, this is the number of bad paths and we're interested in those paths which are not bad. So, the remaining paths are exactly the Dyck paths. So, the number of Dyck paths. Which is as we have discussed is the earth cattle number is equal to 2N choose N. The total number paths. Minus the bad ones. 2n, choose n-1. Okay, let's write this formula in a slightly different way. So, 2n to n is 2n factorial. Divided by (n!) squared. And this thing is (2n)! / (n-1)!(n+1)!. So this is equal to (2n)! Over (n-1)! n! Times (1/n- 1/n+1). So this thing is equal to 2n factorial over n- 1 factorial, n factorial times 1 over n(n + 1). So what do we get is 1/n+1 times (2n)!/(n!) squared. And this is 1/n+1 times (2n choose n). So it is N plus 1, so this is 1 over N plus 1 times the middle coefficient and the Pascal triangle. So we have attained the main result of this lecture and explicit formula for catalan numbers. Here's this result. Theorem, the F Catalan number is equal to 1 over n+1, times the middle coefficient in the pascal triangle to n choose n. [SOUND]