0:04

by now I think most of you are convinced that the, meromorophic transfer theorem

provides a really, pretty simple, turn-the-crank method, for doing the last

part of analytic combinatorics. Giving us analytic transfer.

Right to asymptotic estimate of coefficients.

For a big variety of combinatorial classes.

next I want to introduce an even more important concept.

The idea of a schema where we can have a general theorem that directly gives us

results for a, a whole set of combinatorial classes all at the same

time. as many examples of this in Analytic

Combinatorics, this is the first of many examples that we'll see.

so, the idea is of a schemist, that's a treatment that unifies the analysis of a

whole family of classes. so that would redo the analysis once and

we don't have to do again. you could think of our transfer theorems

as that way, but you, you'll see the distinction.

so for example, what we're going to talk about now is all combinatorial classes

that are built using the sequence construction at the top level.

So if a class has the form, f equals sequence of g, where g is any class at

all labeled or unlabeled, and we're going to say that's a sequence class and

it falls within the sequence schema. And then what we'll see is, a way to get

the coefficient asymptotic for sequence schema.

Just in terms of the generating functions for these top level classes.

So for example, for numeration. we know that if f is a sequence of g,

then the generating functions satisfy the relationship f of z equals 1 over 1 minus

g of z. where these are the coefficients of, this

is for the unlabeled case. the number of structures we're talking

about is f sub n. For the labeled case, it's n vectorial f

sub n. We've seen examples of, of those.

but what's also interesting is that we can use the same approach to analyze

parameters. so like if you want to count the number

of g components in f. So its the sequence of g's and number of

how many different g, how many g's are there in f, and then you could just mark

it with variable you as we saw in lecture three.

and get this relationship that the [UNKNOWN] generating function for f has

to satisfy in terms of the generating function for g.

Or maybe you want to mark the number of components of size k.

so then you take the ones of size k and mark them with u and take them out.

and then you get an, equation like this for the generating function [UNKNOWN]

generating function for number of components of size k and so forth so the

idea that its a sequence class gives us a relationship among the generating

functions. And we can exploit that.

in the analysis. with metamorphic asymptotics.

So now what often happens and this is the first again of many examples is when

we're looking at the generating function as an analytic object, there's some

technical condition that we have to assume about degenerating function in

order to be able to apply the analytic results, and so, maybe there's something

like [UNKNOWN] that gets rid of the technical condition out there, but for a

lot of these, we don't know those. But usually, as you'll see, these

conditions are easy to check and they hold so, for sequence classes, its the

idea of supercriticality. So what we're going to talk about is

supercritical sequence classes, where we mix up the formal and the analytic.

And we're going to say that a sequence class is supercritical if, if you look at

the generating function of the G class, the component class you have it's

generating function G of Z. and it's got a radius of convergence.

and the thing is if you evaluate the function at it's radius convergence and

it's bigger than one, then we're going to say that the sequence class is super

critical. And that's the condition that we need in

order to be able to unify the analyses. so, just as an example, we did the

generating function for integers a while ago Z over 1 minus z.

So the radius of convergence is 1 minus epsilon for any epsilon.

so if we evaluate it at, at row, then we get 1 over epsilon minus 1.

and there's plenty of values of epsilon within the radius of convergence, of

course that's bigger than 1. So, as long as we pick a small enough

epsilon we have the super critical conditions satisfied.

We can do this test enough for on the other coming into our classes that we

looked at. So, anyways, since I of Z has this

property the classic compositions is super critical.

Its the g that we're testing that has to has this property that if you evaluate at

its raise [UNKNOWN] you get bigger than one.

So since intergers has that property, compositions is super critical.

now in the book there's a full treatment of what happens when there's periodicity

in the generating functions. and were going to just for simplicity.

Because I really just want to get across the idea of what a scheme is.

Were going to ignore a periodicity in this lecture.

and so we have another technical definition called strong aperiodicity

that says that there's not going to be aperiodicities in there.

so given those two definitions, now We have a general transfer theorem for the

whole schema. and it gives an even simpler way to

derive the coefficient asymptotics for these types of classes.

so it says that if f is strongly a periodical supercritical sequence, then

it's coefficient asymptotics is just 1 over g prime of lambda.

and the growth is one over lambda at the end plus one, where lambda's the root of

g of lambda equals one, in its radius of convergence.

So we've find a root, but it's a simpler root and boom, we have the coefficient

asymptotic. so you need to, this is just a quick

sketch of the proof and it's technically not so difficult.

