Next we'll look at coefficient asymptotics.

How do we get estimates of the coefficients of the generating functions

that are so easily obtained through the symbolic methods?

Fortunately, it's the case that we often can immediately get the coefficient

asymptotics through general analytic transfer theorems.

And we've already seen some examples of transfer theorems that work for

a lot of cases.

For example, Taylor's theorem is a transfer theorem.

If you have a generating function f(z) and

you know its derivatives, then coefficient of z to the n in f

of z is the nth derivative evaluated at 0 over n factorial.

And for lots of functions, that's how we extract coefficients.

That how we get started with generating functions.

We saw another example with rational functions.

And we talked about that in the generating functions lecture and

also the asymptotics lecture.

This is a special case, just for simplicity, on this slide.

If f(z) and g(z) are polynomials then the coefficient of z to the n,

and the ratio of f of z to g to the z, depends on

the largest root of g, of the denominator.

And if 1 over beta is that, then this expression gives the,

it should be asymptotic of the coefficient of z to the n and the ratio of those two,

beta times f of 1 over beta divided by g prime of beta, beta to the n.

The growth is like beta to the n, and

that's the constant if that root has multiplicity 1.

And we have a better formula.

A more complicated formula that depends on the multiplicity,

if it's got a higher multiplicity.

So those are two examples of transfer theorems, and we use those.

The one I want to talk about today,

next is what's called a radius of convergence transfer theorem.

And that covers the problems that we talked about today and many others.

But actually, most of the transfer theorems that we use in real life

are based on complex asymptotics.

We'll talk about those in a lot of detail in part two.

But the radius-of-convergence one works for a lot of things, and

that helps give a coherent treatment of analytic combinatorics at this level.

So here's the theorem.

The idea of this theorem is that the function 1/(1-Z) seems to arise a lot.

In the common furrow constructions that we develop.

So this is 1- z to alpha power where alpha's not necessarily an integer.

The only restriction is that it can't be a 0 or a negative integer.

And it so gives us, it, in some sense,

it generalizes the ratio on, that I did before where G of z was a polynomial.

Now it's 1 minus z, raised to alpha power.

Coefficient of z to the n and f of z over 1 minus z to the n, alpha,

is asymptotic to f evaluated at 1 times n + alpha- 1 choose n.

And that's asymptotic to f evaluated at 1 n to the alpha- 1 over gamma of alpha.

Gamma of alpha is a constant I'll talk about in a second.

And I'm not going to go through the proof now, because most people are just going to

want to apply this theorem and not prove it, but it's not that difficult a proof.

Really it's a convolution that involves the generalized version

of the binomial theorem, and also, since the thing converges,

the sum of the first end coefficients converge exponentially to F(1).

That's the quick description of the proof of the first part, and

then the second part is standard asymptotics.

Just using the definition of the generalized binomial coefficient, and

it's function, the gamma function.

If you don't know what the gamma function is, here's just a real quick summary.

It's a way to generalize the factorial function.

It plays an important role in analytic [INAUDIBLE] and the analysis of

algorithms, because it arises in transfer theorems just like this one.

So for real Z, if you define this function,

gamma Z equals integral from zero to infinity.

T to the z minus 1, E to the minus t, dt, turns out

that function has the properties that we would want in generalizing the factorial.

For example, gamma of alpha plus 1 equals alpha times gamma of alpha.

Just like n factorial equals n times n minus 1 factorial.

So, and then if you work it out, gamma 1 equals 1.

So gamma of N plus 1 is exactly equal to N factorial.

So for integers, it matches the factorial, but

it always satisfies this property for any alpha.

And the gamma 1 equals 1.

And then one that comes up really a lot for us is gamma of one half.

If you want to compute gamma of one half, so

that Z equals one half in there, and then you get something like the normal and

you compute it to be the square root of pi.

And so again one half equals the square root of pi is a value

that we want to know, because we applied this thing with alpha equals one half.

