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.