0:04

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.

Â 8:01

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.

Â 10:21

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.

Â 13:53

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.

Â 19:54

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.

Â 21:21

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.

Â 23:37

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.

Â