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]