0:31

So this is the our next to last lecture. [COUGH] next time we'll talk about saddle

point, which is for generating functions that have no singularities.

But we're, we're going to talk about lots of the combinatorial classes that we

considered in part A. where we have a generating function

equation that's not rational or meromorphic that has singularities other

than poles. and last time, we saw a general approach

to dealing with such functions but that lies underneath some very broadly

applicable. schema, and that's what we're really

going to be talking about today. so the first one is Simple varieties of

trees. And we've talked about that a couple of

applications last time, so let's just look again.

so we start with this transfer theorem that's proved with the singularity

analysis process developed by Flajolet and Liskow in 1990.

but that all, all that mechanism kind of lies underneath.

so, if the idea is, we have, a, whats called a simple variety of trees.

Where the combinatorial construction is Z.

with a product, either cartesian product or a star product.

of a sequence, a recursive sequence of the same class, where there's some

modifier that says what sizes of sequences to use.

so, there's this idea of lambda invertible, you know where there's a few

technical conditions. But the main one is that we define a

function fee which comes right out of the, symbolic method from the

construction into a generating function equation.

So, the sizes of sequences that we use translate into different functions, phi.

so the construction defines the function phi.

and that's a so-called, characteristic equation and lambda is the root of this

equation. phi of z equals lambda phi, equals z phi

prime of z. So if we have that value lambda, then we

have the coefficient asymptotics and the function phi, and it's a function of the,

first of all, the coefficient growth is just v prime of lambda.

The exponential growth is just v prime of lambda to the n.

And then the constant is a simple calculation involving the second

derivative evaluated at lambda. and it's also the case that the

singularity analysis gives us an approximation to the function itself.

and that's going to work out to be important in applications later on in

this lecture. so it says that a simple variety of trees

has a square root singularity. And we can accurately approximate both

the function and its coefficients at that singularity.

And as always with singularity analysis, we can take these approximations out to

arbitrarily arbitrary many terms. in lecture we'll just work with the tilde

approximation. And this applies to any kind of tree.

virtually any kind of tree, and we'll look at several examples next.

So important to note is and as I just mentioned that the singularity ana,

analysis gives you not only the coefficient asymptotics, but also

approximation of the function nears its dominant singularity.

and that's automatic. This is a schema that works for any, any

kind of sequence. and so as usual in most applications what

we're going to be focusing on is the calculations involved in the coefficient

asymptotics. And these are quite simple calculations.

For example, we looked at general trees, and again, back in part 1 of this course,

we looked at general varieties of trees. And there are certainly a lot of

calculations involved in finally getting out the coefficient asymptotics.

There's information between in terms of it's catalan numbers and Sterling's

approximation and other things But doing that calculation from scratch

involves certainly a fair amount of of a discreet Mathematics.

and the idea of Analytic Combinatorics is we can get that coefficient asymptotics

in just a few simple steps. this is a review of last lecture, but

maybe some people are watching this lecture for the first time.

So, a G is the class of rooted ordered trees that's just the construction is

cartesian product of Z and a sequence of trees.

And tree is a root in a sequence of trees that immediately translates to the

generating function equation. G of z equals Z over 1 minus G of z.

Now we're going to apply the theorem for simple variety of trees.

And what that means is we first have to identify the characteristic function.

That's 1 over 1 minus u, we compute its derivatives.

so that's easy, 1 over 1 minus u squared and 2 over 1 minus u cubed.

5:54

and then we get the characteristic equation which is 1 over 1 minus lambda

equals lambda over 1 minus lambda squared, that's setting phi prime, equal

the phi equal to lambda phi prime and you get lambda equals one half.

And then evaluating the characteristic function and its derivatives at lambda we

get 2, 4 ,and 16. And plug in those values, we immediately

get the co-efficient asymptotic. Now 4 to the n of three halves over

4square root of pi. so that's our, our pattern.

That's our template for Analytic Combinatoric that we strive for for every

problem. They have a construction, take us right

to a function generating equation. Take us right to coefficient asymptotics

and that's what the simple variety of trees transfer theorem does for this

example. so what about binary trees?

That's another familiar example that we've looked at since the early lectures

in part one of this course. well, one way to construct Binary trees

is to say it's an external node. Or it's an empty tree.

or a binary tree on the left or an empty tree or a binary tree on the right.

you might have been expecting some construction like a binary tree, is like

a node or a node in a sequence of either zero, or two binary trees.

That's another way to construct binary trees.

we'll actually look at that one later on. but this one translates right to the

generating function equation, B of z equals z times 1 plus B of z squared.

If you have z times the function involving the original on the right then

that's simple variety of trees. so we take the simple variety of trees

theorem we have to identify the characteristic function.

In this case it's 1 plus u squared. compute the derivatives, 2, 1 plus u, and

2. characteristic equation.

fi of u equals, equals u phi prime of you and that, now works down to this

equation. that lambda squared and through lambda

comes out lambda equals one. And then evaluate the characteristic

equation and its derivatives at lambda and we get 442 in this case.

