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.