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. 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. 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. 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. so that's the correspondences for the basic operations that show that if we apply one of these operations, then we immediately imply a relationship on the generating function. and again if you find this proof a bit confusing and you want to see some more basic examples please take a look at chapter five of our Introduction to Analysis of Algorithms book. We're in part one of the Analytic Combinatorics course. [COUGH] so that's a quick introduction to the symbolic method.