and so that means the exponential growth is 4 to the n.

and the two is canceled. and we simply get one over square root of

pi four to the n, n to the three halves. Again, media transfer from the

construction, to a generating function equation, to coefficient asymptotics.

that's Analytic Combinatorics. in here's another example review from

last lecture that's those first 2 examples we know how to do with

relatively elementary methods. this one examples like this are much

harder. So this is Unary-binary trees where a

tree has either 0 every node has either 0, 1, or 2 children.

So a tree is a node. Plus a sequence of either zero, one, or,

or two, trees. so that's, simply expressed.

immediately translates to, the generating function equation.

M of z equals z times 1 plus M of z plus M of z squared.

that's a simple variety of trees. So we identify the characteristic

equation, one plus u, plus u squared. Compute the derivatives, 1 plus 2 u and

2. characteristic equation if you set v of u

equal to u times v prime of u and solve. in this case it's lambda equals 1 again.

1 plus 1 plus 1 equals 3, 1 plus 2 is 3. Then, evaluate the characteristic

function, and it's derivatives, add lambda and we get 332 in this case.

So phi prime is 3, so that means 3 to the n is the exponential growth.

and in this time, the constant turns out to be square root of 1 over square root

of 4 pi over 3, into the three halves. So all simple varieties of trees are

going to have N to the three halves. They're going to have exponential growth,

and the difference is what's the factor and what's the constant.

again, straight from the spec. To the generating function equation to

the coefficient asymptotics without anything in between.

Now there is a lot of machinery under there in terms of the singularity

analysis process Lagrange was in there to prove this.

quite a bit of sophisticated mathematical machinery was necessary to establish this

transfer theorem. But once it's proved it's very easy to

apply and that's the theme of this whole lecture.

Sure we have some very applicable transfer theorems that are quite easy to

apply and can lead to the analysis of all sort of combinatorial structures that

would be very, very difficult to analyze otherwise.

and just to finish the story, this is simple variety of trees also works for

labelled structures too. so we looked at Cayley trees, so that's

labelled rooted, unordered trees. and so there's N to the N minus 1, we

looked at this in lecture two. so this is the analysis that we did in

lecture two and I'm just going to flash through it.

So it's a, a Cayley tree is a root-connected to a set of trees

And for the labeled structures, the transfer from the construction into the

generating function equation is for exponential generating functions.

in SET means take e to the power, so we get c of z equals ze of c of z.

and then in lecture two we used Lagrange inversion theorem.

to get the coefficients out, in [COUGH], that eventually getting to into the N

minus 1 for the number of Cayley trees. [COUGH], so it's in factorial times that

coefficients, N to the N minus 1. so in that certainly a valid way to

extract coefficients. but my point for this lecture is that we

don't need different tools for every type of trees.

We've one term that works for all type of trees.

So lets look at Cayley trees from the stand point of a simple variety of trees.

same construction its a node is a node star product with the set of nodes.

so that same translation, C of z equals ze to the c of z.

But now as the simple variety of trees, this one's even simpler than the ones

that we just looked at. we can it satisfies z star product

sequence or set of something. and so we immediately get the

characteristic function phi of u equals e to the u.

The derivatives are all e to the u so as long as our generating function has this

form then the rest of the theorem comes through.

so our characteristic equation is either the lambda equals lambda e to the

lambda's. So lamda's 1.

and then plug in to evaluate the characteristic function of the value 1.

You get e all the time, so phi double prime over phi is just e, and phi prime

is e so it's e to the N. So, immediately, get 1 over square root

of 2 pi e to the N, N to the minus three halves, immediately.

boom, boom, boom, for Cayley trees, using the same theorem that we use for General

trees, or Unary-binary trees, or any kind of tree.

Just a matter of figuring out the characteristic function, doing the

derivatives. Solving the characteristic equation,

plugging back in into the formula. it's a very general and significant

theorem. You don't need to know the underlying

mechanisms behind it, in order to get coefficient, asymptotics.

You can work at a different level, which is a level closer to the problem.

How do I construct my constructure, my structure, and what's how can I estimate

the number of structures of that size? and then I can use that information for

all sorts of things, like taking a log to find out how many bits there needed or

other information. And we'll, we'll talk about examples in a

little bit. So just as an aside, to show that

everything's hidden under the covers. Even Stirling's formula's hidden under

the covers. we looked at the exact derivation through

Lagrange inversion. and then, in this lecture, we talked

about the approximate derivation through singularity analysis.

The exact one says we get into the N to the N minus 1, the approximate one says N

factorial e to the N over square to 2 pi N cubed.

so that's, those derivations are a proof that that holds, and that's just

Stirling's formula. so counting Cayley trees in two different

ways gives us Stirling form-, Stirling's formula.

That's, that's one way to look at it. but that's really, in today's context,

what we're interested in is the, we took 4 pretty different types of trees and got

coefficient, full analysis of them. Including down to coefficient asymptotics

using the same theorem. that's an introduction to schema based on

singularity analysis.