0:04

Welcome to Analytic Combinatorics, Part 2.

We're going to dive right into the material today, assuming that everyone

who's watching this has either taken Analytic Combinatorics Part 1 or has

watched the introductory video from analysis of algorithms to analytic

combinatorics that was posted before the class.

today we're going to start right out with ordinary generating functions in the

symbolic method. So a quick overview of what the analytic

combinatorics is. Again it's a calculus for analyzing

properties of large combinatorial structures.

So what we do is use the symbolic method that I'm going to talk about today to

define a class of combinatorial objects along with the notion of size and an

associated generating function and then we use standard operations, or

combinatorial constructions to develop a specification of the structure.

And the result is[UNKNOWN] via the symbolic method, a direct derivation of a

equation that has to be satisfied by the generating function, either an implicit

or an explicit equation. and then the classic next steps are to

extract coefficients and use classic asymptotics to estimate them.

And eventually get asymptotic estimates that quantify the desired properties.

this general approach is what we covered in part one, and is covered in our second

edition of our book Introduction to analysis of algorithms.

for part two we're going to talk about the symbolic method in more detail and

many other examples. but when it comes to estimating the

asymptotic values of the coefficient, we're going to use complex asymptotics.

We don't have to find an explicit solution and that'll be the second part

of this part two, where we'll talk about directly deriving asymptotic estimates

that give us the desired properties. and that's what the Analytic

Combinatorics book is all about. First part's about the symbolic method.

Second parts about asym deriving directly asymptotic estimates of, of the

coefficients. so the overview is a bit like this.

These are the eight chapters that we're going to talk about.

the symbolic method there are three chapters, ordinary generating functions,

exponential, and multi-various. and then some chapters on complex

analysis. and the idea's that when we have the

specification, we start with the specification, then symbolic method is

the process that gives us a generating function equation.

and complex asymptotics gives us another set of processes that immediately give us

the asymptotic estimates that are our desired result.

3:05

so today we're going to talk just about the symbolic method and for the next

couple of lectures. and again, there's some easier examples

that moves a bit slower in part 1 and in analysis of algorithms in the purple

book, Analytic Combinatorics, has a very rigorous treatment.

this lecture is somewhat in between, it's an overview that assumes some familiarity

with generating functions and basic mathematics; like, like it's covered in

part 1 of this course. If you move, find that we're moving a bit

quickly refer back to Analysis of Algorithms book.

[COUGH] . If you find that we're moving a bit

slowly read chapters one, two, and three of Analytic Combinatorics.

And then within a lecture or two we'll all be moving at the same pace, I think.

So basic definitions. A combinatorial class is a set of

combinatorial objects and an associated size function.

That's our starting point that's our object of study.

in the, today what were going to talk about is a, as a primary object of study,

the ordinary generating function associated with the class.

And that's a formal power series, where you have a variable c and use some for

all objects in the class z the to size of that object, that's the ordinary

generating function. So the size function is like an absolute

value just says that's like the size of the object.

[COUGH]. And then the class name, the class name

is usually a capital letter with the same letter as the generating function.

and then the object name is usually a lower case letter of the same letter.

[COUGH]. Now there's a very elementer elementary

identity that's fundamental to all the manipulations of the symbolic method.

And that is, this generating function where we look at all the objects, raise z

to the size of the object. that's equal to summing for all n the

number objects of size n times z to the end.

because if there's A sub N objects size N, then there's A sub N terms on that

left hand side one for each object of size N and collect them together you get

A sub N Z to the N. And that's a fundamental identity that

we're going to work with. And our goal is to find good estimates of

this value A sub N. And we refer to that as with the notation

square brackets Z to the N, that means the coefficient of Z to the N in A of z,

that's A sub N. and again I mention the conventions,

usually we try to use a roman letter for the class name.

for the generating function name, it's the same letter with an argument.

Uh,[COUGH] for in the book we use a slightly different font.

object variable is just lower case of the same letter and then the coefficient is

subscripted of the same letter. Uh,[COUGH] and size we usually use

capital N or little N and this kind of adopts a fantasy that we have a different

letter for each class but actually there's only 26 letters.

And we look at way way more classes, so sometimes we have a conflicts in these

names. but we do the best we can.

Now so with the symbolic method, what we can do is specify the class and at the

same time characterize the generating function.

that's the process that we want to talk about today.

Uh,[COUGH] so there's a number of basic combinatorial objects that are

characterized well by ordinary generating functions and they're called unlabeled

classes, and we'll talk about that distinction later.

so integers or strings which are sequences of characters, recursive

structures, trees, languages. and then compositions and partitions

which are compositions are positive integers sum to add, and partitions are

unordered compositions and we'll look at all of those soon.

7:30

so, to describe those communotorial classes, we use basic operations or

constructions. so if we have two classes A and B of

unlabeled objects, and again we'll talk about what that means later on, that have

the generating functions A of Z and B of Z, then we can perform some natural

operations on them so the disjoint union is just take object from A and an object

from B. And be uh,[COUGH] that makes a new class

and the ordinary generating function of that class is just sum the two generating

functions. and then there's a Cartesian product if

we take a pair of copies, one from A, one from B, then we get a class whose already

generating functions, the product of the two generated functions.

And the proofs of these are easier, we'll look at them in just a second.

And then there's sequence which is applied the product multiple times taken

either none or one or pairs or triples any sequence of objects from a class,

then you get another class whose generating function 1 over 1 minus A of

z. Those are, with those basic constructions

we can describe quite a rich set of combinatorial classes but we also have

many other constructions and we'll look at some today.

Uh,[COUGH] so here's just the proofs about the generating functions.

so for A plus B, if you have an object that belongs to either A or B and you sum

over all objects in A plus B. Then you can split the sum into two

parts: the ones from A and the ones from B, then, by definition then, that gives

you the sum of the two generating functions.

for cartesian product, it's slightly more complicated but not much.

if you take an ordered pair of objects from a be all ordered pairs and you sum

over all ordered pairs then you can treat that as a convolution of two sums.

9:46

and since there's one from A and one from B and we're combining them, then the

object that's the ordered pair, the size of that object, is the sum of the sizes

of the two objects that we combine. and those are independent, so we can just

split those sums and get the product. so the generating function for the

Cartesian product is the product of the generating functions.

and for sequence well [COUGH], if you take a sequence of size k, then just

extending the product operation, you get A of Z to the K.

and sequence is 0 plus 1 plus so forth,[INAUDIBLE] actually for any

seqence of integers and so if you take any size, it's just 1 plus A of Z plus A

of Z squared and so forth, which is just 1 over 1 minus A of Z.