Now we're ready to talk about really what 
is analytic combinatorics. 
So it's a calculus for the quantitative 
study of large combinatorial structures. 
And generating functions are the central 
object of study in analytic 
combinatorics. 
So the basic process is 3 step Pretty 
simple. 
first thing we do is define what's called 
a combinatorial construction that per, 
precisely specifies the structure that 
you want to study. 
the second thing we do is use what's 
called a transfer theorem, a symbolic 
transfer theorem, to get a generating 
function equation. 
And then we use another analytic transfer 
theorem to extract the asymptotics of the 
coefficient. 
That's it. 
A 3 step process. 
And what's important is that it's very 
often the case, that all 3 steps are 
almost immediate. 
For example, for our binary tree 
question, how many binary trees are there 
with N nodes? With analytic combinatorics 
we write down the combinatorial 
instruction. 
That's a formula like that one and I'll 
talk on the next slide where that comes 
from. 
Then we use a transfer theorem. 
A simple, this one simple to approve and 
simple to apply that immediately gives 
the generating function equation. 
it's the same one that we got, the hard 
way before. 
And then we use an analytic transfer 
theorem that immediately gives us the 
coefficient asymptotics. 
And again this theorem is very 
sophisticated to prove but it's easy to 
apply. 
so a three step process to solve the same 
problem, avoiding all of the detail. 
That's what analytic combinatorics can do 
for us. 
Let's look at these three steps, in 
detail. 
So, the first step, is to specify the 
class using a combinatorial construction; 
and these things are built from natural 
operations and once you've, 
see a few of these in, in simple examples 
and you'll see how natural they are. 
they're algebraic formulas that are built 
with combinatorial operators and the 
operands are either atoms, or the basic 
building blocks, like nodes in a binary 
tree. 
or they could be other constructions or, 
or classes. 
and there's two cases that I won't get 
into that much detail on in this talk, 
but either the atoms are unlabeled, there 
are no difference between them, or 
they're all different they're labeled. 
in, in That leads to, differences in the, 
in the operators, and in the unlabeled 
case we use ordinary generating functions 
and in label we use exponential. 
but, at this level, there's not Not much 
different. 
and the idea is that what we're doing is 
very similar to formal languages in 
computer science. 
but the idea of a combinatorial 
construction, we are particularly paying 
particular attention to ambiguity if 
you're familiar with formal languages. 
and so, there's a lot of constructions, 
but the basic ones that I could use to 
illustrate one analytic combinatorics is 
are very simple. 
so there's a union operation, so A= B + 
C. 
and the letters just represent classes of 
combinatorial objects. 
A combinatorial class is a set of objects 
and the size function is all. 
there's a Cartesian product, which is 
pairs. 
and there's a Sequence, which is a 
sequence of a just shorthand for pairs, 
any number of pairs. 
so this is the basic constructions that 
we can use and for example this is just a 
fully formal bases for being able to 
write down a specification of what is a 
binary tree with that formula, t = e 
which is the empty class + z which is a 
class containing one thing which is a 
node. 
[COUGH] That, is a product with a node, a 
tree is a sequence of a node and 2 trees. 
so that's a formula that fully specifies 
what we mean by binary tree. 
And we define a binary tree in English, 
we usually say, a binary tree is empty or 
a node and 2 binary trees. 
This is saying that formally in math 
speak. 
That's what a combinatorial construction 
is. 
You'll see lots of examples of 
combinatorial constructions later on. 
So then, the next thing is to introduce 
generating functions. 
Well, one of the things about the 
combinatorial constructions that we use, 
is that we associate the constructions 
with operations on generating functions. 
So, this part happens immediately. 
So for unlabeled classes, we use ordinary 
generating functions, and it's the same 
as before. 
we sum for all sizes, the number of 
objects of a given size times Z ^ N, 
where Z is a synthetic variable. 
And, by the way, that's exactly equal to 
summing over every tree. 
Z to its size, as for all the trees of 
size N, there's one term, and that gives 
T sub N. 
and that representation of the generating 
function, is what gives easy proof of the 
transfer theorem. 
So although I won't take time To do the 
proofs right now. 
So, the basic transfer theorems are very 
simple. 
If you've got 2 classes b and c, and you 
take the union, the generating function 
for the result, is the sum of the 
generating function's of the 2 offering. 
If you do the Cartesian product, it's the 
product. 
If you do the sequence, it's one over one 
minus. 
And that just comes from sum of one plus 
B(z) plus B(z) squared plus B(z) cubed, 
and so forth. 
That easy to prove from the product. 
so, given the operations we immediately 
have a translation to generating 
functions. 
So for example, for binary trees, our 
combinatorial class is the set of all 
trees. 
And the size function is absolute of t, 
notation, is the number of nodes in t. 
so the, what we're interested in is the 
counting sequence, the number of trees 
with N nodes. 
and from this very basic information, Why 
we have the construction that I showed on 
the last slide, immediately translates to 
a generating function equation. 
the empty class generating function for 
that is 1 z. 
The generating function for class 
consisting of a single node is just z. 
and then there's t of z twice so it's z * 
t of z ^. 
So that's a fully rigorous mathematical 
transfer from a construction to a gf 
equation. 
we had many other constructions but for 
all of them there's associated transfer 
theorems. 
nowadays that's what we mean by a 
combinatorial construction, that's one 
for which we know a good transfer 
theorem. 
So generating functions are the key to 
analytic combinatorics. 
But I have to point out quickly that the 
use of generating functions within 
combinatorics was very controversial for 
some time. 
For example, here's a quote from Claude 
Berge, a French mathematician. 
and expressed the point of view of many 
people working in combinatorial 
mathematics. 
So the property is understood better when 
one constructs a bijection, then when one 
calculates the coffeients of a polynomial 
whos variables have no particular 
meaning. 
The method of generating functions, which 
has had devastating effects for a 
century, has fallen into obsolescence for 
this reason. 
That was Berge's point of view. 
Flajolet had a completely different point 
of view. 
He says that they are really the central 
objects of the theory not a mere artifact 
to solve recurrences, as is still often 
believed, and we'll see why. 
When we get to the next step of analytic 
combinatorics. 
What we're going to do is use view the 
generating function. 
It's still a synthetic variable, but 
we're going to view it as a complex 
variable. 
So, the generating function is going to 
be a function in the complex plane. 
And that viewpoint allows us to unlock 
analytic transfer theorems, that 
immediately give us the coefficient 
asymptotics. 
So, for example, even real analysis, but 
also in complex analysis, the coefficient 
of z to the n and 1 over 1 minus z over 
row, that's got a pull, row, it's row to 
the minus n, sum of z to the n row to the 
minus n. 
so that's easy. 
but, we can do much, much more, so for 
example, if we take 1 -0 to the alpha, 
were alpha is any real, except it can't 
be any negative integer, it degenerates 
in that case. 
It's asymptotic to 
N^(alpha-1)/gamma(alpha), that's the 
gamma function which generalizes the 
factorial rho^-N. 
and even if there are logarithmic factors 
we can prove the transfer theorem that 
coefficient is Z^N. 
And that function throws out a log N 
factor. 
now these are simple to apply. 
they couldn't look simpler. 
the proof of them is extremely 
sophisticated. 
And really, it was publication of this 
paper, by Philippe and Andrew Odlyzko, in 
1990, it was really a watershed moment. 
before that time we suspected that we 
could get these answers out in this way, 
but proving it was another A thing 
entirely. 
that's what I said, when I said, we 
needed to, needed to do the math. 
And Philippe and Andrew [INAUDIBLE] 
definitely did the math. 
it's worth understanding, this paper, but 
it's truly tour-de-force and a, and a 
masterpiece. 
but now, we can benefit from, 
There's a very, long list of transfer 
theorems, of this type. 
it's really starting with, with this 
basic one. 
And these things are effective, even for 
approximations and near the 
singularities. 
When there's other functions. 
Functions involved. 
but, for example, for our problem, if you 
want the coefficient of Z ^ N in square 
root of 1 - 4Z, you just plug in the 
standard scale equation, alpha = -1/2 
Half. 
and, row =, 1/4. 
and immediately, you get the asymptotics 
of the coefficient. 
it's asymptotic to n to the - 3 halves 
over gamma -1/2 4 to the n. 
and gamma - 1/2 is - 1/2 square root of 
pi. 
And that, boom. 
That gives us the asymptotics, 
immediately just directly applying the 
theorem without worrying about all the 
sophistication under, under, underlying 
its proof. 
So that's the third step. 
So there you are. 
That's two different ways to count binary 
trees. 
You can go through the classical analyses 
of algorithms all those steps. 
Which, by the way a lot of students and 
I'd say even a lot of professors might 
take quite awhile to really get through 
all the steps to do this Catalan number 
derivation. 
But with analytic combinatorics, it's 
boom, boom, boom, there's the answer, 4 
to the n over square root of pi n cubed. 
take your pick. 
most modern researchers, who are looking 
at scientific study of large quantitative 
structures are, are going the analytic 
combinatorics way. 
because it's effective for a very broad 
variety of combinatorial structures, for 
example the unlabelled case that we're 
talking about. 
So we talked about trees there's othere 
types of tree, I'll talk about that in a 
minute, it works for strings or even 
just. 
For properties of numbers for like, for 
compositions, those are sets of numbers 
that sum to N, or partitions where you 
don't take the order into account or for 
languages, for regular languages or 
context free languages are just examples 
of combinatorial structures that we can 
specify and therefore we can analyze with 
analytic combinatorics. 
labels objects are things like 
permutations or balls and urns, or cyclic 
permutations or functions we call words, 
function from 1 finite domain to another. 
label trees those are acyclic mappings or 
general mappings, and many many others. 
these are just the basic ones. 
and not only that, [INAUDIBLE] is fully 
extendible. 
so, new constructions are easy to derive. 
Just use the tools the way you would for 
any formal language. 
And, not only that, if you don't find the 
construction that you need, you can 
develop, a new one. 
and a corresponding transfer theorem, and 
that's happening regularly for all sorts 
of applications. 
so, just to look at some elementary 
examples briefly you can see how over and 
over again we can just go from a 
construction to a generating function 
equation to get the coefficients out. 
Some times the transfer theorems are very 
simple they're just [UNKNOWN] theories 
expansions. 
So, an integer is just a sequence of 
unmarked objects, there, a positive 
integer say. 
so that's z cross sequence of z. 
So that immediately translates to z over 
1-z and number of integers. 
Of size, n is just a 1, for n bigger than 
0. 
And then we can, use, build on that 
construction to talk about partitions and 
compositions and other things. 
Are string, that's our say genomic 
string, it's a four character string, 
it's a sequence of Four different atoms 
so or in this case, say, M different 
atoms. 
but that immediately gives strings from 
the alphabet of size M. 
The generating function, is 1 / 1 - MZ. 
and there's M ^ N of them. 
again very fundamental construction. 
binary trees is the one that we just did, 
that needs an analytic transfer thereom. 
Now, below the line is the labeled 
universe. 
A permutation is a sequence of labeled 
objects. 
the multiply appli operation involves 
relabeling, and I won't get into that 
now, just show what the constructions 
look like. 
And it's exponential generating function, 
so we need to multiply the coefficients 
by n!. 
Huh, Cycles or labeled cycles, it's log 
of 1 over 1-Z and immediately again, 
immediately gives yourself a generating 
function. 
Huh,words is a, if you specify the 
indecise that have each value, it's a 
sequence of sets, and huh, and so the, 
huh, immediately the transfer theorem 
gets you to the Mz and and it's n to the 
m, it's just looking at the same 
commonitorial object in two different 
ways. 
And there's all sort's of benefits of 
doing that. 
Because one of the real sweet spots of 
analytic, upper analytic combinatorics 
and one, one of the reason's is it's so s 
Is, now you take those fundamental 
constructions and transfers that are easy 
to understand. 
And you, once you do it, then you can 
have variations and get the analysis 
immediately. 
So we talked about binary trees, but you 
could do ternary trees. 
Or ordered trees where the, every node 
can have any number of children at all. 
Or you can specify that the number of 
children has to be less than, a given 
value, say 0, 1 or 2 say or you can have 
actually arbitrary restrictions, of any 
kind. 
Or it's gotta be more than 2. 
And there's important applications of 
every 1 of these they're all easily 
handled with symbolic transfer theorems. 
now if sometimes we can get to generating 
function equations that seem difficult to 
deal with. 
a five way tree's going to have a, a 
fifth order polynomial and so forth that 
we might have to work with. 
and that's it might seem challenging, but 
actually, another hallmark of the 
analytic combinatorics , is that, a lot 
of times a single transfer therm can 
Cover eh, a broad, broad variety of 
cases. 
And those are called universal laws that 
are extremely general. 
Now, that's one of the hallmarks of 
analytic combinatorics. 
for example, context-free constructions. 
So, this is when, we can have a whole 
system of combinatorial construction. 
Where the operators is one of the simple 
ones that I've talked about. 
those with the symbolic transfer go 
immediately into a system of generating 
function equations. 
You're going to write those out 
symbolically, they can be pretty 
complicated. 
But, with Grobner basis elimination, for 
whatever it is, it can be reduced down to 
a single generating function equation. 
Now there's certain technical conditions 
to make all this work; I don't want to 
oversimplify it. 
But in, in the end what happens is then 
that single generating function equation 
there's the theorem called the [UNKNOWN] 
theorem that takes that down to an 
explicit solution. 
so for any system of combinatorial 
construction it's always going to have a 
solution of this time with C, B and A 
constants that we can compute. 
Or we can get more [UNKNOWN] accuracy if 
we want. 
So, the analytic transfer theorem from 
singular ring analysis that we just did, 
gives this simple asymptotic form. 
You have a context free construction. 
It's going to be, a over 2 square root of 
pi, a^3 b to the n. 
Where a and be are constants that we can 
compute. 
it's amazingly, general universal law. 
And there's, several universal laws, that 
we know. 
Before analytic combinatorics, you would 
find papers, long papers that used the 
old methods to come up with the results, 
and it was becoming pretty clear to 
experts that there had to be something 
behind square root of pi N ^ 3 appearing 
in the denominator all the time. 
but, we can now know that, why that 
happens because we have the universal 
laws. 
And, again, there's several others, and 
one of the goals of modern research in 
analytic combinatorics is, discover, more 
and more, universal laws. 
so that leads me just to briefly describe 
analytic combinatorics at the next level 
beyond what I've been able to talk about 
right now. 
one thing is that actually often what we 
want is multi-vari Generating functions 
have to handle combinatorial parameters, 
multivariate analytic combinatorics, 
sometimes will give us limit laws about 
the values of, of parameters. 
A lot of times the, the behavior of the 
functions and the complex plane, it's 
very complicated, and we get oscillation 
like that formula that we had, involving 
the data function, is an example of that, 
so the answer is not simple, we have to 
deal with that. 
sometimes there's a method known as 
saddle-point asymptotics that we have to 
use for for generating functions that 
don't have singularities. 
You can do more than just figure out a 
counting sequence from knowing an 
equation that the generating function 
must satisfy. 
One of the things you can do is generate 
random structures. 
And, one of the important applications of 
analytic combinatorics is use 
combinatorial constructions as a basis 
for generating big random structures. 
Which you can compare against real data 
to decide if you have a decent model. 
as I mentioned, and I didn't discuss in 
detail these analytic transfer theorems 
sometimes have technical conditions that 
need to be checked and sometimes that's 
really the burden of completely solving 
the problem. 
And so we want to remove as many such 
conditions as possible. 
and the other thing is, when another 
thing is, when, when we get into analysis 
of algorithms, we're often talking about, 
with programs, transforming data. 
from one structure, one combinatorial 
structure to another, which is a complex 
process that's, difficult to capture, 
maybe even with, analytic combinatorics. 
and then also, we Easily can construct, 
specify constructions that lead to, 
relatively complicated, implicit 
functional equations, that are maybe not 
so easy to handle with, analytic transfer 
theorem. 
but still there's a very broad variety of 
problems that that can be handled simply 
with combinatorial constructions 
transferring immediately to generating 
function equations and then translating 
to coefficient asymptotics one step after 
another. 
For example that's partitions. 
how many ways are there to Write an 
integer as sum of other integers, of 
smaller integers. 
so [COUGH], a combinatorial construction 
for that is multiset and the transfer 
theorem immediately gives the The 
generating function, 1 / 1 - Z, and so 
forth and then there's a, analytic 
transfer theorem that immediately gives 
the coefficient the asymptotics. 
so, just another example, series parallel 
networks, where this is a model for for 
Boolean expressions and electric 
circuits, and many other things. 
and so, you want to know how many of 
those are, how many bits would you need 
to represent one or study some parameter 
of it. 
You can use a combinatorial, a simple, 
combinatorial construction. 
Get a simple generating function 
equation, that is amenable to the 
standard transfer therm where the 
exponent is 1/3-^8. 
relatively straight forward to study such 
problems with analytic combinatorics. 
so surjections, that's the number of 
mappings onto initial sequences of the 
integers, and of how that's got lots of 
applications and again it's a sequence of 
a set immediately gives the generating 
function and then be, it's 1 over 2 - 
Z(z) so the similarities are 2 over log2 
N. 
at, at log 2. 
And, so that gives the asymptotics, 
immediately. 
components in, in mappings. 
so a mapping is a function from the 
integers 1, through n to itself. 
and, that. 
[COUGH], gives the, the [UNKNOWN] with 
the two constructions. 
It's a cycle of trees, really, and a tree 
is, a node and set of trees. 
so that's what those constructions say, 
and they immediately translate into those 
generating function equations, and then 
we have transfer theorems that 
immediately give the coefficient 
asymptotics. 
So, it's a very, very long list of 
standard combinatorial objects, and 
combinatorial parameters that are 
classical objects, that are amenable to 
study with analytic combinatorics. 
And then, all kinds of new objects that 
were Too complicated to deal with using 
classical techniques, that people have 
studied and learned properties of, with 
analytic combinatorics. 
If you can specify it, you can analyze 
it. 
so that's what's in our 2009 book, this 
is an, an overview of what's inside and 
how it's related and, and what Comes out 
so the first thing is the symbolic 
methods, the symbolic transfer theorems 
for labeled objects, unlabeled objects, 
and parameters corresponding to ordinary 
exponential, and multivariate generating 
functions. 
From those symbolic methods, you can 
either go into complex asymptotics to go 
ahead and get out the asymptotic counting 
results as I've discussed but you can 
also get out moments of parameters as 
well. 
and you can get properties of random 
structures and limit laws as well. 
So that's again, in a short lecture the 
best I could do to describe, really what 
is analytic combinatorics. 
and so, 2009 we think this one is, is 
solved. 
it's got All kinds of applications from 
studying patterns in random strings with 
finite fields, standard algorithms like: 
hashing, data compression, geometric 
search, chemistry, it has combinatorics, 
and one, and one of the original 
history's of our field was Polya, George 
Polya studying application in chemistry. 
there's a connection to analytic number 
theory. 
people are studying planar maps and 
graphs and probabilistic stream 
algorithms. 
we have a solution to a standard, theorem 
in computer science that is based on 
analytic combinatorics. 
Bioinformatics is a very rich and fertile 
area of application, and statistical 
physics, and Automatic testing of 
programs and, many, many others. 
If you can specify it, you can analyze 
it. 
and analytic combinatorics is here to 
stay, here to stay. 
So I mentioned that it was 30 years, in 
the making to get to the book. 
And I just want to finish by, pointing 
out that, we're still counting. 
Though, there's is a second edition now, 
the original analysis for Algorithm book 
that I did, that includes and 
introduction to analytic combinatorics, a 
and I know Felippe always wanted that. 
And more than that, there's extensive web 
content in the process of development. 
and also online course. 
So it's a very active and vibrant field 
if you want to learn more about analytic 
combinatorics there are many ways to do 
so. 
I've given a lecture like this, many 
times since Philippe's death. 
and I, at first, ended with saying, it 
was a pleasure to work with Philippe. 
But now I think it's better to say that 
it's a pleasure to be working with him 
because I feel that I'm still working 
with Philippe. 
I, and I hope that many more of you have 
the opportunity to do so through the 
materials that I've discussed.