0:05

Well complex integration, and all the properties of complex numbers and

functions, and the complex plane that we've been discussing might seem very

abstract, and quite far removed from the analytic combinatorics that is our goal.

and in this section, we're going to see how to apply those abstractions to get us

down to specific methods of getting accurate estimates, asymptotic estimates

of coefficients. and it's based on a much more general

class of functions than the rational functions, which are ratios of two

polynomials that we al, already considered.

its com, complex functions that are the ratio of two analytic functions.

Well, rational functions which are polynomials, are also meromorphic.

But now we're allowing functions like e to the minus z over 1 minus z, over, 1

over 2 minus e to the z. and so a ratio of, of two analytic

functions of any description, a much broader class of of functions.

Now approach, is, going to be to make use of contour integration, to, expand the

function into terms where we can get the coefficients.

and then focus on the largest term to approximate.

this is the same approach as we used for our rationals, but we're going to have a

much more general, transfer there. so first the, the definition.

so function is, is meromorphic if it can be represented as the ratio of two

analytic functions at, at a point in the neighborhood.

Now there's a lot of useful facts about meromorphic functions.

and again sometimes there the definitions in terms of these facts, and these things

are, are all related in complex analysis. But, let's, lets call them facts, that if

you have a function that's meromorphic, then you can expand it in terms of it's

just like the analytic expansion. except we can expand it in the negative

direction, in terms of negative powers of z minus z0 all the way up to some finite

level. and then the smallest term used in the

expansion or the biggest exponent 1 minus z minus z0 that's said to be the order of

the pole. so the singularities of the places where

the denominator is 0 or the poles, and the, where those where those things

happen allow us to do an expansion of, of this sort.

depending on, the order of the pole, or how big the polynomial is, locally.

and just to show this expansion, if, if you have a 0 of the denominator, then you

can write g of z, as z minus 0 to the n times, some analytic function.

And then just expand the analytic function f of z over that one, fz 0, and

that's how you get that kind of expansion.

not, not difficult, not to see at all. Now it turns out that the coefficient of

z over, 1 over z minus z 0 which is h minus 1.

that one turns out to be particularly important, and we'll see why in just a

minute. That's called the residue of the function

at the point. And, we have a special notation for that,

are the residue is equal z0, is h of, h of z.

so we can expand the function both ways from meromorphic and a we have a concept

of, of a residue. so if we multiply by z minus z0 to the n,

then we get something that's analytic. That's another way of just saying this,

here. and another way to say it, is that a

function is meromorphic, if its analytic, except for a set of isolated

singularities at its poles. And at those places is got expansions of

this type. that's, that's the characterization of

metamorphic functions that we're going to take advantage of.

And again, without going into details of complex analysis, I won't talk about

formal proofs of all these types of things.

but this sketch gives an understanding of the kind of functions that we're talking

about. They can be expressed as the ratio of two

analytic functions, and they can be expanded always in this form for each

pole near each pole. so in the functions that we've seen are,

it's usually quite easy to establish that they're meromorphic, and where the poles

are. so for example derangements.

That's meromorphic except there's a pole where z equals 1.

If you multiply it by 1 minus z, you get an analytic function.

in this one, it's you know, 1 over 1 plus z squared, it's meromorphic everywhere,

except at plus or minus i. For this one, for, this is the one for,

for set partitions there's a bunch of poles at 1 at 1 half, all the way up to 1

over r and so forth. So in practice it's fairly easy to

determine that the function's meromorphic, it's the ratio of two

analytic functions. And it's fairly easy to find the poles.

It's the places where the denominator is 0.

that's, that's really the key concepts that we need to know.

and this is what these things look like when we plot them so for example, 1 over

1 minus z to the 5th has five poles. those, those are called the, the roots of

unity and actually I'll talk some more about them later on.

and these are just plots of what the these other functions that arise look

like. And we'll look at more implications of

these later on. For example 1 over 2 minus e to the z,

that's going to pull whenever e to the z equals 2.

Well, if z equals log 2, then e of z equals 2.

But if you add 2 pi i for 2k pi i for any value of k, you also get a pole.

e to the log 2 plus 10 pi i, is also 2, so you're going to get a pole.

And then our plots, the poles turn up as black dots, because they get larger and

larger as you get closer to the pole. And we'll, revisit these kinds of

diagrams, later on. OK.

