0:00

We're going to finish off our study of applications of singularity analysis by

Â looking at another scheme of, of, that's generalizes the simple variety of trees

Â and covers again A whole host of a whole family of commenotorial classes called

Â tree like classes. So for implicit variety of trees we said

Â if you get the generating function of the form f of z.

Â Equals z times phi of F of z, a root and some stuff.

Â That's a tree, that's a, a simple variety of trees.

Â then we can go ahead and analyze it. So for implicit tree-like we say, well,

Â if you have a, any function of z and F of z, it doesn't just have to be z times F

Â of z. and then that's what we're going to call

Â an implicit tree like class with characteristic function phi.

Â on label case, a number of structures is Z to B and F of Z.

Â So we can have any constructs that are a plus [UNKNOWN], a product and sequence.

Â in the label case the number of structures [UNKNOWN] again you can have

Â any set of constructs where its an arbitrary composition of our basic

Â operation sequence set and cycle. all of those things are going to come

Â down to a generating function function equation of this Form immediately by a

Â symbolic transfer. And we'll look at, some examples of this

Â in just a minute. so, and as I've pointed out, this

Â generalizes simple varieties of trees, where if we just take our general

Â function capital phi to be Z times little.

Â Phi w that's gives simple varieties of trees.

Â Here we're allowing arbitrary functions of z and F of z implicit tree like

Â classes. Now we have this smooth implicit function

Â condition again for all of our schema. We have some technical condition we have

Â to make sure is satisfied in order to be able to push singularity analysis all the

Â way through. Usually the technical condition involves

Â eliminating trivial cases but there's also periodicity.

Â in problems with singularities the same distance from the origin that also are

Â involved in these, again, so, here's what it is for implicit tree like classes.

Â So we've got our tree like class concept of f that generating function phi of z is

Â f of z so we say it's smooth implicit. If it's characteristic function satisfies

Â conditions and here's the conditions. Well it's got to be analytic in a domain

Â with its two values uh,less than some values, r and s, so that's and these

Â functions are usually very simple functions, so that's not a problem.

Â so it's gotta be non-negative, and it's gotta actually not be zero for some

Â values. So that's again removing degenerate

Â conditions. I won't spend time on that.

Â 3:22

And there's a characteristic system, not just a characteristic equation.

Â it's got two, values. And so if you take phi of R of this

Â equals S. And the derivative which respect to W phi

Â over R is S equals one, and you solve that, cares, characteristic system and

Â you get good solutions that are reals, positive reals.

Â then that's what's smooth implicit function is.

Â that's the main condition, this characteristic system has to have a

Â solution in real, in the domain of in-elasticity of the function, and again

Â these functions as we'll see are usually pretty simple.

Â 4:02

so here's an example of a tree-like class and we'll look at this later on.

Â This is phylogenetic trees it's called. So L is Z plus a set of at least two Ls.

Â so that's the z set of at least 2. We take e to the l o z and then subtract

Â off 1, and subtract off l o z. So that's not a simple variety of trees.

Â It's not z times something, it's this complicated function.

Â so but that's fine. It is a implicit tree-like class because

Â the characteristic function is Z minus one plus E to the W minus W and then we

Â can write down the characteristic system, which is set that equal to W and set,

Â derivative with respect to W equal to one.

Â So, Z minus one plus EW minus W equals W. the derivative of this with respect to W

Â is just either W minus 1, those go away. E to the W minus 1 equals 1.

Â That's easy to solve. That means E to the W equals two or W

Â equals log 2 as a solution so S equals log 2 and then we plug the log to into,

Â into the other one and we get R equals 2 log 2 minus 1.

Â So we found the characteristic system. It's got a solution that's real so that

Â means that phylogenetic trees are smooth-implicit with those parameters R

Â and S. and It all depends on this characteristic

Â function and the characteristic system. Again, if we can establish this, which

Â often we can with, in a simple calculation like this, then all the work

Â of singularity analysis, of finding the delta domain and Approximating the

Â functions and so forth is all under the covers and we can immediately get the

Â asymptotics. And so, this is the theorem for

Â asymptotics of implicit tree-like classes.

Â We have implicit tree-like class. It's a periodic Again, you can't have

Â any. regular occurrence of of a coefficient in

Â there. And that's discussed in the book and

Â we're ignore that in lecture. so it's smooth implicit with parameters r

Â and s so that phi of r and s equals s, and phi sub w r

Â and s equals 1. Then it's going to, then r is is place

Â where it's got a square root singularity. And we can approximate the generating

Â funciton at that singularity by s minus alpha square to 1 minus z over r.

Â And that approximation gives us the coefficient asymptotics.

Â A, which is one of our N and N minus three halves times a constant, and that's

Â how to compute the constant. A, so, very similar to, a, for simple

Â variety of trees its just more complicated, on complication of the

Â constant. And that, oh that more complicated, a,

Â again, a, we've got coefficent asymptotics now.

Â 8:01

So that gives the characteristic function Z plus W squared.

Â There's the system and S equals a half, R equals a quarter.

Â Then we can compute the derivatives in the alpha and immediately get out the

Â coefficient and asymptotics just as before.

Â So that's a transfer appearing for how implicit tree-like classes in binary

Â trees as a simple example. so, let's just look at a complicated

Â example. A famous complicated example leads to

Â what's called Schroder numbers. A German mathematician called Schroder in

Â the 19th century studies a lot of problems like this and this is one so,

Â bracketing of N items is a tree that's got N leaves.

