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. 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. 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. we just have the one term each one is, 1 over alpha minus z. 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. 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.
