0:00

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.

Â 3:42

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.

Â