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.

Â