Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.
Supercritical Sequence Schema
Loading...
From the course by Princeton University
Analytic Combinatorics
17 ratings
From the lesson
Applications of Rational and Meromorphic Asymptotics
We consider applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes that we encountered in Lectures 1 and 2. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction.
Meet the Instructors
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
by now I think most of you are convinced that the, meromorophic transfer theorem
provides a really, pretty simple, turn-the-crank method, for doing the last
part of analytic combinatorics. Giving us analytic transfer.
Right to asymptotic estimate of coefficients.
For a big variety of combinatorial classes.
next I want to introduce an even more important concept.
The idea of a schema where we can have a general theorem that directly gives us
results for a, a whole set of combinatorial classes all at the same
time. as many examples of this in Analytic
Combinatorics, this is the first of many examples that we'll see.
so, the idea is of a schemist, that's a treatment that unifies the analysis of a
whole family of classes. so that would redo the analysis once and
we don't have to do again. you could think of our transfer theorems
as that way, but you, you'll see the distinction.
so for example, what we're going to talk about now is all combinatorial classes
that are built using the sequence construction at the top level.
So if a class has the form, f equals sequence of g, where g is any class at
all labeled or unlabeled, and we're going to say that's a sequence class and
it falls within the sequence schema. And then what we'll see is, a way to get
the coefficient asymptotic for sequence schema.
Just in terms of the generating functions for these top level classes.
So for example, for numeration. we know that if f is a sequence of g,
then the generating functions satisfy the relationship f of z equals 1 over 1 minus
g of z. where these are the coefficients of, this
is for the unlabeled case. the number of structures we're talking
about is f sub n. For the labeled case, it's n vectorial f
sub n. We've seen examples of, of those.
but what's also interesting is that we can use the same approach to analyze
parameters. so like if you want to count the number
of g components in f. So its the sequence of g's and number of
how many different g, how many g's are there in f, and then you could just mark
it with variable you as we saw in lecture three.
and get this relationship that the [UNKNOWN] generating function for f has
to satisfy in terms of the generating function for g.
Or maybe you want to mark the number of components of size k.
so then you take the ones of size k and mark them with u and take them out.
and then you get an, equation like this for the generating function [UNKNOWN]
generating function for number of components of size k and so forth so the
idea that its a sequence class gives us a relationship among the generating
functions. And we can exploit that.
in the analysis. with metamorphic asymptotics.
So now what often happens and this is the first again of many examples is when
we're looking at the generating function as an analytic object, there's some
technical condition that we have to assume about degenerating function in
order to be able to apply the analytic results, and so, maybe there's something
like [UNKNOWN] that gets rid of the technical condition out there, but for a
lot of these, we don't know those. But usually, as you'll see, these
conditions are easy to check and they hold so, for sequence classes, its the
idea of supercriticality. So what we're going to talk about is
supercritical sequence classes, where we mix up the formal and the analytic.
And we're going to say that a sequence class is supercritical if, if you look at
the generating function of the G class, the component class you have it's
generating function G of Z. and it's got a radius of convergence.
and the thing is if you evaluate the function at it's radius convergence and
it's bigger than one, then we're going to say that the sequence class is super
critical. And that's the condition that we need in
order to be able to unify the analyses. so, just as an example, we did the
generating function for integers a while ago Z over 1 minus z.
So the radius of convergence is 1 minus epsilon for any epsilon.
so if we evaluate it at, at row, then we get 1 over epsilon minus 1.
and there's plenty of values of epsilon within the radius of convergence, of
course that's bigger than 1. So, as long as we pick a small enough
epsilon we have the super critical conditions satisfied.
We can do this test enough for on the other coming into our classes that we
looked at. So, anyways, since I of Z has this
property the classic compositions is super critical.
Its the g that we're testing that has to has this property that if you evaluate at
its raise [UNKNOWN] you get bigger than one.
So since intergers has that property, compositions is super critical.
now in the book there's a full treatment of what happens when there's periodicity
in the generating functions. and were going to just for simplicity.
Because I really just want to get across the idea of what a scheme is.
Were going to ignore a periodicity in this lecture.
and so we have another technical definition called strong aperiodicity
that says that there's not going to be aperiodicities in there.
so given those two definitions, now We have a general transfer theorem for the
whole schema. and it gives an even simpler way to
derive the coefficient asymptotics for these types of classes.
so it says that if f is strongly a periodical supercritical sequence, then
it's coefficient asymptotics is just 1 over g prime of lambda.
and the growth is one over lambda at the end plus one, where lambda's the root of
g of lambda equals one, in its radius of convergence.
So we've find a root, but it's a simpler root and boom, we have the coefficient
asymptotic. so you need to, this is just a quick
sketch of the proof and it's technically not so difficult.
first of all, the function increases from zero to it's radius convergence of
positive coefficients and the value at row is bigger than 1.
So there is a root in there. there is a value where G of lambda equals
one and that's, that's the one that we're going to for.
and then at that point you can write out the series expansion of what G would be.
and then if you take 1 over 1 minus G, then that's gives you the leading term in
that. essentially gives you the coefficient
asymptotics. that's the just a quick outline of the
proof. but really all most people are going to
remember from this slide is this idea. That all I have to do is find lambda and
evaluate g prime at lambda and I've got the coefficient asymptotics.
so, just to look at the examples that we already looked at.
For example, for surgections that's a sequence of non-empty sets.
So, it's 1 minus e to z minus 1, so that's where e of g is.
And so , the lanbda is where g of z equals 1.
So, it's ez equals 2 lambda equals log 2. So, boom, log 2 dm plus 1, and then g
prime, And of that, it's just e of z, evaluate lambda's 2 and that's it.
so such an easy way to get from the construction right out to the coefficient
asymptotics. Find the root that's the exponential
growth. and again this is just another example of
our basic [UNKNOWN], so we're going from the spec to the generating function
equation immediately to the acetonics. and here's another one that we did was
alignments. so now g of z is log of 1 over 1 minus z.
where is log of one minus e equals 1, we already did that calculation.
It's 1 over e, boom, 1 over e to the n plus 1 derivative is 1 over 1 minus e,
evaluate over 1 minus e is e, boom, that's it.
compositions, that's, that's the one we've done.
G of z is z over 1 minus e, where is that equal to one?
At one half over to to the n minus 1. so an even easier way to do coefficient
asymptotics for a whole class of combinatorial classes.
A whole family of combinatorial classes, the ones that are built with a sequence
construction. That's an example of a schema, and we're
going to see other examples later on. Now, you might argue, that's not really
that much of an improvement. the, the other method was pretty simple
as well and there's some truth to that kind of argument.
but what I'll show you next really maybe gives a feeling for why schema are so
powerful. say you want to study parameters.
Like, how many parts are there in a random composition.
so, so it's like for two, it's then one of them's got three, two of them have
two, and one of them have one. The average is two and actually well you
can probably figure out what you think the number of parts is you know in a, in
a composition. but of course the same method's going to
work if we restrict to ones and twos or primes or whatever else.
or let's look at surjections. what's the, if you have a random
surjection, what's the expected value of M?
that's a much more complicated calculation.
Here there's one of them where the value of M is one, there's six of them where
it's two, six of them were it's three so that's the expected value.
And for 4, there's 1 where it's 1, there's 14 where it's 2, there's 36 where
it's 3 and there's 24 where it's 4, and again you get the average.
So, average expected values of parameters or here's for alignments, how many cycles
are there in an alignment. and again, this seems like a difficult
analytic problem. but a real poster child for analytic
combinatorics and this idea of scheme is that we can get, answer these question
immediately through general transfer theorem based on supercritical sequence
scheming. Let's see how that works, and this really
is just a generalization of the simple proof that we did for enumeration just
with the [UNKNOWN] generating function and I'll I'll skip the details.
but what we get is if we have a strongly [UNKNOWN] sequence class then we get the
expected number of g component in a random f component.
we get the expectation and the standard deviation.
Again, all in terms of this lando which is the route of g equals 1 in it's radius
of convergance. Again, the proof of this is just going
ahead from the definitions that we've done before by verious generating
functions. And the same kind of expansion that we
did for enumeration. And you have a similar theorum for number
components of size k and so for it to get much detail...
But, I, again, most people are just going to look at that one things and say,
actually that first term n over landed g prime of landed, that's my expected
number of components. that's all I have to compute.
and for, for example, for composition So my G of z is z over 1 minus z.
My lambda is one half as before. so lambda G prime of lambda, that's one
half, boom. I expect the number of components is n
over 2. for surjections Lambda's log two and u,h
so lambda g prime of lambda. G prime is e to the z e to the log two is
two so its n over 2 log 2. Immediately, we get the number of
components and alignments again it seems like really difficult analytic question
but its just all about computing lambda and then multiplying that by the
derivative of t value at that place and in this case it comes out to be e minus
1, immediately we get results like this and we can get other kinds of results
like component sizes and other things. Simply by using this structure of the
combinatorial class and then what we know about analysis in meromorphic
asymptotics. that's one example of the power of the
idea of a schema. and there are several other schemas
discussed in the book.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
