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.