So that Hankle representation of the gamma function leads us to our starting point, which is asymptotics and what's called the standard function scale. and we'll, we'll just do, the leading term for most of this lecture the way we've been doing. but, all of this, all of these theorems can be taken to any asymptotic decision. and so, it's a, it's a very simple theorem that is actually useful to apply in lots of instances. So, if you have any real alpha actually any complex alpha as long as it's not zero or negative integer. then you can get an approximation to the coefficient of z to the n, and 1 over 1 minus z to the alpha. and that is exactly n to the alpha minus 1 over gamma to the alpha. so we'll look at the proof in the next couple of slides but this is the kind of scale that we're looking at. Lets go up by a square root at a time. So, we know one over one minus z coeffecient of z to the n is one and one over one minus z squared coefficient of z to the n is n plus one. And cubed is n squared and so forth So going down this way, we add a power of n. and so with this table is going to show, is what happens with square roots. So, if we take alpha equals one half we know gamma of one half equals square root of pi. We get n to the minus one half, so it says the coefficient of z to the n in 1 over square root of minus c is 1 over square root of pi n. now if we take alpha equals minus one half, then we get n to the minus three halves. and then we now have gamma minus one half, which is that extra 2. So, it's, coefficient of Z to the N and square root of 1 minus Z, is ,uh, asentog[/g] to minus 1 over 2 squared pi, N Q. that's what, the formula tells us. So now, uh, [COUGH] when down here we're going up by factor of N every time we jump, jumped 1 and the exponent same way, factor of N. So that would, another factor of N, so now it's Square root of n to the 5th and then a slightly different constant depending on properties of the gamma function. And then going the other way it's 1 over square root of n, now square root of n and again with a slightly different constant. So, except for the negative integers, for the negative integers. It doesn't make much sense to talk about the coefficient of z to the n of 1 minus z, because most of them are zero. So, negative integers have to be an exception but everywhere else we have these things here analytic. And we have the theorem gives us the on any function in this standard scale any alpha it'll give us approximation of the coefficients. So, that's very powerful, and very useful and again, the proof of the theorem extends to give a full asymptotic expansion, in decreasing powers of n. with that with that leading term, n to the alpha minus one over gamma of alpha. So, it's a very generally applicable and powerful theorem. So, for example, with this theorem we can take our generating function for the Catalan numbers. And immediately know from the theorem, the asymptotic expansion that we derived with so much pain. using Sterling's approximation binomial coefficients and other things. It's an immediate transfer theorem from the standard scale out to the asymptotics of the coefficients that we can apply broadly. now I'm not going to go through the full proof. Remember, I acknowledge that we're entering deep water. this one's not too bad what we, the key concept in the proof Is to figure out how to remember the square root function. And the way that it goes with the negative integer. But we take 1 minus so it's in the positive. There's going to be this area where there's going to be a line or a slit where the function is not analytic, where all the essential singularities are. And what the proof does is define a contour of integration that ignores that. and all we need to do is be sure, that inside that contour of integration, we have a analytic function. and we know that there's these areas where it's not analytic, and we don't think too much, about what's outside. but that's the, the setup. is that we want to define a contour of this type called a, a Hankel contour. and we make the slit with 1 over n for to get the asymptotics to work out. so, the sketch of the theorem is to to get the coefficient of Z to the N in 1 minus Z to the minus alpha, we use Cauchy's coefficient theorem. It says the coefficient was Z to the N in the function. 1 over 2 pi i, integral over small circle where it's analytic, which, the origin's fine times dz over z to the n plus 1. That's the basic Cauchy coefficient formula and then what we'll do is change variable To z equals 1 plus t over n in that formula. So, then if we make that change a variable, then n to the minus alpha comes out and a minus to the minus alpha stays in, zvn plus 1. becomes that 1 plus t over n to the minus n minus 1, so the little algebra there with that change of variable. But that pulls out the n to the alpha minus 1 term that we're looking at. and then we take our contour of integration and through the an, integral property, we can deform it any way we want as long as we don't go over a f-, a pole. And so we deform it into a Hankel countour. and then take r to infinity which leaves us with a slit like the one in the Hankel representation of the gamma function. and indeed what we do is this integram is just like the one in Hankle's formula for the Gamma function. And that gives us the gamma of alpha. Now this is just a sketch of the proof, and there's a lot of details to check in this proof. but you, you can do that with some time studying the book, depending on your mathematical level of mathematical sophistication. And easily follow this proof. It's a standard proof and not complex analysis to establish this standard function scale. It comes right from Hankel's formula for the gamma function. and, but otherwise is if you're interested in just applications of analytic combinatorics it's an excellent transfer theorem to know. If you have a third route of 1 over 1 minus c whatever alpha that you have, you have asymptotics in terms of the gamma function. And then it's just a matter of computing values to the gamma function. And in a great many cases it's alpha equals one half as we'll see. because of properties and the way that we construct common [UNKNOWN] classes. The generating function equations we get have contraints that lead to this gamma of one half. exactly as this theorem, so that's a very broadly useful function that it can be used in many applications. and actually, we can extend it include logarithmic factors. So, if we add a factor 1 over z, log 1 over minus z to the beta then it brings out a log in to the beta term. and I'm definitely going to skip that proof in lecture but it's a a straightforward extension of the previous proof. once you get the previous proof you can get this one and again knowing this theorem. say in the very first lecture for analysis of algorithms when we analyzed quick sort. we can immediately get 1 over 1 minus c, logarithm 1 minus c equals log n. Or, uh, [INAUDIBLE] squared, log 1 minus c equals n log n. This transfer theorem gives us the coefficient of [INAUDIBLE] asymptotics immediately for lots of generating functions that arise in practice. and again, so that's another one and then there's a table in the book that actually does it for all the alphas. And betas and for alpha and one-half, just like on the table that I showed you. But that's a very powerful and useful transfer theorem. so as I mentioned just the promise of analytic combinatorics allows us to work at a high level with constructions. immediately giving generating function equations by the symbolic method. and then a transfer theorem that takes those generating function equations right to coefficient asymptotics. same for we looked at cycles in permutations or in earlier lecture. and came up with the generating function, 1 over 1 minus z log 1 over 1 minus z. Knowing the standard function scale, we can immediately take that to get the coefficient asymptotics. log in, no computation needed at all. Oh general transfer theorem, that's useful in lots of applications. Now these two examples well, particularly this one, elementary, and there's many ways to get these kinds of results. Again, as usual when we look at variance, and we look at more complicated things. we can still use the same transfer theorem to quickly get the result without any calculation, with very little caluculation. And we'll see many, many examples of that in the next lecture. That's an example the standard function scale, which is our starting point for singularity analysis. [BLANK_AUDIO]