So the first idea is to extend the Koshi formula to integrate any curve that goes

around the pole. and so this is a result for a single

pole. If can have a meromorphic function, and

you've got a closed loop within its domain.

And there's a single pole inside that loop, and the interval around the loop is

2 pi i times the residue at, at the pole. that's the coefficient of h to the minus

1. and that's easy to prove from the things,

that we've seen. so for example if f of z is 1 over z then

that's got a pole at 0, and the residue is 1.

That's the coefficient 1 over z and we saw that the integral of 1 over z dz is

just 2pi i. just using the polar coordinates.

As such, you know, that's an easy example.

and let's look at a more, complicated example.

So what we can do is because s is a pole, we, we can expand h near that pole, and

write it as a power series of this form, starting at z minus s to the m, and and

going on. so and that's really the essence of being

meromorphic, is that you can write such an expansion near a pole.

so now we can then deform our curve. by the Koshi theorem to a circle that is

centered at s, and has no other poles. so because there's no other poles in

there, and then just integrate. so if we plug in the expansion and

integrate, then what's going to happen is, and we saw when we did our

integration example 5, that they're all 0, except for the one that is 1 over z

minus s. that's the only one that, that doesn't

cancel to 0. so that's what's left is just to go back

and look at that integration example. they all go to 0, except 2 pi i times the

the residue. so that's a single pole.

it gives us the residue the value of the integral is the residue at that pole.

so and this is a really significant kind of calculation, because what it says is

that the local properties of a function near the pole is connected somehow to

properties in the function elsewhere. In this case integral along a curve that

might be distant. it doesn't matter what the curve is, it's

only the local properties of the function near the pole that matter for a

meromorphic function. So generalizing the integrator around a

pole, we have what's called the Residue thereom.

10:31

If you have a meromorphic function, and you have a closed loop and it's where

it's defined to be meromorphic, then an integral around that loop, is equal to

sum of the residues, 2 pi i times the sum of the residues.

so take the residue i, at every pole and add them all up you get the value of the

integral. then, here's just a sketch of that proof

it's actually almost all of it. what we're going to do is we're going to

look at small circles, centered at each pole.

and what we're going to do is define a path.

this is kind of an intermediate version of the path.

That's the same as our original path, except it goes in and around, and out

again for each pole. In fact it'll do the perfect small

circle, and out again. So for every pole, we'll take our

original path, but for every pole we'll go in and grab it, and go and go out.

Now, actually in this curve, the poles are all outside the, the path.

So the integral around the path is 0, where we arranged it so their all

outside, even when it's, a circle like that, it's really outside the path.

So the integral 0 of the in and out lines cancel out.

One going one direction, one going the other way, direction.

And the circles is, the residues, by doing one pole at a time.

so that, immediately gives the result, that the, integral, around the path is

equal to, some of the residues. so that's a quite a general and powerful

theorem, and then we're going to be able to make, take advantage of that to get

coefficient asymptotics for meromorphic functions.

In fact the transfer theorem for that gives nearly exact results for

meromorphic functions. is, a direct application of the residue

theorem. So, the theorem says, if you have a

meromorphic function and you know the poles, then the coefficient of the

function is just polynomials over each pole to the nth power where the degree of

the polynomial has to do with the order of the pole.

And again I'll just quickly sketch this proof.

so now what we're going to do, is take an integral around a big circle of radius r.

we're going to take our function, and we're going to divide by z to the n, n

plus 1. and so by the residue theorem the value

of that integral is some of the residues inside.

and some of the residues inside, gives exactly these polynomials.

And just for example, if the pole of order 1, then the function grows like

this constant over z to the minus alpha and so therefore, the residue of the

function of over z to the n plus 1 is the same as the residue of this c over z

minus alpha to cvm minus 1. and that's just the z goes to alpha, that

just gives you alpha to the m plus 1. That's the coefficient of 1 over z minus

alpha. And there's is simply c over alpha to n

minus 1, n plus 1. You do that for every pole if it's of a

higher order, then you start to get the polynomials.

And I won't go through that detail. because we'll see another way to do that

in just a minute. so, value of that integral is is the,

these polynomials are a pole to the nth power and then it's easy to bound that

integral. because the value of the function on the

circle is going to be a constant that doesn't depend on n.

So when n gets exponentially small nm. so that's a quick sketch of a theorem

that gives us with exponentially small error a very accurate term equation for

