As a poster child for the application of generating functions next we're going to take a look at the Catalan numbers, which are a fundamental sequence of great interest in combinatorics. one way to, there's many applications of the Catalan numbers, and I'll give a few. So one of the earliest that people thought about was, how many different ways are there to take a polygon with n+2 sides and draw lines from one vertex to another and make it all triangles? So for example if you have a pentagon, you have all these different ways to triangulate it well actually it's easy just draw from any vertex you draw to the two opposite and in a five vertices you get five triangulations or if it's a square you just get two but if you, if it's a hexagon, there's lots of possibilities you can do three like that or you can do these N shapes and there's lots of possibilities and actually turns out that the number of triangulations of a hexagon is fourteen. so that's a number sequence that is described by this recurrence relation, over here. the in, in general if we draw and leave K. we draw our diagnol and leave K vertices on one side, and N minus one minus K on the other side, and there's one less because we draw the triangle, then you can triangulate those anyway that you want and each one of them independently. So it says thatt the number of triangulations has to satisfy that reccurence relation, sum from zero to K less than N, T, K, T, N minus one, K, plus an extra because there's always one way to triangulate the the triangle. So that's a recurrence relation that we're going to take a look at solving. but it applies in many other applications. here's another application the so called, gambler's ruin problem. So you're a gambler, you start with zero dollars and you make $1 bets. And if you win, the line goes up. There's just a graph of the amount of money that you have. So in this case, there's two wins, followed by a loss. Win, loss, win, loss, two wins and then a bunch of losses. And the idea is the gambler will keep going until having $0 makes a bet and loses and then the game's over. And how many different A's so are there for, for, the for, for the gambler to do that, I would say N, N wins in the sequence and a lot of b loses to and so, and again, if you try out all the possibilities it turns out that, there's only two possibilities, if there's two dollars you could win, lose, win, lose or you can win 2 and then lose 3 and those are the only two possibilities. And there's five different ways for three wins in fourteen for four wins. And same sequence because it satisfies the same recurrence. You can just set up the recurrence by the first time the gambler gets back to zero if that happens after K wins. then independently you have a gambler's ruin problem on K and then N minus 1K. And it follows the same recurrence. U, here's another one binary tree structures. So a binary tree is a root node that has connected to two binary trees, the tree on the left and the tree on the right or it could be empty. w-, that's called an external node. So how many different binary trees are there with N nodes? And we'll look in much m-, in a lot of detail at binary trees later one. So this f-, Two different binary trees with two nodes so that is you got one of the root and you could have a one node tree on the left or a one node tree on the right and every node has to have two children and the ones at the bottom have two blank children, those are called external nodes. For three, there's five possibilities you have a node at the root and it could be empty on the right with either one of these trees on the left or it could be empty on the left with either one of these trees on the right or you could have two trees of size one, one on either side. so there's five possibilities for three nodes. And similarly, there's fourteen possibilities for four nodes. so, you could have empty on the left, and anyone of the three node trees empty on the right. Anyone of the three node trees on the left. Empty on the left, anyone of the three node trees on the right. or you could have one on one side and two on the other side in four possible ways. so again, same number sequence again, satisfies the same recurrence. if you got k nodes on the left, you are going to have n minus one minus k nodes on the right. And you can try all possibilities on either side so it's got to satisfy the recurrence, where you, T equals n is equal to the sum for all k up to n minus one of Tk, Tn minus one minus k plus delta trying to make it true for zero, Catalan numbers. here's another one. How many trees with n nodes? A tree is a node connected to a forest of trees. To any number of trees, so it's not restricted to be just two. And again, we'll talk in detail later in the course. about trees and binary trees. but for now, I just want to point out all the possibilities. and it satisfies these same recurrents. so Catalan numbers describe a lot of combinatorial objects of interest. So how are we going to solve the Catalan recurrence with generating functions? Well, we're going to use the formula. we got the recurrence that holds for all N. now we're going to, what's the next step? It's multiply by Z to the N and sum on N. on the left hand side, that gives us T of z. that's the generating function for the Catalan numbers. On the right hand side we'll get a one for the delta term on the right. and then we get some [INAUDIBLE] zero. Zero less than or equal to K less than N, TKTN - 1. and that looks familiar, it is familiar. that's we're going to work backwards from the convolution derivation that we did before. so, Now what we'll do is, first thing we'll do is switch order of summation. so switching order summation means if you're try for every value of K then the inner sum is just for N bigger than K. now in that inner sum will change N to N plus K plus one. Change n to n+k+1, n bigger than k, that's n bigger than or equal to k+1. So that's the same as n bigger equal to zero. And then the t sub n-1-k just becomes T sub N. And then we have z^(n+k+1). And that gives us a way to split it into independent sums by distributing the ks and the ns. And then you can see immediately the one z comes out and then it's two copies of the generating function t of z. so that's a backwards convolution that shows us that the Catalan generating function has to satisfy this functional equation. T of c equals one plus z times t of z squared. So we're halfway there. we've got a, an equation that the generating function has to satisfy. Now I. Common sense rule for working with generating functions that I want to point out, and again it's always worth while to check your math with your computer, and that includes symbolic, calculations, like this one, You know the initial values of T of Z, we did the, we did the examples so we know that it starts out being one plus Z, plus 2Z squared plus 5Z cubed plus 14Z four. before we go any further we might want to check that this equation that we have are really holds and you can do it in pencil and paper or you can use a symbolic maths system and you could see that if you take 1 + z times 1 + z^2 and so forth I just took it out to four terms here the ones that we know if we multiply them out it the you get 1 +z+2z z +2z^2 + 5z^3 + 4 and so forth. Now after a while the terms are no good because we didn't take these terms far enough. but still that gives confidence and actually you can boot strap this to get more terms. But, it gives confidence that we've got the right equation. so that's just checking your math with the computer even when it's, symbolic. Alright so now what we need to do is to extract coefficients to find an expression for the N-th Catalan number. So that's the GF equation well it's an equation we know how to solve with the quadratic formula. and so that's the solution with the quadratic formula. just implying the eighth grade formula. and then, we have to pick 1 plus or 1 minus and It, it's going to be the minus. So just left out that one consideration. and that you get from checking with the initial values. so now how do we deal with that? We, we expand one over, square root of 1 - 4Z with, just use the binomial theorem. It's 1 - 4Z to the one-half power, so it's the sum of one-half 2's and 4Z to the N. and then this one part goes away. and so, and again, we can check that from initial values. so that's a key step for this generating function. We have a solution that uses the quadratic formula. And then we have a [COUGH] an expansion of a function that we know how to expand, know how to find coefficients. so that tells us what T sub N is. it's minus a half. One half choose N plus one minus four to the N plus one. This extra Z is what gives to, leads the, the N plus one. Now that is, it is okay, it is not totally satisfying because the one half n+1 is may be not such familiar function in its way to manipulate this to get it to be a little more familiar function and actually next time we will talk about much better way to continue to manipulate it to get really a concise representation. But let us just do a little more algebra to get the. It's in more of a form that we can people can. relate to so This is the definition of the binomial coefficient, when the upper index. for any binomial coefficient we just, it's On the bottom is N plus one factorial. And on the top is N plus one terms, where we subtract zero, one, two, all the way up to N. so that's just the do, definition. And there's the - 1/2 and there's the - 4 to the N + 1. And so now what we're going to do is take we have N plus one terms here and we've got n plus one force and we're going to take a bunch of those if we'll take the n plus one minus 2's and multiply them in, and one of them kills that and then the others you get one, three, five all the way up to 2n minus one like that. so that's a slight trick but cleans it up quite a bit and now if you have that then if you fill in the evens so two to the n is two over one times four over two and so forth. As now we have the odds and the evens and we have an n factorial so that's going to immediately give us 2n factorial over n factorial times n factorial which is 2n choose n. So that's a proof that the number of binary trees in N nodes, number of general trees in N nodes, the number of ways to triangulate an N plus 2-gon, and so forth. The Catalan numbers is one over N plus one, times two N choose N, and that's one of the most famous number sequences in combinatorics. and we'll see in many cases we explicitly use data structures like trees in practical algorithms and data structures. So we need to understand these properties of them. and we're going to continue working with the Catalan numbers in several other occasions later on in the course.
