The first type of function that we're going to talk about is called rational function. and that actually covers a fair number of the generating functions that we've encountered. A rational function is simply a complex function that's a ratio of two polynomials. So, out of the examples that we have this one which is the generating function for the number of strings having no occurrences of peak consecutive zeros is rational. [UNKNOWN] to polynomials in this, one for set partitions is also a ratio of two polynomials. and the other ones here, they're not rational. They're different kinds of complex functions and we'll talk about how to deal with them in time. But right now, we're going to focus on the rational ones. and the approach is, is simple, it's actually familiar. We're going to do just what we do with, with real functions. when we encounter a ratio of two polynomials with a real function, what we do is we use partial fractions to break up into simpler terms where it's easy to get the coefficients out. and, and not only that, when we have our broken into number of terms, we're going to focus on the largest term to get the approximation. difference is it's the same approach as for reals, the difference is that we might get complex roots of the polynomials. so, and we'll see that in the examples. so here's simple example. So if we have this rational generating function z over 1 minus 5z plus 6z squared. and it's complex and we're going to be interested in a coefficient of z to the N. So, what we do is we factor the plynomial in the denominator. so, in this case, 1 minus 3z, 1 minus 2z. and then using partial fractions means that it's going to separate into the form c0 over 1 minus 3z plus c1 over 1 minus 2z. This is called a method of undetermined coefficients. and now, what we'll do is just cross multiply, and set co, coefficients of the constant equal, set coefficients of z equal and solve for the coefficients. So, if we cross multiply, we get 1 minus 2z times c0 plus 1 minus 3z times c1 over the product 1 minus 3z, 1 minus 2z, has gotta equal z. So, that means the constant part, c0 plus c1, has to equal 0. And the coefficient of z, which is minus 2c0 minus 3c1, has to equal 1, or 2c0 plus 3c1 equals minus 1. So, that's two equations, and two unknowns. So, solve those, you get c0 equals 1 and c1 equals minus 1. 1 plus minus 1 equals 0, 2 minus 3 equals minus 1. And so, plugging those in that says that a of z is equal to 1 over 1 minus 3z 1 over 1 minus 2z. And we can just check that by cross multiplying. But that is something that we can expand. We have the power series expansion for those two functions that tells us that a sub n is 3 to the N minus 2 to the N. That's partial fractions to expand a rational generating function. Now, we can get into different situations depending on the character of the roots. so, one thing that can happen is that you can have roots of higher order. so, for example, with this generating function, when we factor the denominator it's 1 plus z times 1 minus 2z, the quantity square. so, that means that we're going to need three terms in the partial fraction's expansion one for the 1 minus 2z, another for 1 minus 2z squared. And in general, if the root, root appeared three times, we'd need three terms, and four times, four terms, and so forth. So, multiple roots lead to more terms in the partial fraction expansion. But the same basic method works cross multiply. And now we have possible terms of z constant term z and z squared. So now, we have three equations and three unknowns. and go ahead and solve for those. And in this case we get c0 equals minus 2 9ths, c1 equals minus 1 9th, and c2 equals 3 9ths. They all sum to 0, and so forth. And again from that then, we have broken the function up into simpler terms. that we know how to expand the coefficient of z to the N and 1 over 1 plus z minus 1 to the N. in this one, it's 2 to the N. in that one, it's you know, 3N2 to the N. 3 over 1 minus 2z squared the coefficient of a sub N in that is 3N2 to the N. So, that gives us an exact formula for the coefficients in that rational generating function. Now and that's exactly the way we would do this if these very, if this was a real function. now before we go to complex functions I just want to point out that we're going to focus on asymptotic results. So, when the roots are real, we're only going to care about really one term, the largest term. So, we extract those different roots one those different terms, one for each root. but the first thing to, to notice is only the largest one matters anything smaller, any root that smaller than the largest one, it's going to have the, it's going to be a term forth. But it's going to be exponentially small by comparison to the large one, so we just throw it out and get a good approximation. These are excellent approximations, there's no problem with that. So, smaller roots give exponentially smaller terms. and we can when there's multiple roots as in this case it's not exponentially smaller but will usually also just keep the largest of the terms. In this case we'll say that a sub N is asymptotic to 1 3rd N2 to the N. And this is going to hold, in general, no matter what the roots are if they're real. If you get a root that's multiplicity 3, then your're going to have N squared times the root to the nth power and so forth. but generally we're going to keep the largest term. That's when the roots are real. when the roots can be complex, it can get a, a little more complicated and I'll just do an example. to indicate that I'm not going to do all possibilities in this lecture. they're certainly covered in the book though. so let's say, we had this rational generating function. So, this polynomial now has some complex roots so, it can be written as 1 minus 2z over 1 plus z squared. And actually, though, in this case, the 1 minus 2z cancels. So, that all that we have left is 1 plus z squared. So, what's 1 plus z squared? Well, we can write that as 1 minus iz times 1 plus iz. That's what complex gives us. It gives us the ability to factor it all the way down using i equals square root of minus 1. If you multiply those two together, you get 1 then you get minus iz plus iz which cancels. And then, you get minus i squared z squared, but i squared is minus 1 so that's plus z squared. So then, you can, those are the two roots. you can write then the expansion in this form and solve for the coefficients again. and in this case, the solution is that they're both equal to 1 half, so that says that in this case A of z is equal to 1 half 1 over 1 minus iz plus 1 over 1 plus iz. And again, we can extract coefficients in there and it says that the coefficient of z to the N and A of z is 1 half i to the N plus minus i to the N. and actually just factor out the i to the N and you get i to the N times 1 plus minus 1 to the N. and this is interesting because actually this is going to be 0. if if N is even and, and then the final result is not going to have, I'm sorry, if N is odd, it's going to be 0. So, it's not going to be any i's in the final result. And actually the sequence goes 1 0 minus 1 0. So, it's a generating function for a sequence of real numbers but we expressed those using complex. and that's just a tiny indication of a more complex phenomenon when in the generating functions that we look at sometimes, we have periodic fluctuations in the answer. Those periodic of fluctuations are expressed often in terms of a complex arithmetic of this sort. Now, in this introductory lecture, I'm not going to go too much further other than to say that, that phenomenon is out there. and actually for many of the examples that we've considered, we don't have this kinds of period disciplines. so, I'm just going to point it out on this one slide for now. things can get complicated but they can be fully understood and there's quite a bit of information in the book about these sorts of problems. And we'll return to a few of them later on in the course. so in summary we have this theorem which is like the partial fractions theorem. It is the partial fractions theorem and it, it works for you know, complex numbers as well as reals. there's a lot of symbology on this on this slide. And I'm not going to read every symbol just to express the idea that if you've got a rational generating function, then you have a polynomial g of z in the denominator by definition. And what you care about is the roots of that polynomial. now those roots, there are a certain number of them, and they're going to have multiplicity. like the 1 minus 2z squared, would be multiplicity 2. if the polynomials of degree t the roots times their multiplicity is going to add up to to t the multiplicities of the roots is going to add up to t. Maybe they're all different in which case, there's t different terms. if the multiplicity is mi, there's going to be a polynomial that is of degree mi minus 1 in N. but most of the time if they're unique you're just talking about 1 over the root to the Nth power. and so we get a expansion of the generating function as a power of roots using partial fractions. and, and there's constants that depend on the function in the numerator and if you happen to get complex roots, you're going to get periodic behavior as I saw. Now, I'm not going to we don't apply this theorem in this form there's too many things going on. as I mentioned, most of the time, we can assume that there's, it, we will encounter functions where there's a unique pole of smallest modulus. And that's the only one that we worry about. And we will, I don't want to worry about its multiplicity, like with the 1 over 1 minus 2 z squared, example that we did. so it's a typical case, it's the unique pole of smallest modulus. In that case, the coefficient of z to the N in the ratio of those two polynomials, is just a constant times whatever root to the N times N to the multiplicity minus 1. and not only that, we can explicitly compute that constant using l'Hospital's rule. there's an explicit form for that constant and there's that's going to be an effective way to extract coefficients for many of the generating functions that we've seen. So, for our first example the pole of smallest module is at 1 half. and that's for our second example that we're, that factors into it, 1 minus 2z squared. and so that root appears with multiplicity 2 plug into the formula, you get c plus 1 3rd. And so, this is a transfer theorem that tells us immediately that the coefficient is e to the N and that rational generating function is 1 3rd N2 to the N or generating function for the Fibonacci numbers. and again phi is, the root closest to the origin is, it's phi hat do you remember your Fibonacci numbers, and 1 over that is phi. Go and compute the constant and we can get immediately from this transfer theorem the asymptotic growth of the coefficients simply plugging into that formula. or this is a more complicated one which is the generating function for the number of binary strings that don't contain four zeros in a row. you might have to use symbolic math package to get the root that, that's closest to the origin. and 1 over that root is 1.9276, then you can plug in to get the constant. and again you immediately get the asymptotic growth. so that's the transfer theorem for rational generates functions. And this theorem really amounts to an algorithm. so nowadays we don't compute roots for something like that by hand we use a computer algebra system. in effect, the whole thing is embodied so if you go to WolframAlpha, which is a, a free service and you type in give me a power series for z over 1 minus 3z plus 4z cubed. it'll tell you that exactly that answer that we computed. 1 9th z to the N times minus 1 is 1 to the N plus 2N plus 3 to the N. now we'll pick off the largest term but still that idea of doing the partial fractions, doing the expansion is an algorithmic procedure and people have coded it up and computer algebra systems have that. Now, computer algebra is not really a topic of this course although we use it but things can get complicated. and I tried finding that series in WolframAlpha for the set of binary strings with no occurrences of four zeros in a row. and it said well maybe you should buy a copy of our software that we charge for. and that's fine or, or maybe there's another package that does this. the point is it's a, it's an algorithm for a particular problem there's a way to get there. we'll talk a lot more about this in our next lecture. another thing about this is and this was covered in part one in this course and it's on page 157, 158 of our Introduction of Analysis of Algorithms book. Is that another way to look at this idea of extracting coefficients from rational rational functions using partial fractions is, it's an algorithm for solving linear recurrences. because what we do to solve linear recurrences is just make the recurrence valid for all and multiply both sides by z to the M and sum on N. that gives us an equation satisfied by the generating function. That equation if the recurrence is linear, if the co, if the coefficients are constant that equation is going to be rational. It's going to be ratio of two polynomials. So then, so then this theorem that extracts the coefficients from a rational function is going to solve the recurrence. And again computer algebra systems nowadays it's just the same problem in a different form. we'll solve linear recurrences for us. But what I want to focus on is analytic combinatorics where we want to use that transfer theorem to get us asymptotic results immediately. so if we have the combinatorial class, which is all binary strings with no occurences of four zeros in a row, which we talked about in the first lecture. And we have a specification using the combinatorial construction where its binary string of less than four zeros, the empty or with a 1. And then another string of that type that defines the class of all such binary strings, and then, the symbolic transfer immediately takes that specification to this generating function equation. that generating function equation if we solve for b4, gives us the ratio of two polynomials, that's a rational function. then we can apply the analytic transfer theorem for rational generating functions to immediately get the asymptotic result. Now, we have to compute a root, there's a, a little bit of work. There's no avoiding that but the the actual math is just applying a transfer theorem. we're going to see many more examples of this in the next lecture. So, rational generating functions, we know how to do analytic combinatorics. Next, we'll move on to the next more complicated kind of generating function.