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.

Â