0:05

This is the last lecture in the analytic combinatorics class, so it's appropriate

to do a wrap up and a survey of the things that we've done.

And I've used this slide at the beginning of every lecture to give the basic

overview that what we're after is mechanisms whereby we can specify a

combinatorial problem, and from that specification, immediately and

automatically derive a generating function equation, and then use complex

asymptotics to get asymptotic estimates of coefficients, which give, which give

us the quantitative results, that we're looking for.

the basic ideas, are I'll, I'll say in words because they're worth restating.

first of all, we have combinatorial specifications that give us succinct ways

to define discrete structures. And this is an extensible system of

specifications and people are discovering new ones every day.

Associated with the specifications, we have the symbolic method, which gives us

a way to transform the specifications to equations that define generating

functions. We're treating the generating functions

as formal objects that we can immediately derive definitions from the

specifications. Then we pivot and treat the generating

functions as analytic objects, as functions in the complex plane.

and we can get coefficients, estimates of the coefficients, by doing that.

Either using Cauchy's coefficient formula directly when the singularities are

poles, or using singularity analysis when we have essential singularities, or

saddle-point asymptotics when there's no singularities at all.

so, and more important, in many situations we have a schema that for,

various combin, combinatorial classes that give universal asymptotic laws.

So, in, in many cases where we don't, need to go down to the detail of

asymptotics. Certain combinatorial classes, just by

their structure, asymptotic laws, tell us quantitative bounds on, on their

properties. so, early on, we looked at constructions

and symbolic transfers for unlabeled objected and for labeled objects.

and these basic constructions gave us the tools to specify many, many classic

combinatorial problems and get associated generating functions immediately.

and then, after treating generating functions as analytic objects functions

in a complex plane we saw explicit ways to transfer from generating function

equation to coefficients. for meromorphic functions, there's a

general transfer theorem. if the generating function is in the

standard scale, we saw at the beginning of the singularity analysis lecture that

we could immediately transfer functions like that into coefficient asymptotics.

if we have square root or logarithmic singularities, we can use singularity

analysis. And if there's no singularities, we can

use the saddle point method as discussed in this lecture.

3:35

But more than that, there's schemas. We can organize.

We saw in several lectures that we can organize combinatorial problems into

broad schemas that cover, infinitely many combinatorial types and, and the simple

asymptotic laws that govern them. so we looked at supercritical sequence

schema. if it's built as a sequence with certain

technical conditions, we know the coefficient asymptotics, or we look at f

x blog. If it's a set under certain conditions,

again, certain technical conditions we get asymptotic.

Or a simple variety of trees, where it's recursive against certain technical

conditions or context-free, or implicit tree-like classes.

These schema cover a very, very broad variety of combinatorial constructions.

And we immediately have coefficient asymptotics under certain technical

conditions. One of the most important aspects of

analytic combinatorics is the discovery of schemas like this and the associated

universal laws that's the very essence of analytic combinatorics.

There's plenty of other examples in the book.

4:46

So from the beginning I've been repeating Philippe's mantra, if you can specify it

you can analyze it. And I'll just click through the 20 or so

examples from binary trees to surjections to compositions, alignments, compositions

of various types, permutations with derangements order trees of two regular

graphs. Lots of different types of combinatorial

classes finally ending up with involutions and set partitions in this

lecture. I noticed that that's just a small

example for every one of these examples is variations, that again can be handled

in a, in a uniform manner. so just in case someone asks you took

analytic combinatorics, what is that? this is, the answer.

it seems to enable precise quantitative predictions of the properties of large

combinatorial structures. It's a theory that's emerged over recent

decades as essential, not just for the analysis of algorithms but also for the

study of scientific models in other disciplines, including statistical

physics, computational biology and information theory.

So, then the question is what's next. Well we've only really looked at the tip

of the iceberg and this an introduction to analytic combinatorics.

and there's quite a bit more in the book and in the research literature for

further study. so we only covered the basic

constructions for example. There's many associated many other

constructions that people have studied in symbolic transfers that lead down paths

through many other important applications.

For example, there's a whole family of, there's quite a bit of discussion about

paths and lattices and other types of combinatorial problems that we haven't

talked about. Looking at the details of the singularity

analyses proofs is really worthwhile to, that really is a watershed moment in

Analytic Combinatorics because of the development of those transfers.

there's a lot of conditions having to do with periodicity, irreducibility and what

happens with algebraic functions and context-free languages that are

fascinating mathematically and important in applications and definitely worth

studying. And we have only a few moments in this

course to talk about and other schemes as we move on we're going to talk about five

or six at this point these other ones. The Drmota Llaley Woods theorem that

helps us with that, exclusions of systems of generating functions equations, that's

another key, an insightful piece of mathematics that's at the core of

analytic combinatorics and definitely we're going to study.

reading more about saddle point approximations and the associated

technical conditions and the trade off between the central approximation and

neglecting the tails. That's also important area to study in

more detail. The primary reason for that is the role

of both that kind of saddle point in limit laws and multivariate asymptotics

but we're not looking just for numeration but also distributions of properties of

combinatorial objects. and there are developed in that of the

book are important and far-reaching and widely applicable.

General laws that tell us that is often the case that parameters that come

between objects again in simple asymptotic behavior.

And then applications, there's many appliactions in the book and many

applications in the research literature. And really its the applications that

inform the mathematics that we develop in analytic combinatorics.

So,, for an overview of whats going on recently and in also Fajolet's life's

work in papers. I recorded a a postscript to this course

I called if you can specify it you can analyze it the lasting legacy of Phillipe

Flajolet. And that's the second part of, of a

lecture, that I gave earlier this year, and this first part with a preview of

this course so take a look at that if you're interested in further study in

analytic combinatorics. and finally I want to finish by talking

about other resources or seamless plugs or things that are available related to

the information in this course. we've been talking mostly about the

analytic combinatorics book prior to that, part one of the course was about

analysis of algorithms. And then algorithms book joint with Kevin

Wynne, also have online materials and a course.

And if you're a mathematician and not familiar with programming, we have

Introduction to Programming. and all of these have associated web

resources that you can, take a look at, to get, lots more information or to

engage, with, with the material. and also you're here because, of, of

online courses, we have online courses associated with algorithms with analysis

of algorithms, and with analytic, analytic combinatorics.

And also as special treat for people, that are taking this course, there's a

t-shirt, and if you go to the book site you can get details on ordering the

t-shirt. so, just the a final though, and this is

a Winston Churchill quote, it's also a rock anthem.

but now this is not the end. It's not even the beginning of the end

but it's perhaps the end of the beginning and that's the way I'd like you to think

about analytic combinatorics.