the coefficients of a meramorphic generating function.

Now, but this is complicated. And what we what to do is, focus on the

leading term in the same way, as we did for polynomials.

but before doing that, we have to consider a few points.

So first one is some of the roots might be comp, complex.

Is that going to give complications? and the answer is it surely is, because

the leading term is going to depend on the distance for the origin of the pole.

and all the poles, are going to contribute to the leading term.

So for example, there's the nth roots of unity, so those are just e to the 2 pi ik

over n, of course 2 pi k over n plus i sin 2 pi k over n.

If you raise any one of those complex numbers to the nth power you get 1, and

they're all distance 1 from the origin. and so I already showed 1 over 1 minus z

to the 5th. So there's 1 over 1 minus z to the 25th.

there, so you have 1 over, those numbers to the nth power.

All of them, and they're all the same distance from the origin.

And we already saw an example of this phenomenon, when we did, the rational

generating function for 1 over 1 plus z squared.

that's a root of minus 1. so there is plus and minus i.

And then we saw that, these things mix up, so that the coefficient of z to the

end fluctuates and oscillates. so, you have to consider, all the poles

that are the same distance from the origin.

and that seems like that's going to be a problem because this kind of situation

might arrive and give us complicated expressions when we're trying to do

analysis of this sort. but, fortunately for combinatorial

generating functions, it's very often the case that's there's one route that's

closer to the origin, than all the others.

17:08

And not only that, there's a theorem called Pringsheim's theorem.

That says that if you've got a generating function that has non-negative

coefficients, and of course, the generating functions that we get for

analytic commenotoriac's always have non-negative coefficients, because

were're counting things. and then, if it's got radius and

convergence r, then the, the point z equals r, that's a real number, it's the

smallest positive real root. That one, is a singularity of the

function. Hm, so, you, it means that, for very many

of the cases that we need to consider. all we need to worry about, is the real

number that's closest to the origin. And the asymptotic growth, is that number

to the nth power. So for example, this is a generating

function, that we get when considering strings containing, no occurrence of four

zeroes in a row. It's got poles out there, but there's one

that's closer to the origin, and that's going to to determine the asymptotic

growth. And not only that, the contribution from

the other terms are exponentially small, they really can be safely ignored.

So, that's the implication, only the smallest positive real root matters, if

no others have the same magnitude. Now, if you do have a bunch of roots that

have the same magnitude, you can get really complicated periodicities.

and you can read about that starting on page 266, in the book if you're

interested. It's called the Daffodilemma, because the

curves that we have to consider maybe look a little bit like a a daffodil.

It can get very complicated. but so many of the combinatorial classes

that we've considered this doesn't, this doesn't come up

There's, a single root that's closest to the origin, and therefore, it's real, by

Pringsheim's theorem. so, that's going to lead us to a much

simpler theorem for the leading term, the asymptotics, the meromorphic generating

functions. so here's the theorem, it's the same

statement, conditions as for the general theorem.

meromorphic in a, a closed disc and size r, and it's analytic at the origin, and

everywhere on the circle. if alpha, is a unique closest pole to the

origin, that means all the other poles are furthered.

then it's real, and not only that, we know the coefficient asymptotics.

It's of the form, a constant times beta to the n times n to the m minus 1, where

m's the order of alpha. we have an explicit expression for the

constant. and Beta is 1 over alpha.

that's a theorem in that, this is just a quick proof sketch so near the pole we

can expand the function in this way. And again, since it's a poll of order 1,

where you're just going to prove a frame equals 1.

20:33

so you want to calculate h minus 1, one thing you can do, is take the limit z

goes to alpha, of alpha minus zh is z. and there are, the, approximation and I

add alpha to the function is approximated by h minus 1 over alpha minus z.

so then we can just go ahead and expand it.

So 1 over alpha, so it's h minus 1 over 1 minus 0 over alpha, 1 minus 0 over alpha,

is sum zdn over alpha to the n. and that gives us the, uh, [COUGH] the

coefficients that, the asymptotic growth is 1 over alpha to the n, and then the

constant is, well in this case m equals 1.

so it's minus 1 times f of alpha over, well, we'll look at this proof of exactly

where this constant comes from in a minute.

that's all going to be done on the next slide.

So just a couple of notes about this. So so I'll complete this, proof on the

next slide. So as I mentioned, the error is

