0:04

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.

Â 0:56

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

Â 1:20

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.

Â 3:13

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.

Â 3:59

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.

Â 4:48

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.

Â 5:18

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.

Â 6:29

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.

Â 8:46

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.

Â 9:17

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.

Â 9:31

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.

Â 11:10

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.

Â