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.