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.
