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.