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 method. 
fortunately it's the case that we often 
can immediately get the coefficient 
asymptotics through general transfer, 
analytic transfer thorems, and we've 
already seen some examples of transfer 
thorems that worked for a lot cases. 
For example, Taylors thorem is a transfer 
thorem. If you have a generating function 
f(z) and you know it's derivatives. then 
coefficient of z^N and f(z) is the nth 
derivative evaluated at zero over N 
factorial and, for lots of functions 
that's how we extract coefficients. 
That's 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^N and the ratio of 
f(z) to g(z) depends on, [COUGH], the 
largest root of g, of the denominator. 
and if one over beta is that, 
then this expression, 
gives the it's should be asymptotic of 
the 
coefficient is z to the n in the ratio 
that's two beta times f of one over beta 
divided by g prime of beta, beta to the 
n. 
The growth is like a beta to the n and 
that's the constant if that root has 
multiplicity one and that we have a 
better form a more complicated formula 
that depends on the multiplicity if its 
got higher multiplicity. 
So those are two examples of transfer 
theorems. 
And, 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've 
talked about today and many others. 
but actually most of the transfer 
theorems that we use in real life are 
based on complex asymptotics. 
and we'll talk about those in a lot of 
detail in part two. 
but the radius and 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 thorem. the ideal this 
thorem is that, the function 1 / 1 - z 
seems to arise a lot, and, the 
commonaltoric constructions, that we 
develop, so this is 1 - z to alpha power, 
where alpha's, not neccessarily, an 
integer, the only restriction is that it 
can't be a zero or a negative integer. 
And it, so gives us the, it in some 
sense, it, it generalizes the ratio on 
that I did before where g(z) was a 
polynomial. 
Now it's 1 - Z z, raised to alpha power. 
Coefficient of z to the N and f(z) / 1 - 
z alpha is asymptotic to f evaluated at 
one times N plus alpha - 1 choose N. 
And, that asymptotics to f evaluated at 1 
N to the alpha - 1 over gamma of alpha. 
Gamma of alpha's a constant and I'll talk 
about it 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. 
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 N coefficients converge 
exponentially to f(1). 
That's the, quick description of the 
proof of the first part. 
and then the, the second part is standard 
asymptotics. 
just using the definition of the 
generalized, binomial coefficient. 
And this 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 
combinatorics 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 one 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 one 
equals alpha times gamma of alpha. 
Just like N factorial equals N times N 
minus one factorial. 
so and then, I, we work it out. 
gamma, gamma one equals one, so gamma of 
n plus one is exactly equal to n 
factorial. 
So for integers, it matches the 
factorial. 
but it always satisfies this property for 
any alpha and so gamma one equals one and 
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 takes 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. 
[COUGH] and so again one-half equals 
square root of pi is a value that that we 
want to know because we applied this 
thing with alpha equals one-half, that's 
square root of one minus z. 
so that's a transfer theorem that works 
whenever we have a convolution of some 
function with one minus e to the alpha. 
And that turns out not to come up a lot. 
just a little more generally if the 
radius of convergence is bigger than a 
row and if a row is not equal to zero, so 
just applying this to zero of a row, plug 
in, in zero over row in this theorem then 
we get slightly more general. 
You could do one over one minus zero over 
row to the alpha and that pulls out a row 
to the end in the [COUGH] in the 
asymptotics. 
so, 
And that, that's just an elementary 
calculation to see, where that comes 
from. 
so that corollary is the one, that, now 
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 so far 
in this lecture for catalan numbers so t 
of z equals one over 2z 1-square to 1-4z. 
So there is tiny complication because of 
first term has the cancel out but 
ignoring that what we're using is alpha 
equals one half in this alpha equals 
minus one half. 
So that's what. 
One minus zero over rho to the minus one 
half in the denominator that square root 
and rho equals a fourth, so that's square 
root of one minus 4Z, 
And then after this case is just a 
constant, just half up-front, and so we 
wind up needing gamma of minus one half 
and then that's two times gamma, of, of 
one halfs, just because gamma, alpha plus 
one equals alpha gamma of alpha, minus 
two square root of pi. So 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's not hard to finish the calculation 
to show that 
This transfer theorm immediately gives us 
the asymtonic's 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 this same theorem works for the 
arrangement problem. 
so different numbered, generalized 
arrangements, 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 E, 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 N that's H Sebem, that 
immediately gives the asymptotics, E to 
the minus H sub M. 
so do problems that the first one a lotta 
calculations to get there. 
second one we don't even know how to get 
there. 
immediately through this analytic 
transfer theorem we can get the result. 
And 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 
transfer theorems based on complex 
asymptotics. 
And I'll just talk through one, there's 
lot of technical details, just to give 
you some idea. 
If you have a system of combinatorial 
constructions or you have a bunch of 
classes and they are all interacting, and 
those operations indicated by OP zero, OP 
one, up to OP t Those can be sequencer, 
or sum or product operations. 
And you can create a whole linear system 
of combinatorial constructions. 
So very simple special cases, the binary 
tree one, where you got t on one side 
and. 
z times t times t on the other side. 
You could have a much more complicated 
thing. 
A cycle of binary trees of sets of well 
not those, but linear combinations of 
combinatorial classes. 
The 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's a, a method called 
Grobner basis elimination that reduces 
those all down to a single generating 
function equation. 
And not only that, there's a theorem 
called the Dimota-Lally-Woods theorem 
that shows there's an explicit solution 
to that equation. 
that equation's got the square root. 
and this is in the complex domain. 
and there's a process called singularity 
analysis that immediately gives a simple 
asymptotic form. 
So any combinatorial construction is 
asymptotic to a over two squared pi n 
cubed b to the n. 
Where a and b are constants that we can 
explicitly calculate from the 
construction. 
Its an amazing universal law. 
And you can find in older mathematical 
literature, hundreds of papers that come 
up with these these kinds of results. 
that this this one process covers. 
And that's just one example of universal 
laws that we see in analytic common 
towards there are many more. 
So that's an introduction to coefficient 
asymptotics.