The square root of 1 minus c.

So that the transfer theorem that works whenever we have a convolution of some

function where 1 minus c is the alpha, and that turns out not to come up a lot.

And just a little more generally, if

the radius and convergence is bigger than a rho and if a rho is not equal to zero.

So, it's just supplying this to zero of a rho and

plugging in zero of a rho in this theorem, then we get slightly more general.

We could do one over one minus zero of a rho to the alpha, and that pulls out a rho

to the n in the in the asymptotics.

So that's just the elementary calculation to see where that comes from.

So that corollary's the one that we'll really be interested in.

So, that's the theorem.

If we have a generating function of that form, we know the asymptotics.

And that applies to the two major problems that we've talked about in this

lecture for catalan numbers.

So T of z equals one over 2 of z one minus square root of one minus four z.

So there is a tiny complication, because the first term has to cancel out.

But ignoring that, what we're using is alpha equals one half in

this alpha equals minus one half, so

that's one minus z over rho to a minus one-half in the denominator,

that's square root, and rho equals a fourth, so that's square root of 1- 4z.

And then f in this case is just a constant, just the half out front.

And so we wind up needing gamma of minus one half,

and then that's 2 times gamma of one half, just because gamma of

alpha plus 1 equals alpha gamma of alpha minus 2 squared of pi.

Now you plug it all in.

And then maybe it's easiest to think about it by just multiplying both sides by z.

And then apply these exactly.

It is not hard to finish the calculation to show that this transfer

theorem immediately gives us the asymptotic of the catalan numbers.

So one transfer theorem to get the generating function.

Another transfer theorem,

the analytic one, to get the asymptotics of the coefficients.

And the same theorem, works for the derangements problem.

So, there are a number of generalized derangements, and

how we had this complicated function.

Not so complicated, with this transfer theorem.

Now we have alpha equals one.

We have rho equals one.

Our function is just e to the minus z, so all we need to do is evaluate f at one,

that's e to the minus one, minus one-half, up to one over m, that's h sub n.

And that immediately gives the asymptotic e to the minus h sub n.

So the two problems, and the first one, a lot of calculation to get there,

the second one, we don't even know how to get there immediately

through this analytic transfer theorem, we can get the result.

This is just really just the beginning.

What part two is going to be devoted to is the idea of really universal laws

that we can get from transferring theorems based on complex asymptotics.

And I'll just talk through one.

There's a lot of technical details, just to give you some idea.

If you have a system of combinatorial constructions where you have a bunch of

classes and they're all interacting, and

those operations indicated by OP0, OP1 up to OPt.

Now those can be sequencers or sum or product operations.

And you can create a whole linear system of combinatorial construction.

So, a very simple special case is the binary tree one,

where you got t on one side, and as e times t times t on the other side,

you can have a much more complicated thing, a cycle of binary trees of sets of,

well, not those, but linear combinations of

combinatorial classes, a whole system of combinatorial constructions.

Those immediately transfer to a system of generating function equations with

the symbolic method.

Well that's good.

But those generating function equations might be quite complicated and

difficult to solve.

But in fact, there is a method called Gröbner basis elimination

that reduces those all down to a single generating function equation.

And not only that, there's a theorem called the Dmota Lalley-Woods theorem,

that shows that there is an explicit solution to that equation.

That equation got the square root, this is in the complex domain, and

there is a process called singularity analysis,

that immediately give the simple esthetic form.

So any combinatorial construction is asymptotic to A over 2 squared

pi n cubed b to the n where a and b are constant, so

we can explicitly calculate from the construction.

It's an amazing universal law, and

you can find in older mathematical literature hundreds of papers that come up

with these kinds of results that this one process covers,

and that's just one example of universal laws that we see in analytics [INAUDIBLE].

There's many more.

So, that's an introduction to coefficient asymptotics.

Coefficient Asymptotics

Analysis of Algorithms

与讲师见面