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.