Â So the black ones are the leaves here and no unary nodes.

Â So and there's lots of applications of this, that are described in the book on

Â page 69. so how many bracketing within leaves so

Â here's all the breacketing. Say wiht three leaves, you can have a

Â [UNKNOWN] three or you can have two in left or two in the right.

Â again no unary nodes all nodes are either degree 0 or the degree 2 or more in the

Â sizes the number of leaves so its the 11 of size 4 and so forth.

Â that's equivalent to the number of ways of parenthesize an n items.

Â in part one of the course we talked about correspondences between trees an

Â parentheses systems. an if you go back an forth between these,

Â these slides you can see the correspondence between, bracketings an

Â ways of parenthesizing in items. So here all four are in the same

Â parentheses system. down here we have three with one on the

Â right or One on the left and then three, and so forth.

Â so that's where Charter was actually interested, was parenthesizations.

Â there's many other ways to look, look at this.

Â and-or conjunctive propositions are trees where and and ors,

Â alternate or what's called Series-Parallel Networks.

Â All of these things are equivalent to Bracketings.

Â So they are found in all sorts of different applications in combinatorics.

Â So what does it look like from the standpoint of analytic combinatorics?

Â Well a bracketing is a node or a sequence of more than one bracketings.

Â it's interesting to note that that combinatorial specification is probably

Â the most succinct way to describe what a bracket is.

Â and that's often true in analytic combinatorics.

Â We're talking about suc-, succinct ways of specifying things, and it turns out

Â that those lead us directly to automatic ways to enumerate 'em.

Â but that certainly is an important important part of the science is what is

Â it that you're trying to count? You need to specify and want to do it

Â succinctly. And [UNKNOWN] constructions are not a bad

Â mechanism for that. so, as usual, that translates immediately

Â to the generating function equation, so we have to subtract of the size zero and

Â the size one. And we could go ahead and solve for that

Â and, and so forth. But, the implicit tree like classes says

Â you don't really have to go ahead and solve for that.

Â What you have is your function is expressed as a function of Z in itself.

Â That's all you need to see. and as soon as you see that, then you can

Â get the coefficient asymptotics. I'm not going to do the details for this

Â example. that's left for your exercise for this

Â week. I'll do a more complicated one.

Â 12:08

[COUGH] This is more [INAUDIBLE] slightly more complicated, it's not that much more

Â complicated. It's a labeled version of the same

Â problem. so actually you have a lot of labeled

Â [INAUDIBLE] leaves, and. you're trying to collect them together

Â and provide a heirarchy in some way. And this turns up in lots of scientific

Â and commercial complications related to evolution and in many other things.

Â And it's another problem for study in the How 19th century.

Â so many applications of this sort of thing.

Â so this is the number of different labeled hierarchies of N nodes.

Â we're now, there's not only different shapes but now there's different labels.

Â So you can put one two four together and three apart and that leads to that kind

Â of thing. and the order in the tree doesn't matter.

Â But the way in which things are grouped matters so I won't go through the

Â details, but that's the anyway the number of label hierarchies.

Â and again, the the spec is the most succinct way to define it.

Â labeled hierarchy is a node in a set of at least two labeled hierarchies, that's

Â all. so the generating function equation,

Â again. it's Z plus, all the labeled hierarchies.

Â It's either the L of Z subtract off the zero, subtract off the one as we've done

Â many times before. But now from the standpoint of this,

Â tree-like schema that's as far as we need to go.

Â It's just a function of Z in itself. so that means we can apply, the theorem

Â for implicit tree-like classes. It's a function of Z and itself.

Â We just have to identify, what the function is, in the spaces Z plus E to

Â the W minus one minus W. We make a system of equations by setting

Â that equal to W and its derivative equal to one.

Â That's the system of equations. The derivative with respect to W.

Â Z to w minus 1 equal 1, e to the w minus 1 equals one means w equals log 2 and

Â then plug w equals log 2 into this one and you get r equals 2 log 2 minus 1.

Â 14:32

so now we compute the other derivative derivative with respect to z of the

Â characteristic equation evaluated r and s.

Â And second derivative with respect to w. So those are the calculations, derivative

Â with respect to z is just 1. First derivative with respect to w is ew

Â minus 1. Second derivative is z to the w.

Â Plug in those values of R and S. and actually, well it's 1, the derivative

Â of C. Second with respect to W, it R and S and

Â S is log 2, it's just 2. so that means alpha equals, just square

Â root of R, which is 2 log 2, square root of 2 log 2 minus one.

Â So those simple calculations, boom, give us the complete, a, coefficient

Â asymptotics for this class of labelled hierarchies.

Â It's a implicit tree like class, a, in, have top level analytic common in tours.

Â Getting us right to the coefficient asymptotics.

Â Again, all of these methods are various ways to find it will specific techniques

Â or even towards each problem. the beauty of singularity analysis is

Â that all that calculation is hidden under the cover and done once for us.

Â And it's organized, then, in terms of a few broadly applicable schemers.

Â And if you heard of hierarchies, if your scientific problem you observe in the

Â field that, that's really better modeled by a set of more than four things, or,

Â sets of three and nine things, or whatever it happens to be, you can write

Â down a construction and you can test that construction against what you're

Â observing, in nature. and then you can get the coefficient

Â asymptotics immediately via applying schema of this type.

Â It's a very broad and general way to get to the, useful, information, that's

Â needed for, whatever scientific endeavour is involved.

Â That's a third, fourth example of a schema based on singularity analysis,

Â tree-like classes.

Â