Just to summarize we've looked at many different applications of singularity
analysis starting with some familiar ones rooted ordered trees and binary trees.
we looked at the unary-binary trees and Cayley trees always getting generating
function by the symbolic method and coefficient asymptotics.
By a transfer theorem built from singularity analysis.
we looked at properties of mappings. 2-regular graphs, labeled a higher piece,
and other implicit, tree-like classes, and always being able to go from
construction to generating function to coefficient asymptotics.
And these are only representative examples for each one of them, and
there's many, many other types of classes that are similar that we can define and
still get immediately to the coefficient asymptotics.
we have a very powerful and general calculus for deriving estimates of, of
coefficients from combinatorial constructions.
if you can specify it, you can analyze it.
Singularity analysis is a very effective approach.
For generating function equations for classes with the GFs that are not.
It actually, that are not meromorphic. It actually also works for meromorphic
functions it's, it's more general. And some of these schemas that we've
actually done were meromorphic. Though we didn't, we just didn't we just
didn't talk about it. Could be.
so the idea is that what, we have these schema that can unify the analysis for
entire families of classes. we talked about the x blog, and simple
variety of trees, and the context free classes last time, and we didn't show any
applications this time, in implicit tree like classes, and we can always get out
to the a coefficient asymptotics for large families of combinatorial classes.
and there's other schema also that have been proven.
Now, not every example goes as smoothly as the ones that I've shown in lecture.
and particularly for context free and related classes the calculations involved
to actually find the specific constant can be complicated.
but usually it could be mechanized and it's reasonable to expect for a great
variety of classes that you're going to find this kind of behavior just using the
basic principle of coefficient asymptotics is the location of the
singularity is going to give you the asymptotic growth and the nature of the
singularity is going to tell you about the sub-exponential factor in the
constant. And in a great many cases we can compute
these things exactly into arbitrary asymptotic accuracy.
so next lecture we're going to talk about what to do with generating functions that
have no singularities. but, singularity analysis is really at
the heart of analytic combinatorics.
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
