Today we're going to talk an introduction to analytic combinatorics. 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'll see it builds upon all the things that we've talked about to this point. It gives us a coherent starting point from where we can go forward in the analysis of algorithm and the analysis commentarial structures. And I hope that by the end of this lecture you will have a pretty good idea of what analytic combinatorics actually is. I'll just start with a brief overview. With the analytic combinatorics it's a calculus for the quantitative study of large combinatorics structures. In most of the work behind analytics combinatorics is set forth In our book Analytic Combinatorics that will be the basis for part two of this course. But it also plays an important role in the analysis of algorithms and the tie between elementary combinatorics and the kind of analysis that we need to really study computer programs. So 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 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 I mentioned last time our asymptotics 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. In 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 combinatorial 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 theorem to get our coefficient asymptotics directly. [COUGH] Essentially, this process allows us to avoid a lot of the detailed 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 of binary trees within nodes. There's a combinatorial construction 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 too, and you'll understand everything that goes behind the transfers. So the beginning point is this symbolic method, so we'll start by talking about the symbolic method. Now, it's in approach number one, for defining common thorough 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 coefficient count objects of the same size. Now that's what we've been doing in generating function counting in several examples already. Then we're going to define operations that allow us to give constructive definitions of objects. And then from those operations, we're going to have translations for each operation that defines a construction to an operational generating function. And this is just the kind of notation that we use. Upper case letter for combinatorial objects. Some notation, like absolute value for size. And then generating function we'll add the same letter as the class, except it'll 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 after these definitions we'll do examples and you'll see the need for this. But it's a good thing to talk about them right at the beginning so what is a combinatorial class? It's just a set of objects, and a size function. Now, we have to have something to begin with, and we call those atoms. Those are objects of size one. We also, for convenience, have a atom of size zero. Which is a neutral object, and that's useful for describing, you will see that is useful for recursive definitions. So a combinatorial construction uses the union, product and sequence operations that I will talk about in a minute to define a class. In terms of atoms in other classes. And we start with the very based building blocks over in the right where the notation capital Z is in a contains a single atom. Then there's notation capital E which is a neutral class that contains an atom of size zero and then there's also an empty class. And again, it's not worthwhile to spend time on these definitions right now but to refer back to them when we use them later on if necessary. So here's a very simple example of a combinatorial class with natural numbers. So the 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're getting to that detail and more, much more detail later. It's a set or sequence, it's the same thing. So, there's only one object of each size. So we most usually at the beginning we're most interested 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 one over one minus z. So that's a simple example of a common notarial class. And actually it seems trivial when the base the early ones do seem trivial it's when you put them together that you get interesting useful mathematical results. So for example, this kind of notorial class is a basis of study of things like partitions of natural numbers, how many ways can you break them up into sum and compositions and so forth? We don't get into that too much. Show in part one but we will in part two. Here's something 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 familiar class had to get used to our 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 2 to the n, z to the n, which is 2z to the n, or 1 over 1- 2z. So that's another example of a combinatorial class. Here's one, a familiar one, recast in terms of analytic combinatorics. So a binary tree is empty or it's a node in two binary trees, that's better in sequence, the order matters. So those are familiar binary trees that we studied before. We know the counting sequence is the catalan numbers. That was a subject of quite a bit of lecture three. And its got the 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, and again, I'll talk about the distinction with labeled in a minute. We're just going to use three different constructions. If A and B are combinatorial classes of unlabeled objects then we have the disk joint union, a Cartesian product in the sequence operations. On here is the meaning of each one of those. A + B is just copies of objects from A and B. You take one from A, and one from B. And that's the disjoint union. Cartesian product is ordered pairs of copies of objects, one from A and one from B. And sequence is sequences of objects from A. So, those are the constructions, and these are just examples of how a construction might work. So for bit strings, maybe you could use the usual distributive law. So (00 + 01) is got copies of 00 and 01. 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 unary numbers, so an atom Cartesian product with a sequence of atoms gives that list. And there is binary trees. So an external node kind of atom crossed with an internal node kind of atom. Crossed with a little tree of size one. Gives a 2 tree node. 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 unlabeled, again, we'll talk about 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 OGFs of the two classes that were operands. For Cartesian product it's the product. All right, we'll do a proof of this in just a second. And for sequence, it's 1 over 1 minus. So whatever construction we make, we can translate that to an operation on the generating function. So, anything that we can construct we have a generating function for. And these are the proofs, and these are very straight forward from the kind of generating function counting arguments that we did when we talked about generating functions. If gamma belongs to A + B, then 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(z) + B(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, 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 follows from the idea that sequence is like a product of 2, product of 3, product of 4, 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 the symbolic method, we don't have to worry about sums involving convolutions anymore. Whereas, we can get so our practice of 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 every time that we're going to study a combinatorial class we're going to do it according to this rubric here. So we have to articulate what's the class. It's a class of all binary trees. What's the size function? A combinatorial class is a set and a size function. And we're going to use then internal nodes in t. 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 1, the size of an external node is 0. So that's the set up, that's the building blocks. The generating functions of these little classes, since the size for an external note for 0 is 1. Size for internal node is 1 it's z. That's the generating function for that little class. Okay, so that's the set up. And then here's the construction. And this is just using the union and Cartesian product rules. You can read it in English or you can read it in math. It says a 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 description of a 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 in the generating function is 1. Generating function for Z sub dot is Z. Generating function for the two Ts is T(z). Any Cartesian product of those, it translates to the product of the generating functions. So 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 studied already. Then finally get out to the answer that the coefficient of Z to the n and that function is [COUGH] asymptotic to 4 to the n / square root of pi N cubed. But 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 we'll 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. Just as a similar 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 of t. And the atoms are a little bit different because we consider external nodes to be size 1 and internal nodes to be a size 0. 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 (z) is Zt(z). If you plug in Zt(z) in 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 -1 internal nodes. There's easier proofs of that, but this is showing the consistency of the analysis and the ease of developing a commonatorial construction to get a generating function equation. Let's look at some other examples. What about binary strings? And just as a warm up, just to check our understanding of the notation and atoms and constructions and transfers, let's try to count binary strings. And we know what the answer is. So our class is the class of all binary strings. Size is the number of bits in the binary string. OGF, same as before, 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 to the N in the function. For binary strings, we have two atoms, either 0 bits or 1 bits, we'll call them Z0 and Z1, they both have size 1, and they both have generating function Z. So how many binary strings within bits, well, a binary string is a sequence of 0 and 1 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-. A binary string is a sequence of 0 and 1 bits. And the transfer immediately gives us B(z) = 1 / 1- 2z. And that checks the coefficient of Z to the N of B(z) is 2 to the N, as we expected. Very simple and elementary, as we'll see in just a minute, this translates to a more interesting and much more difficult to solve problems. Just as an aside, there's lots of ways to construct any commentorial class. Here's an alternate way to do binary strings, the same starting point, but we can use this construction. A binary string is either empty, or it's a 0 or 1 bit, followed by a binary string. That leads to the generating function equation direct from transfer theorem, 1 + B(z) = 1 + 2zB(z). And if you solve for B(z), you get the same result. So it's another way to do it. So again, very simple constructions, immediate transfer to GF equations. And then it's just going to be a matter of extracting coefficients. [COUGH] So here's now first example of a problem that might be more difficult to solve. And it's representative of very general treatment that we'll do in Chapter 8. How many N-bit minor strings have no two consecutive 0s? Actually, there's lots of practical applications, where such questions are quite important for looking for lots of consecutive 0s, some types of communications devices have problems in such situations, and you'd have codes that don't do that. And so these things are well studied. And this is a simple example, but it gets to be a much more complicated very soon. That's what we'll talk about in Chapter 8. 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 set-up. Our class is the class of binary strings that don't have any 00. We have the same set-up for generating function, and the atoms are all the same. So what does the construction look like? Well, a binary string with no 00 is either empty or at 0, or it's 1 or 01, followed by a binary string with no 00. You can check if that's a way to describe the class. You have to think about it a little bit, but it's not too bad. And what's important, though, is that we don't have just in English language description, we have a combinatorial construction. Combinatorial construction immediately translates to a generating function equation. See 0 cross Z1 is Z squared, Z1, our generating function is Z. At + Z0, generating function is 1+z. So put all that together, now we have a generating function equation for B00(z) that we can solve, and that's 1+z / 1-z- z squared. And again [COUGH] extracting coefficients, now 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. 1 / 1-z-z squared is Fn. Z is F / 1-z-z squared is Fn+1. If you add Fn to n+1, you get Fn+2, and that checks with the anti-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 both part one and part two of the course. And 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. Then we'll do a construction that mirror some English language description usually, and that will 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 lots of examples to follow. But before considering some more, I want to talk about labelled objects. But that's an introduction to symbolic method.
