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.

Â