1:29

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.

Â 3:23

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.

Â 6:14

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.

Â 6:57

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.

Â 7:49

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.

Â 8:32

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.

Â