Today we're going to talk about an 
introduction to analytic commonotorics. 
it might seem a bit strange in a course 
entitled, Analytic Combinatorics to not 
get to this topic until the middle of the 
course. 
But as you see it builds upon all the 
things we've talked about until this 
point and gives us a, coherent starting 
point from where we can go forward in the 
analysis of algorithms and the analysis 
of combinatorial structures. 
And I hope by the end of this lecture 
you'll have a pretty good ideal of what 
analytic combinatorics actually is. 
Just start with a brief overview. 
Analytic Combinatorics is a Calculus for 
the quantitative study of large 
combinatorial structures. 
and most of the work behind Analytic 
Combinatorics is set forth in our book, 
Analytic Combinatorics, that'll be the 
basis for part two of this course. 
but it also plays an important role in 
the, in the analysis of algorithms and, 
and the, the tie between elementary 
combinatorics and the kind of analysis 
that we need to really study computer 
programs. 
So the features, the basic features of 
analytic combinatorics is that, 
we begin with formal combinatorial 
constructions. 
So that is, we have a mathematical way to 
specify what it is that, that we're 
studying. 
the generating function that we've talked 
about in the third lecture, is really the 
central object of study in the analytic 
combinatorics. 
Number one, because we have transfer 
theorems that can immediately give us 
generating function equations from the 
combinatorial constructions. 
And number two, because we can take 
transfer theorems to give us estimates of 
the values of things right from the 
generating function. 
As mentioned last time, our asymptotic 
results are going to extend in principle 
to any desired precision on the standard 
scale. 
and most important is that it's a 
calculus, that is, we can handle 
variations on fundamental constructions 
very easily. 
and those kinds of variations help us 
cover a very broad variety of problems 
for study. 
So this is just a graphic depiction. 
We start with combinatorials 
constructions. 
And we use a symbolic transfer theorem to 
get a generating function equation and 
that process is sometimes known as the 
symbolic method. 
Then from the generating function 
equation, we use analysis and we use 
analytic transfer thorem to get our 
coefficient asymptotics directly. [COUGH] 
Essentially, this process allows us to 
avoid a lot of the detail calculations 
that we've been doing, in the analysis of 
algorithms and combinatorial structures. 
for example, in analytic combinatorics, 
if you want to know the number or tree, 
binary trees within nodes, there's a 
commonotorial instruction and we'll go 
through the details of this. 
That immediately transfers to a 
generating function equation. 
That immediately transfers to coefficient 
asymptotics for the result without going 
into all of the detail. 
That's the overview. 
We'll end the lecture with this slide two 
and you'll understand everything that 
goes behind the transfers. 
So the beginning point is the symbolic 
method, so we'll start by talking about 
the symbolic method. 
Now, it's an approach for number one, for 
defining combinatorial constructions. 
But mainly, for translating them to 
generating function equations. 
And the way that we do that is, define a 
class of combinatorial objects. 
Define some notion of what the size of an 
object is. 
Then, define a generating function, whose 
coefficients count objects of the same 
size. 
that's what we've been doing in 
generating function counting in several 
examples already. 
and then from those operations we're 
going to have translations for each 
operation that defines a construction to 
an operation on a generating function. 
And this is just the kind of notation 
that we use. 
Upper, upper case letters for 
combinatorial objects. 
some no, notation like absolute value for 
size. 
and then generating function will have 
the same letter as the as the class. 
Except it will be a function of a 
variable, usually Z. 
and then the operations actually will 
involve familiar symbols So now we have 
to get started somewhere, so there's a 
very formal basis, that, and, after these 
definitions we'll do examples and you'll 
see, the need for, for these, but it's a 
good, thing to talk about'em right at the 
beginning. 
So what is a combinatorial class, it's 
just a set of objects and size function. 
now we have to have something to begin 
with, and we call those atoms, those are 
objects at size one. 
We also, for convenience, have an atom of 
size zero. 
Which is a neutral object, and that's 
useful for describing. 
You'll see, that's useful for recursive 
definitions. 
so a combinatorial construction uses the 
union product and sequence operations 
that I'll talk about in a minute to 
define a class in terms of atoms in other 
classes. 
And we start with the very basic building 
blocks over on the right where the 
notation capital Z is in a contains a 
single atom then there is notation 
capital E which is a, a neutral class 
that contains an atom of size zero and 
also this empty class. 
And again now worthwhile I spend time in 
these definitions right now but to refer 
back to one we use later on if necessary. 
So here's a very simple example of a 
combinatorial class the natural numbers. 
So the defi, definition of a natural 
number is a set of atoms. 
Or since you can't tell the difference 
between atoms that's what we mean by 
unlabeled and we'll get into that detail, 
in much more detail later. 
A set or a sequence, it's the same thing. 
So, there's only one object of each size. 
so, we most usually, or at the beginning, 
we're most interesting in the counting 
sequence. 
How many objects of each size there are? 
In this case, there's only one. 
And we use ordinary generating functions, 
so the ordinary generating function for 
natural numbers is just 1 / 1 - Z. 
So that's a simple example of a 
combinatorial class and actually, that, 
it seems trivial, and that basically the 
early ones do seem trivial. 
It's when you put'em together that you 
get interesting and useful mathematical 
results. 
So, for example this combinatorial class 
is a basis of study for things like 
partitions of natural numbers. 
how many ways can you break'em up into 
subunits and compositions, and so forth? 
And we don't get into that too much in 
part one but we will in part two. 
here's something that we, that we study 
all the time in computer science a bit 
string. 
A bit string is a sequence of zero or one 
bits, and that's very familiar just 
defining this in familiar class. 
I have to get used to are, are notation 
and conventions. 
so how many bit strings are there of 
length N, well there's two to the N, so 
what's the OGF, it's two to the N, Z to 
the N, which is 2Z to the N, or 1 / 1 - 
2Z, so that's another example of a 
combinatorial class. 
here's one familiar one recast in terms 
of analytic combinatorics. 
so the binary tree is empty or it's a 
noded two binary trees that's, that are 
in sequence in order that matters. 
so those are now familiar binary trees 
that we studied before. 
we know the counting sequence is the 
Catalan numbers. 
[COUGH] that was the subject of quite a 
bit of lecture three. 
and its, its got this OGF and that 
derivation is all given in lecture three. 
so those are three examples of 
combinatorial classes. 
And now I want to show constructions and 
how we build those things. 
so for unlabeled classes, so that's a 
[COUGH] And again, I will talk about the 
distinction with labelled in a minute. 
We're just going to use three different 
constructions. 
If A and B are combinatorial classes of 
unlabelled objects, then we have the 
disjoint union, the Cartesian product and 
the sequence operations. 
And, here is the meaning of each one of 
those. 
A plus B is just copies of objects from A 
and B. 
Take one from A and one from B and that's 
the, that's the disjoint union. 
Cartesian product is ordered pairs of 
copies of objects, one from A and one 
from B. 
And sequences, sequences of objects from 
A. 
so those are the constructions and these 
are just examples of how a construction 
might work. 
So, for bit strength [COUGH]. 
I mean, you can use the usual 
distributive law. 
So 00 + 01 is got copies of 00 and 01. 
And same on the right. 
And if we do the Cartesian product of 
those, we have to take each possibility 
on the left and sequence with each 
possibility on the right. 
so there's six possibilities there. 
So that's an example of, a, use of the 
cartesian product and disjoint union, 
operations. 
So here's one just with uninary numbers, 
so, a an atom of cartesian product with a 
sequence of atoms is, gives that list and 
there's binary trees so in, external node 
kind of atom, crossed with an internal 
node kind of atom crossed with a little 
tree of size of one, gives a two tree 
node. 
that the, that's the kind of 
constructions that we're going to use. 
And those are interesting, and we'll see 
how to use those to precisely define 
Classes of interest 
But and unlabeled again. 
We'll talk about it later what we mean by 
that. but what's most important is the 
idea of a transfer theorem. 
and this is, the first basis of the 
symbolic method. 
The idea is while we're constructing the 
classes we're also developing equations 
for their generating functions because 
for every operation we have a 
corresponding operation on the generating 
function. 
and for simple unlabeled classes they're 
quite simple. 
So, for example, for disjoint union. 
If we take disjoint copies of objects 
from A and B, and we form the disjoint 
union, the OGF for that class is the sum 
of the OGF's of the two classes that were 
operans in. 
For cartesian product, it's the product, 
we'll do a proof of this in just a second 
and for sequence it's one over one minus. 
So whatever construction we make, we can 
translate that to an operation on the 
generating function, so anything that we 
can constrruct, we have a generating 
function for. 
so and, and these are the proofs. 
And these are very straightforward from 
the kind of GF generating function 
counting arguments that, that we did when 
we talked about generating functions. 
if gamma belongs to A plus B then it, 
they're disjoint copies. 
So some of them belong to A, some of them 
belong to B. 
you split the sum in those two ways, and 
you have A of Z plus B of Z. 
for cross product that's a convolution. 
Again, they break up into independently, 
into the ones from a and the ones from b. 
the size of [COUGH]. 
Since you've taken one from each the size 
of gamma is the size of the alpha-1 plus 
the size of the beta-1. 
and those are independent, so that's the 
product. 
in sequence fallouts from the idea that 
sequence is like a product of two product 
of three product of four. 
It's just the, geometric series gives the 
proof of the sequence. 
So that's the transfer theorems and 
that's the proofs. 
And from this point forward with a 
symbolic method we don't have to worry 
about sums involving convolutions 
anymore. 
[COUGH] whereas, 
[COUGH], we can get so we can or practice 
doing convolutions and so forth, but with 
this we can do multiple convolutions and 
we don't have to worry about carrying 
around those details. 
We know what the generating function is 
going to be. 
so let's just look at how it applies for 
binary trees. 
so, so every time that we're going to 
study a combinatorial class or we're 
going to do it according to this rubric 
here. 
So, we have to articulate what's the 
class its a class of all binary trees. 
What's the size function a comment of 
class is the set and that in the size 
function and that's we're going to use 
under internal nodes indeed. 
the ordinary generating function is the 
sum over all trees in the class Z to the 
size. 
and as we discussed when talking about 
counting with generating functions that 
for every size N there's going to be T 
sub N that gives us the counting 
sequence. 
the coefficient of Z to the N in the 
generating function is the number of 
trees, and that's what we're going to be 
looking for. 
we need atoms to get going. 
We have internal nodes and external 
nodes. 
so we'll denote external nodes by Z sub 
box, and internal nodes by Z sub dot. 
and we want to count according to 
internal nodes, the size of an internal 
node is one, the size of an external node 
is zero. 
so that's the set up, that's the building 
blocks on the generating functions of 
these little classes since the size for 
an external node is zero, it's one, the 
size for an internal node is one, it's Z. 
that's the generating function for that 
little class. 
Okay. 
So that's the setup. 
And then here's the construction. 
and this is just using the, union and 
Cartesian product rules. 
It, it, you can read it in English, or 
you can read it in math. 
It says, the binary tree is an external 
node. 
Or, it's a tree connected to an internal 
node connected to a tree. 
and that's what we mean by a binary tree. 
This just makes it rigorous 
So, that's the construction. 
So that's a, a description of the class 
of all binary trees. 
A recursive description, but it's a 
description of a class of all binary 
trees. 
And now what's significant is, we can use 
the transfer theorem to immediately 
translate to the generating function 
equation. 
Z sub box. 
The generating function is one. 
Generating function for Z sub dot is Z. 
Generating function for the two Ts is 
T(Z).z). 
And Cartesian product of those is the 
same as the, translates to the product of 
the generating functions. 
And no sums involved there. 
We don't have to do sums anymore to get 
generating function equations of this 
nature. 
Now the next step is to extract 
coefficients. 
We're going to talk about that a little 
later. 
I'll just remark that this is something 
that we've studied already, to finally 
get out to the answer that coefficient is 
E^Nn. 
And that function is asymptotic to 4^N 
over squared of pi N^3. 
but for, for now when talking about the 
symbolic method we're going to consider 
how do we get those generating function 
equations. 
That's the first part of analytic 
combinatorics the symbolic method. 
And well, let's look at lots of examples 
of that. 
And then later we'll talk about how do we 
get the coefficients out. 
So that's our binary tree analysis recast 
in terms of the symbolic method. 
All of the calculations that we did 
before are in there, but it's a much, 
much, much more general setting. 
And we'll see how important that is as 
the course goes on. 
so what about ki, just as a similiar 
example, what about if we want to count 
binary trees by external nodes. 
so that's a different combinatorial 
class, because it's got a different size 
function, and we denote that with box and 
T and the atoms are a little bit 
different, because we consider external 
nodes to be size one and internal nodes 
to be a size zero and the generating 
functions are different. So it's the same 
construction, but the atoms are different 
so we get a different generating function 
equation. 
It's a really similar generating function 
equation, actually T box to Z is ZT of Z. 
if you plug in ZT of Z of that equation, 
and divide by Z, you get the same 
equation as before. 
well, this is a proof that the number of 
binary trees within external nodes is the 
same as the number of binary trees within 
minus 1 internal nodes. 
there's easier proofs of that, but this 
is showing the consistency of the 
analysis and the ease of developing a 
commentorial construction to get a 
generating function in equation. 
Let's look at some other examples. 
What about binary strings? 
and just as a warm up, just to check on 
our understandings, and notation, and 
atoms and constructions, and transfers 
let's try to count binary strings. 
Now we know what the answer is. 
So our class is, the class of all binary 
strings. 
The size is, the number of bits in the 
binary strings. 
OGF, same as before, and same as always 
for every object in the class you add up 
Z to the size of that object and that 
brings the counting sequence as the 
coefficient of Z^N in that function. 
for binary strings, we have two atoms, 
either zero bits or one bits, that will 
call them Z0 and Z1 they are both of size 
one, and they both have generative 
function Z. 
So how many binary strings within bits? 
Well a binary string is a sequence of 
zero and one bits, that's what that says, 
that's the definition of binary strings. 
And now we go to the transfer theorem, Z0 
+ Z1 is 2Z. 
Sequence of 2Z, 1 / 1 minus. 
Binary strings of sequences are in one 
bits. 
And the transfer immediately gives us 
B(Z)z)=1/(1-2*z). 
= 1 / 1 - 2Z. 
and that checks, that coefficient of Z^Nn 
and B(Z) is 2^Nn, as we expected. 
Very simple and elementary as we'll see 
in just a minute how this translates to 
more interested, interesting and much 
more difficult to solve problems. 
just as an aside there's lot of ways to 
construct any combinatorial class. 
Here is an alternative way to do binary 
strings, same starting point or we can 
use this construction. 
A binary string is either empty, or it's 
a zero or one bit followed by a binary 
string. 
That leads to the generating function 
equation direct from transfer theorem 1 + 
B of Z = 1 + 2Z B of Z and if you solve 
for B of Z you get the same result. 
And so it's another way to do it. 
So again very simple constructions 
immediate transfer to OGF equations then 
it's just going to be a matter of 
extracting coefficients. 
so here's now the first example of a 
problem that might be more difficult to 
solve and it's representative of a very 
general treatment that we'll do in 
chapter eight. 
How many embed binary strings have no two 
consecutive zeros? 
actually there's a lots of practical 
applications where such questions are 
quite important. 
if, if we're looking for lots of 
consecutive zeros some types of 
communications devices have problems in 
such situations, and need to have codes 
that don't do that. 
And, and so, these things are, are well 
studied. 
And this is a simple example but it gets 
to be much more complicated very soon. 
That's what we'll talk about in chapter 
eight. 
but, still, 
let's take a look at solving this with 
the symbolic method. 
okay so it's the same, it's binary string 
so it's the same setup our class is than 
the class of binary strings that don't 
have any 00. 
we have the same setup for a generating 
function and the atoms are all the same. 
So what does the construction look like? 
While a binary string with no 00 is 
either empty or it's zero or it's one or 
01 followed by a binary string with no 
00. 
and you can check that that's a way to 
describe the class you have to think 
about a little bit but it's not too bad. 
and what's important though is that we 
don't have just an English language 
description, we have a combinatorial 
construction. 
Combinatorial construction immediately 
translates to a generating function 
equation. 
Z 0 across Z 1 is Z squared. 
Z 1 generating function is Z. 
[INAUDIBLE] plus Z zero generating 
function is one plus Z. 
So put all that together. 
Now we have a generating function 
equation for B zero, zero Z that we can 
solve and that's one plus Z over one 
minus Z minus Z squared. 
and again [COUGH] extracting 
coefficients. 
These are problems that we know how to 
solve. 
In this case, it turns out, and we'll 
look at the details later. 
In this case, it turns out to be 
Fibonacci numbers. 
11-e^-z^2) / 1 - Z - Z^2 is F sub N. 
Z is F1-e^-z^2) / 1 -1. 
Z - Z^2 is FN + 1. 
If you add FN + FN+11 you2. 
get FN+2 And that checks with the nth 
Fibonacci number, checks with the numbers 
that we found on the previous slide. 
Many of you probably noticed that it was 
Fibonacci numbers at that point. 
And, it's clear that this 
argument and this process is going to 
extend easily for binary strings with 
other kinds of restrictions. 
the trick is coming up with a 
construction that precisely describes 
your class. 
but often that's not difficult. 
And again we'll look at a general 
treatment of this later on in the course. 
So those are just some starting examples. 
we're going to have many, many, many 
examples, to follow. 
all with the same basis in one both part 
and part one and part two of the course. 
we're often asking how many of some type 
of objects are there, with some kind of 
restriction. 
we need to specify what the class is. 
We need to specify what the size function 
is and the atoms. 
and write down the generating function. 
And then we'll do a construction. 
that mirrors some English language 
description usually. 
That'll immediately translate to an OGF 
equation. 
and then the last step is to extract the 
coefficients and we'll talk about that at 
the end. 
So lot's of examples to follow. 
but before considering some more I want 
to talk about labeled objects, but that's 
an introduction to symbolic method.