Just want to finish up, by talking a little bit, giving some perspective on the things that we've talked about so far today. So, [COUGH] the idea is that we have a calculus that is going to be very effective for quantitative study for all kinds of large combinatorial structures. Always going through the same kind of process where we have a construction that translates to a generating function that translates to coefficient asymptotics. Actually, with complex asymptotics we don't even have to solve explicitly for the generating function often. Merely the form of the equation is going to give a generating function that is going to give a trace for it there. That gives us the coefficient asypmtotics immediately. And just think about what we've talked about in the last four lectures versus this lecture. The count binary trees, so we hit a whole slide to go from recurrence to generating function involving convolution. And then, expanding that generating function, involves some kind of intricate calculations, using binomial coefficients, that you might remember. That got us to the exact form of the Catalan numbers. And then we had to do the asymptotics using Sterling's approximation that also involve a significant amount of calculation. Now you may remember the first time you saw each one of these, the amount of intricate calculation that seemed to be involved, although there's straightforward from step to step, there's a lot of steps. With analytic combinatorics we don't do those calculations anymore, we simply create the combinatorial construction. Get to the generating function equation and then get the transfer theorem to get the asymptotic result that we're interested in and these are normally very accurate and certainly accurate enough for practical applications. So for derangements we didn't even do the calculations. So complicated, but we can get immediately to the coefficient asymptotics. And this is a good example of something that is characteristic of analytic comment work. Because we had a basic construction permutation from a set of cycles that we'd modify to work with, to get this answer, that's very common. We start with some fundamental constructs that are basic things that we want to study. They're either elementary, or they're trivial, or they confirm our intuition and we understand them. But we try to understand them from the standpoint of analytic combinatorics. But then, we can have compound constructs, where we have a set of cycles, or a sequence of sets, and so forth. And again those are only the constructions that I've presented. There's many, many other constructions available. In those things, there's lots of possibilities. They'll tell us something about the structure, like a permutation is a set of cycles. And actually lots of classic combinatorics can be dealt with in this way. And then there's variations, like generalizing the arrangements by adding another parameter. The possibilities immediately become almost unlimited. And not only that, when we get to a generating function equation, we often have a universal law that will give us the asymptotics. There'd be no way to go in and get the exact result and then do asymptotics from the exact result. In principle, you could do that because what underlies analytic combinatorics is a bunch of very simple techniques, but why would you if your goal is the asymptotic result? So that's a very standard paradigm. And also, combinatorial parameters can be handled, and we'll see lots of examples of that. And so that is, we're not just counting things, we're counting properties of things. But we talked about, in the generating function lecture, about the concept of cumulating costs where rather than computing averages by using probabilities what we do is we count up the total cost among all structures and then divide. And it's reducing, finding an average for a number expected in a random object to two counting problems. So to find the leaves in a binary tree, we count trees using the standard process to get to the estimate of the Catalan numbers. But it turns out that the symbolic method works for bivariate generating functions so that same construction will give an explicit equation for the total cost. So that's the leaves in all trees. You just keep track of the leaves in another variable and the same construction follows through, and then differentiate a value at a one to get the leaves on all trees the way that we did before. We're going to get again an explicit and then we have immediate transfer for that one too. So now we don't have to go into the detail, we have these two asymptotic results and then we just divide. And that's how we get to N over 4. And again, we can do this without all the detail that we presented before. So, this is the slide that I started up with maybe it makes a little more sense now that we've going through a number of examples. Analytic combinatorics we begin with combinatorial constructions. We used symbolic transfer terms to get generating functions they're the central object of study because transferred to them from combinatorial constructions. And we extract coefficients from them using analytic transfer theorems. And so, within principal, we can do this to any precision on the standard scale, and we can handle variations as well. So now, for the rest of the course, we're going to be looking at, many applications of analytic combinatorics. First we'll do trees, and then we'll do permutations, which actually can be represented as a certain kind of labeled trees. And we'll talk about bitstrings in associated data structures in mappings which are fascinating structures. And these all have applications to the analysis of algorithms. So that's what we'll be doing for the rest of the course. So that's a perspective on what we've been doing. I just want to finish with some exercises that you might do to cement your understanding of this material. So exercise 5.1 is, how many bitstrings of length N have no occurrence of three 0s. And that's a fine exercise to try out these techniques on. Or for trees, and this is just again to go through the steps of [COUGH] analytic combinatorics for problems similar to the ones that we did. So this is binary trees where the size is the total number of nodes, internal and external. So there's no even numbers, it's always an odd number of total number of nodes. And so you get an expression for that. Permutations, what about when the cycles are all of odd lengths? That's an easy one. Tree parameters, so the red nodes here have both children internal. And the blue ones have one internal and one external. So what's the average number of red nodes and blue nodes? We already did the average number of leaves is like N over 4 so those are similar problem. So for the next lecture if you read solutions to those exercises and read the analytic combinatorics chapter in the text. You'll have a good feeling for the basis for of an analysis of algorithms that we're going to begin starting in the next lecture.