This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings.
Coefficient Asymptotics
Loading...
En provenance du cours de Princeton University
Analysis of Algorithms
37 notes
À partir de la leçon
Analytic Combinatorics
Analytic Combinatorics. With a basic knowledge of recurrences, generating functions, and asymptotics, you are ready to learn and appreciate the basic features of analytic combinatorics, a systematic approach that avoids much of the detail of the classical methods that we have been considering. We introduce unlabeled and labelled combinatorial classes and motivate our basic approach to studying them, with numerous examples.
Rencontrer les enseignants
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
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.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
