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.

Â