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.

Â