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. 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. 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. of a, one over one to the N minus three S times a constant. For any construction, any kind of recursive construction, we've got a class defined in terms of, itself and, and atoms. so like for example, binary trees. If we use the other construction of binary trees where it's a node or a root and a sequence of 0 or 2 binary trees. the other way to define binary trees. Now our equation is z plus zB z squared. 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. [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. 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.
