So fully understanding the proof of singularity analysis is certainly a deep order in complex analysis. but as promised, now what we're going to do is look at some general schemas that in applications will free us from a lot of that difficulty. So, it seems like a lot of work approximating function checking delta [INAUDIBLE] and other things. The question is are there any short cuts? and the answer is, yes, that the process is is really automatic for a, for a broad variety of classes. and we'll look at some, some, examples. we saw one of these in a previous lecture. where we referred to a treatment that unifies the analysis. Of a family of classes as a schema. and now we're going to look at examples of schemas that are amenable to singularity analysis. they get us into the top level of analytic combinatorics where we can go from the spec, to the equation via the schema right to the coefficient asymptotic. so last lecture we looked at the super-critical sequence schema that handled the amorphicity all constructions of the form f equals sequence of g. Now we're going to look at the, for singularity analysis, we're going to look at analogue for label classes, called the exp-logs scan. it handles f equals set of g. we'll look at what's called simple variety of trees. And again, there's a technical condition called invertible. and that will handle things like unary binary trees and many other things and we'll look at so-called context-free schema which handle families of constructions that are quite common for common, unlabeled commonotorial classes, and they're the technical conditions called irreducible. so if we have a problem that falls within to one of these schema, then we have an easy way to solve it. so let's look at label sets. so again, this is similar to supercritical sequence, except it's for sets. If we have a labelled class that has a construction of the form F=SET(G), where G is another labelled class, that's a labelled set class which falls within the labelled set schema. So the generating function just like symbolic transfer theorem. we get F of Z equals E to the G of Z. and so, if F of N is the coefficient of the to the F of Z, it's labeled so the number of structures is n factorial F of N. we can also work with parameters by marking things with another variable, U making it bivariant. So if you want to mark the number of g components with u, then you can do either the ug of z or the number of g, g components of size k. and there's lots of things that we can do with parameters as well. But just focusing on enumeration, if z equals e to the g of z. And so now there's some technical conditions that we can check that the construction or the generating function coming from the construction satisfies and if it satisfies these technical conditions. then we can get a quick analysis. So we say that it's exp-log with parameters alpha, beta in a row. if the generating function for g, for the ones that we're taking sets of satisfies these conditions. so it's going to be analytic at zero and nonnegative coefficients. So that's pretty much automatically satisfied for combinatorial generating functions, 'cuz we're counting things that coefficients are nonnegative. finite radius of convergence row so that has to do with whether it has a singularity or not. and then if there's similar with what we saw for meromorphic and other applications. If there's a lot of singularities the same distance from the origin and you have complicated period decipes but in a great many applications It's got a unique singularity on its radius of convergence, and and it has to be, it has to be a delta domain for the G function at row. That has to be checked. So these are all technical conditions that are required in order for the singularity analysis proof to go through. for many applications these are not very easy to establish. And then the other condition which is not a general condition but it's the one that holds lots of applications, and that's what X blog, this is the log part of X blog. Basically it says, that you can approximate G. with an a log with various parameters. so alpha times log, or 1 over 1 minus z over row, plus beta. Those are the parameters. So, and sometimes it's actually equal to a log function, in which case I can plug in and actually many of the applications will do, it's equal In which case, you can pull the parameters right out. So, that's the log part The exp part comes from it being a labeled set. So, those are the conditions the, the technical conditions at that, if it's satisfied, then we say that. The thing is X blog. So, for example, the generating function for cycles is log of one over one minus b so that's analytic and that's the domain see the first few conditions work. but and it's equal to log 1 over the z, so that means alpha equals 1, and rho equals 1 and beta equals 0. So, set of permutations, which is sets of cycles, is exp log of 101. And wait, that's an easy one, and we have more complicated ones, But still, plenty of classes where if you can have a set of things that you can approximate with log. then we have a transfer theorem. And here's the transfer theorem for exp-log labelled sets. So, it's some kind of set it's a exp-log with parameters alpha beta and row. that means that g is approximated with alpha log 1 over z over row plus beta that's true. Then just doing the transfer through the exponential f of z is, is approximated by e to the beta 1 over 1 minus z over row to the alpha. which again applying asymtotics function skill transfer gives the coefficient of Z to the N and F of Z. We just have to figure out those parameters, alpha, beta and rho so that the generating function for G is approximated for and you have the coefficient asymtotics. not only that the for such classes the the proof shows that the number of G-components is going to be alpha log N. That's true for any exp-log class. an extremely brief proof sketch really not at all it's really those conditions match up with the basic singularity analysis process. and it's just applying the singularity analysis in this general setting. and you can see that the conditions of delta elusivity and so forth. match up so I'm not going to go through that detail. So most people for applications are just going to remember that one formula. going to need to remember just that one formula for exp-log labelled set classes. so, for example a trivial example but still to check the method. this is using that schema to develop asymptotics for the class of all permutations. So permutations the set of cycles. so that's the exp-log form. Now G of z is log of 1 over 1 minus z. So were going to apply the theorem and find that alpha equals one, beta equals zero and roe equals one, as I said. So we get the asymptotics immediately either the beta is one and the gamma of one is one and one over rho is one all the, all the all that we have left is one. [LAUGH] so that says tinhat the average number of permutations is N factorial. so in, but more important if we apply the corollary then we immediately get that the average number of cycles is approximated by log n. So that's using the schema to find the average number of cycles in a permutation. and that's, again, we have lots of other ways to get that easy answer we'll look at many, many more examples in the in the next lecture of applying the exp log label set schema. Here's another example of a schema, simple varieties of trees. So we say that a combinatorial class, if it's a enumeration-generating function, satisfies f of z equals z times phi f of z. Then it's a simple variety of trees with characteristic function phi. And again we're going to have technical conditions on such functions that'll enable us to get a general theorem to get coefficient asymptotics for such classes. so. And this one works either if they're unlabeled or labeled. so for unlabeled, then it's coefficient of Z, and the n of F is Z is the number of structures. And then we have constructions like Z times the sequence omega, so sequence omega just means that omega is the set and you pick one's outta, outta that set that you want Let's see what's of length K K 1 K 2 are there in that set Omega. and we've seen that in plenty of examples. and labelled case then the, it's interfactorial times coefficient deviant number of structures in acidic cartisan product star product. but all those things lead to a generating functioning equation of this form immediately by symbolic transfer. Or this function feed depends on which integers are, are in the set omega. so and we'll look at examples of that. and we have seen examples of that before. now again we need a technical condition in order to be able to approve a transfer theorem. And for tree classes its called invertible. so there again we have a parameter so we're going to say it's lambda invertible if the characteristic function satisfies these conditions. again, it's gotta have non-negative con-, coefficients, and it's gotta be non-trivial. so phi 0 plus phi 1 u would be trivial. it's gotta be analytic, and it's got a radius convergence, and phi 0 is going to be not 0. Now, those are just removing degeneracies. So here's the key technical condition that have what's called the characteristic equation. Phi of lambda equals lambda phi prime of lambda. so well the characteristic equation is phi of mu equals lambda phi prime of mu and I've got a solution of lambda positive real root less than r. so for example let's look at just for rooted order trees again an elementary construct now that we've seen many times. So that's G equals Z times sequence of G, generating function is Z Over 1 minus G of Z, so phi of U is 1 over 1 minus 1, phi prime of U is 1 over 1 minus u squared. so the characteristic equation is is this equal to the lambda of u times that, so one of the [UNKNOWN] Equals u over 1 minus u squared. and that's true for u equals 1/2. So the root of that equation is lamda equals 1/2. So therefore, rooted ordered trees are 1/2 invertable. so that's a technical condition, that characteristic equation has to have a real root, and, and it has to be non degenerous really is what the other ones are saying. so now we have a transfer appear. If you have a simple variety of trees and it's lambda invertible, then boom we have the coefficient asymptotics as a function of lambda. and a the exponential growth rate is feed point prime of lambda, and the constant is 1 over square root of 2 pi feed alpha prime of lambda or free prime of lambda. and that's all we have to know for simple varieties of trees, and that covers many, many commonotorial classes. now the proof is deep water. It's uses so-called analytic inversion to develop an approximation to the function and then use a singularity analysis, a standard function scale to get the translation done. and it's just important to note that kind of amazing the end of the free hats factor shows up for for all kinds of trees. so for example and actually the gamma function square root of pi shows up 2. one point I haven't been mentioning is that there's a condition of periodicity that's discussed in the text that I'm ignoring here in lecture. okay so let's show analytic combinatorics for trees using the simple variety of tree asymptotics. so that's the construction, that's the generating function. then we just look at the theorem and we figure out what lambda is Lambda's one half, and then we plug into the equations that we developed for phi of u, phi prime, and phi double prime. and so, like lambda prime is 4, so it's going to be 4 to the n. and then the ratio of phi prime, phi double prime over phi prime Is 8, so, I'm sorry, phi double prime over phi is going to be 8, so we have 16, so boom. We can get the coeffcient asymptotics. The n to the minus three-halves, the 4 to the n, and then 1 over 4 squared of pi, comes out immediately. and our running example from before. Unary binary trees. Now we have different things that we allow. And the size of objects in the, in the sequence. so we're going to take either zero one or number of objects in this sequence. We're going to take either zero one over two. so that's our generating function equation. so now we immediately apply the theorem. We don't say have to solve. We just immediately apply the theorem. so our characterstic fucntion is one plus U plus U squared, [UNKNOWN] first derivatives, one plus two U, second derivative is two. The characteric equation is one plus lamda plus lambda squared equals lambda plus two lambda, splve that for lamda and actually, lambda equals one, solves that. so then phi of lambda equals 3, phi prime of lambda equals 3 phi double prime equals 2, the constant 2. So, that means the exponential growth factor is 3 to the n. We have n to the minus 3 half. Ratio of phi double prime to phi. and, 4 3rds and boom, we have the coefficient asymptotics. 3 to the n n to the minus 3 halves, and we have the coefficient. So this theorem can enumerate any, any kind of tree. And that's next lecture we'll look at lots more examples, but it's, it's very significant. When we looked at unary binary trees using singularity analysis, we had a fair amount of work to do. we needed to solve that polynomial equation if it goes out to fourth and fifth degree, it might be hard to solve. we needed to expand the function around the singularity. that might involve some calculation, might need a computer. and we need to check analyticity and so forth. We still kind of have to do that, but many people skip that step, at least the first time through. but when we use the schema and the general theorem it's completely plug and chug. You figure out fee, you figure out it's derivatives, you know, to solve that characteristic plug-in equation. Plug it in and you have the coefficient asymptotics for any of a variety of trees and the schema does it's job. It unifies the analysis for an entire family of classes. And, using this theorem, you don't have to know much about, complex analysis to apply it. You just, use the characteristic function, solve it, gives you the exponential growth. And then you compute the constant from derivatives of the characteristic function. and you're done. and again, it's a very surprising fact that you're going to have this N to the minus 3 halves factor and then also the square root of pi factor. which goes all the way back to gamma of one half, for all kinds of trees. and, there's many other schemas have been developed and I'll just talk about one more right now. So-called context-free classes. so if you have a family of constructions where each line involves only cartesian product and plus for unlabeled classes that corresponds to context-free grammar from computer science. And we call it a context Free class, and we can develop a general transfer theory for context free classes. So for example in computer sciences will be familiar with these kinds of examples as not many of them out there. So we want strings with equal numbers of 0s and 1s. here's a family of constructions for strings with equal number of 0s and 1s. and so to understand this if you want. u is a set of strings where the number of 0s is bigger than the number of 1s of any prefix. And d's a set where the number of 1s is bigger than the number of 0s in any prefix. and then, so you take the u number of 0s is bigger but then it runs out, so you need a one, and then you take a D. And the number of zeroes is bigger, and so you take a zero and so forth, so these constructions kind of illustrate this idea. and anyway, that's about context-free grammars and there's many examples that people have studied. so but in the present context there's the idea that there's a, again, a technical condition that will allow us to unify the analysis of context-free classes. and this one is, is maybe not familiar to people, or maybe not familiar with with computer science or graph theory. All it says is the dependency graph is strongly connected. Well, it's nonlinear. There have to be things multiplied together for this dependency graph is strongly connected. Strongly connected, so that just means, dependency graph is for every production in the grammar, we draw an arrow to anything that's used on the right-hand side. So S uses S and D and U U just uses U and D just uses D Strongly connected means you can there's a directed path from any node to any other node. in this case there's no directed path from E or D back to S. So that's not strongly connected, not irreducible, that example. here's another example of so called non-crossing forests, and that one is strongly connected. And so that's the condition. And that's a a natural condition it turns out. And then given that condition, if we have an irreducible context-free class then first part of the theorem is that the generating function has a square root of singularity. and then there's another a, aperiodic condition, but then we have a unique dominant singularity, and again we get square root of pi one over rho to the n, n to the minus 3 halves asymptotics, where you alpha is the computable real. It's an amazingly general transfer theorem. Any context-free class is going to have the same asymptotics as as trees did. And at a very high level, it's maybe understandable that it would be that way because a derivation in a context-free grammar is kind of tree-like. but still, this is a very deep theorem. And the basis for it is something called the [UNKNOWN] -Woods Theorem, and that's very, very deep water. that I'm not even going to try to characterize in this introductory treatment of analytic combinatorics. and computing the constant even for such classes can be complicated and maybe is best left for a computer. so I'm not even going to give applications of of this in this introductory treatment. because there's a lot, because there's a lot of things that have to be checked for this. that's not introductory analytic [UNKNOWN]. but still it's important to know that the existence of such a theorem is this square root of pi N to the minus 3 halves asymptotics is, is really universal in a very broad sense. And it's proven for many, many examples of combinatorial classes. so in summary, singularity analysis is a fine example of if you can specify it you can analyze it. It's a very effective approach for developing transfer from GF equations to coefficient at the asymptotics. Now the analysis can be detailed and burdensome, but we have schema that can unify the analysis for entire families of classes. and we saw three examples. the label set schema the simple variety of trees schema and the context-free schema. They all have technical conditions involved, but they cover a very broad family of constructions. Uh,and they all wind up with the same sort of coefficient acetonics and in the first two cases the confrontation of the constants are easy. In the second one it can be in particular examples. If you can specify it you can analyze it and singularity anaylsis is a with a very deep and important method that supports this statement of Philippe's. Uh,there are plenty of other schemas, and we don't have time to talk about them all in this introductory treatment, but we'll talk about another one in the next lecture. so that's introduction to schemas and transfer theorems based on singularity analysis.