first of all, the function increases from zero to it's radius convergence of

positive coefficients and the value at row is bigger than 1.

So there is a root in there. there is a value where G of lambda equals

one and that's, that's the one that we're going to for.

and then at that point you can write out the series expansion of what G would be.

and then if you take 1 over 1 minus G, then that's gives you the leading term in

that. essentially gives you the coefficient

asymptotics. that's the just a quick outline of the

proof. but really all most people are going to

remember from this slide is this idea. That all I have to do is find lambda and

evaluate g prime at lambda and I've got the coefficient asymptotics.

so, just to look at the examples that we already looked at.

For example, for surgections that's a sequence of non-empty sets.

So, it's 1 minus e to z minus 1, so that's where e of g is.

And so , the lanbda is where g of z equals 1.

So, it's ez equals 2 lambda equals log 2. So, boom, log 2 dm plus 1, and then g

prime, And of that, it's just e of z, evaluate lambda's 2 and that's it.

so such an easy way to get from the construction right out to the coefficient

asymptotics. Find the root that's the exponential

growth. and again this is just another example of

our basic [UNKNOWN], so we're going from the spec to the generating function

equation immediately to the acetonics. and here's another one that we did was

alignments. so now g of z is log of 1 over 1 minus z.

where is log of one minus e equals 1, we already did that calculation.

It's 1 over e, boom, 1 over e to the n plus 1 derivative is 1 over 1 minus e,

evaluate over 1 minus e is e, boom, that's it.

compositions, that's, that's the one we've done.

G of z is z over 1 minus e, where is that equal to one?

At one half over to to the n minus 1. so an even easier way to do coefficient

asymptotics for a whole class of combinatorial classes.

A whole family of combinatorial classes, the ones that are built with a sequence

construction. That's an example of a schema, and we're

going to see other examples later on. Now, you might argue, that's not really

that much of an improvement. the, the other method was pretty simple

as well and there's some truth to that kind of argument.

but what I'll show you next really maybe gives a feeling for why schema are so

powerful. say you want to study parameters.

Like, how many parts are there in a random composition.

so, so it's like for two, it's then one of them's got three, two of them have

two, and one of them have one. The average is two and actually well you

can probably figure out what you think the number of parts is you know in a, in

a composition. but of course the same method's going to

work if we restrict to ones and twos or primes or whatever else.

or let's look at surjections. what's the, if you have a random

surjection, what's the expected value of M?

that's a much more complicated calculation.

Here there's one of them where the value of M is one, there's six of them where

it's two, six of them were it's three so that's the expected value.

And for 4, there's 1 where it's 1, there's 14 where it's 2, there's 36 where

it's 3 and there's 24 where it's 4, and again you get the average.

So, average expected values of parameters or here's for alignments, how many cycles

are there in an alignment. and again, this seems like a difficult

analytic problem. but a real poster child for analytic

combinatorics and this idea of scheme is that we can get, answer these question

immediately through general transfer theorem based on supercritical sequence

scheming. Let's see how that works, and this really

is just a generalization of the simple proof that we did for enumeration just

with the [UNKNOWN] generating function and I'll I'll skip the details.

but what we get is if we have a strongly [UNKNOWN] sequence class then we get the

expected number of g component in a random f component.

we get the expectation and the standard deviation.

Again, all in terms of this lando which is the route of g equals 1 in it's radius

of convergance. Again, the proof of this is just going

ahead from the definitions that we've done before by verious generating

functions. And the same kind of expansion that we

did for enumeration. And you have a similar theorum for number

components of size k and so for it to get much detail...

But, I, again, most people are just going to look at that one things and say,

actually that first term n over landed g prime of landed, that's my expected

number of components. that's all I have to compute.

and for, for example, for composition So my G of z is z over 1 minus z.

My lambda is one half as before. so lambda G prime of lambda, that's one

half, boom. I expect the number of components is n

over 2. for surjections Lambda's log two and u,h

so lambda g prime of lambda. G prime is e to the z e to the log two is

two so its n over 2 log 2. Immediately, we get the number of

components and alignments again it seems like really difficult analytic question

but its just all about computing lambda and then multiplying that by the

derivative of t value at that place and in this case it comes out to be e minus

1, immediately we get results like this and we can get other kinds of results

like component sizes and other things. Simply by using this structure of the

combinatorial class and then what we know about analysis in meromorphic

asymptotics. that's one example of the power of the

idea of a schema. and there are several other schemas

discussed in the book.