All right, so let's summarize what we've done in this lecture.
as promised, we've looked at from an analytic combinatorics point of view a
whole range of classic combinatorial classes.
from bit strings to derangements, to surjections, to alignments, to set
partitions, integers, compositions. In every single one of 'em, we took a
specification, immediately to a generating function with the, via the
symbolic method, and then, immediately to coefficient asymptotics, using the
meromorphic transfer theorem. Not only that, not only are we able to do
these classic combinatorial classes but also we can do variations.
Like restrict the bit strings to not contain a particular pattern.
Or generalize derangements where We parameterize the number of cycles that
are disallowed. same way with the surjections and for
compositions all different types of restrictions and as well as the
numerants. all of those things, again, are the same
basic idea of a speck that goes into a generating function, goes to coefficient
asymptotics immediately. Handling these types of problems without
analytic combinatorics, which you can find in the literature is possible
because underlying the calculations, there's nothing particularly novel or
important to this point. it's possible, but it requires a huge
amount of calculation. And analytic combinatorics allows us to
skip over the top. to immediately derive asymptotic results
without much calculation. and that's important because the idea of
a speck gives us an open ended way to specify combinatorial classes.
without having to worry that we may not be able to understand their coefficient
asymptotics. actually we can for this huge set of
combinatorial classes. so as promised I, I think in this lecture
you've seen that our transfer theorem for mero, meromorphic generating functions
gives immediate analysis of a large variety of classes.
We can just as easily handle variations. And then, we have the idea of a schema,
which unifies the analysis for a whole family of classes, including analysis of
parameters. now and also there have been several
other schemas developed that are talked about in the text.
so what we have do next is look at generating functions that are not
meromorphic. and that's going to be the topic of the
next two lectures when we get functions with singularities that are not isolated
that are not poles. and that'll be our topic for the next two
lectures.
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