exponentially small. now, if the, if they're close to the same

distance, there might be periodicities for some problems that you might have to

look at. you know, often the next term does

involve some kind of periodicities. now and the other thing to notice is, if

you go back and look at our transfer theorem for rational functions it's the

same. well and it ought to be the same, because

if f of g and g of 0 polynomials, you get the same kind of result.

but still, it's quite different paths, to this same result.

the residue calculus in Koshi's theorem and so forth, gives us the asymptotic

result that we need for a meromorphic functions.

And again, we've been through quite a bit of complicated abstractions in this

lecture. but really what you need to remember is

these simple formulas. and in very many cases, as we'll see in

the next lecture, it's simply a matter of, of plugging into these formulas to

get the coefficient asymptotic's. The essence of analytic commonotorics, is

we start with a commenotorial construction, and that gives us a

generating function equation. And then an analytic transfer theorem

like this takes, the generating function equation and immediately gives us the

coefficient asymptotic's. now before I go on, I want to justify

this constant that's the coefficient. so I mentioned before that when we

compute the constant if the poles of order 1, just by taking the limit of

alpha minus zh of z. Well, if you take that limit, then you

can use L'Hopital's rule, take the derivative of both sides.

Uh,and so that's alpha minus z times the derivative of f, plus f times the deriv

alpha minus c, which introduces a minus sign, on the bottom is g prime over z.

But, the pole of order 1, g prime of z is not going to be 0, so we can just plug in

alpha. It kills the first term, and we get minus

f of alpha over g prime of alpha. So that's an easy way to compute the

coefficient. if it's of order 2, then we have to apply

l'Hôpital's rule twice, and so we can do the expansion as before.

We have two terms now but we just take the leading term, and now our leading

term we're expanding 1 minus z over alpha squared.

and then that, because of the square, brings in a factor of n, into the leading

term, simply by elementary generating function exponentially.

and then the rest of the calculation is using l'Hôpital's rule twice.

take the first derivative, take the second derivative.

and if it's of order 2, the second derivative is non 0, and then taking z

equals alpha, kills all of the terms except 1.

and we're left with 2 f of alpha over g double prime of alpha, and then you can

convince yourself from that, that's of order m.

Then our coefficient that we need is minus 1 to the m, and f of alpha nth

derivative of a g, evaluated at alpha over alpha n, that's the coefficient.

and then the growth is, n to the n minus 1 over n, where m's the order of the pole

1 over alpha to the n. so a simple formula for the coefficient,

in terms of the order of the pole. And again there's a lot of calculations

here but I really think the bottom line is you can see some light at the end of

the tunnel. we've done a lot of calculations but what

we have in the end is for many, many examples.

of, First of all, we have an analytic transfer to take a meromorphic generating

function, into its asymptotic growth form.

In most of the cases that we're going to consider, that we have considered in

terms of commenotorial classes, the poles are order 1, so the growth is a constant

times Beta to the m, where beta's 1 over the closest route to the origin.

So all we have to do, is compute the dominant pole.

Now that's the smallest root where the denominator's 0.

maybe we have to use a ah, [COUGH] math package to do that but many times it's

simple, it's elementary. and you should check that no other no

other poles have the same magnitude, that's usually very easy, you usually

just do it with a plot. and then what's the residue from the

theorem? It's just f of alpha over g prime of

alpha an easy calculation. And, then the constant is just now, it

might, you might worry by g prime being 0, well if your prime is 0, then its not

order of 1, so you'll just have to adjust to do the order's of mk's, but we have a

formula for that, too. again that, doesn't come up, in a great

many of the commenotorial classes that we consider.

So the constant then, is just h minus 1 over alpha.

And the exponential growth factor, beta, is just 1 over alpha.

so that's the bottom line, is we've got a very simple method to transfer from

generating a function equation into constant times exponential growth factor.

so there has been no doubt a great deal of difficult and complicated mathematical

material in this lecture. but really the purpose of it, is to

persuade you that there's rigor in our being able to do these kinds of analytic

transfers. most of the time in applications we can

just use it without going back to the detail in difficult theorems that we've

talked about. so, just to give, just a couple of

examples so if our meromorphic function is rational like z over 1 minus z

squared, well there's, alpha, that's the root.

So it's phi hat, which is the same as 1 over phi, so the exponential growth's

going to be phi to the n. and what's the constant?

