0:00

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]

Â