it's phi hat over 1 plus, 2 ha, 2 phi hat, which is 2 phi hat squared 5 minus

1. So that's just square root of 5.

and then, to get the coefficient we divide by phi n, which takes that out.

So that immediately gives the asymptotic's for that generating

function, which comes up in a couple of combinatorial classes.

this is the combinate generating functions for derangements.

so the pole is at 1, so f of alpha is e to the minus 1, is 1 over e.

g prime of alpha, is just 1. So, it's just 1 over e divided by 1, 1 to

the n. coefficient of z to the n, and hz is 1

over e. or to generalize, to generalize

derangements. so in, in that case f of, alpha again is

1. That's where the pole is, there's only 1

of them. evaluate the numerator at 1.

you get e to the minus h3, or one over e to the h3.

exponential growth is 1 to the n, which goes away, divide by alpha as 1.

so immediately we get the coefficient with a very simple calculation.

so just as an example, here, here's what we're going to be doing for the entire

next lecture is looking at how analytic combinatorics gets us from a

combinatorial specification, down to asymptotic results.

So we talked about generalized derangements.

That's a combinatorial construction and the symbolic method immediately gives

that generating function. And now, we have an analytic transfer, to

take us immediately from that generating function, right down to the asymptotic's

of the coefficients. you don't need to know too much about

Koshi's theorem or residues, or any of these things in order to be able to apply

this analytic transfer theorem. so, in the next lecture we're going to

see many, many, many more examples of this general idea that we can have an

analytic transfer that works for a, a broad variety of generating function

equations, and takes us right to the coefficient asymptotic's.

30:38

Ah, [COUGH] so just in terms of the general form of the coefficients that I

talked about at the beginning of this lecture.

and the first principle of coefficient asymptotic's is the location of the

singularities, tells us the exponential growth.

And the second one, is the nature tells us what about the sub, sub-expotential

factor. For meromorphic functions, if the

smallest real root is alpha, then the exponential growth factor is, 1 over

alpha. It's that location of the singularity,

closest singularity to the origin, that gives us the exponential growth.

And if it's a pole of order n, then it tells us the expo, the sub-exponential

factor is a polynomial n to the m minus 1.

that's a very, very general statement, and not only that, we have the specific

way to compute the constants as well. That immediately gets us, accurate

asymptotic results. And again, next lecture, you'll see many,

many, examples of this. I just want to to finish with, an idea

that this isn't, this approach to combinatorial analysis is, controversial

in some circles. so, for example, this is a quote from,

Riordan's book, which is a very important and influential book in combinatorics.

And what he said is that generating functions belong to algebra, not

analysis. so it's all about, using, manipulating

generating functions, and then setting coefficients equal, to learn things about

commentorial objects. and we saw some examples of that, in part

one of the course, early on, for those of you that took part one.

Like the Vandermon Convolution which is a sum on convolving polynomial

coefficients, that's easily proved via generating functions.

And what Reardon said in his second book, commentorial use recurrences generating

functions and such Transformations, as the Vandermon Convolution.

Others, that means people who are not combinatorialists, and so they should be

able to do what they want, but Riordan says, to my horror, they use contour

intervals, differential equations, and other resources in mathematical analysis.

Not sure what he means by, to my horror. But I can remember reading, quotes like

this and, Riordan's not the only one, as a student, and being completely, really

confused, about what to do. even for derangement's if you're looking

for the coefficient of z to the n, and e to the minus z over 1 minus z, you have

to do a convolution. and you have to do some reasoning with

that convolution, to get to the asymptotic result, 1 over e.

I can remember first learning these kinds of manipulations, and being a little

mystified by how we we get to 1 over e, particularly since it's such an accurate

result. And that's just for a derangement's which

are permutations without singleton cycles.

if you had a generalized derangement's like permutations without cycles of

length 1, 2 or 3, then you've got a four-way convolution.

how are you going to get from this kind of formula to the asymptotic result 1

over e to the 1 plus 1 half plus 1 1 3rd, a very simple asymptotic result.

and I still to this day, don't understand what Riordan's plan would be for trying

to solve this problem. A little known many, many more general

problems that we're able to address by using contour intervals, and other

resources of mathematical analysis. That's precisely what we're doing in

order to get simple way's to derive asymptotic estimate for enumerating, and

studying property of a very broad variety of combinatorial classes.

and next time I'll certainly convince you of that.