Today we're going to start on the second part of the course where we talk about complex asymptotics. this is a set of methods that we use to extract information about the coefficients right from the generating functions. Again, as in the first part of the course, we want a high level, automatic methods that get us to the results that we need. And I'll try to introduce that in today's lecture. So let me just start off with a roadmap of what we are going to talk about before getting into complex analysis. so this is our standard overview. And again, we've finished the first part of the course on the symbolic method. And now we're going to start into complex asymptotics where again we're going to have talk about machinery that we can use. To take a generating function equation. And get out asymptotic estimates of the coefficient automatically. today were going to talk about rational and metamorphic functions. We'll talk about what those are in just a minute. So our starting point is that with the symbolic method. We saw that we had tools, combinatorial constructions, and transfer theorems They give us generating functions that vary widely in, in nature. Now, that's the generating function for derangements, that's for involutions, that's for surjections and so forth. and these functions are all quite different in character. but still, what we want to do is eventually our goal is to get asymptotic estimates of the coefficients out. so we want to know that the probability that a permutation is a derangement is about 1 over e, and so forth. and we'll see during the second part of the course for all of these functions we are able to automatically extract these kinds of asymptotic estimates. Now, the classical approach is to take the generating functions and derive an explicit expression. And then use acetonic techniques to develop an approximation. But with analysis of combinatorics, what were going to do is directly derive the approximations. So just and this is an example. That I've used. in the very first lecture. But eh, it's worth, eh, pointing out again. When we're counting say Catalan trees. We have a construction that gives us a generating function equation, we get an explicit form for the ordinary generating function. we can use Newton's binomial theorem to expand it. and then extract coefficient and then we can use Stirling's formula to get an approximation. And I've left out a lot of calculations in this this derivations and you saw them in earlier lectures or in Part 1. or for derangements similarly, we have a construction that gives us an EGF equation. Its relatively simple, explicit form will be exponential generating function. and that on we can also expand but now that's a convolution, a double sum, but we can manage it, get an explicit form of the coefficients. And then eventually see that that aproximates to about 1 over e. We've got mathematical arguements in each one of these steps to make that we don't want to repeat these arguements for every problem that we encounter. So, not only that the combinatorial constructions that we use in this symbolic method, both through labeled and unlabeled objects. the whole idea is that we can use those same constructions to make variance of the objects that are much more complicated. And get quite complicated forms for generating functions. And then we get, actually fairly complicated functions that, might lead to, difficult problem extracting coefficients. And, and certainly in classical analysis these kinds of problems face mathematicians all the time. But as we'll see, starting in today's lecture and in the next couple of lectures, there's an opportunity, because in the end, it turns out, there's a relationship between the generating function. The explicit form of the generating function and the asymptotic result and even in these two examples you can kind of see it. There's a square root in the explicit form for Catalan trees and there's a square root of n cubed in the denominator in the asymptotic approximation. Is it e to the minus n for derangements in the generating function. There's an e to the minus in the asymptotic result. And as we'll see, that's no coincidence. So here's the overview of really what we are going to be doing for the next several lectures. In the first part of the course, we talked about the idea of taking a specification- And using a symbolic transfer theorem to give us a generating function equation directly from the specification. In this part of the course now what we're going to do is take the generating function equation and develop analytic transfer theorems that immediately give us the asymptotic result. And we'll see many, many examples like this character where the derivation of the asymptotic result is as simple as that. specify, transfer, transfer, asymptotic result. We'll see many examples of that. So that's our our overview. This really represents a profound shift in the point of view. in the first part of the course, we were treating generating functions as formal objects. It was all about symbolic manipulations. To have some kind of formal relationship between the specification and and the generating function that lead us to the generating function equation. starting with George Polya many decades ago, some mathematicians started to realize that we could also treat generating functions as analytic objects, a completely different point of view. they're the same function and we need some rigorous justification of it. but in the end that's how we get our asymptotic results. And the other thing that is going to come up starting in today's lecture is that we're not going to stick to the real to real value generating functions. We're going to move to the complex plane, but in the analog career value functions is worth considering. So what happens. Lets say we have this generating function. 1 over 1 minus 2x. That's the generating function that counts the bit strings. What happens if we treat that as a function? Well the coefficients are positive. So we only have to worry about the positive part of it. in we have this idea that we can use as series, that's valid in a certain interval. That allows us to abstract the coefficients and get the answer that we want. In the case of this one. The tail or series of, of that function analytically. is the series 1 plus 2x, and so forth. That's only valid for x less then 1 half. In this little interval here. but that validity is enough to give us what we need when we take the coefficient of z to the n, and that, we get our result, z to the n. Now, but there's other things that we can do, analytically, with these types of series. so, for example, we can differentiate term by term where the series is valid. And that's a analytic manipulation that also corresponds to formal manipulations on a generating function. Then, we have the idea of a singularity. There's a point where that series is no longer valid. In this case, when x equals 1 half. So we have to recognize these points and not try to do analysis of points, on the series of points where the series is not valid. But we have the idea of continuation. We can take that function and we can use that function even in places where the series is not valid. So in this case, like we could say, f of 1 equals minus 1 just by plugging in x equals 1. And the whole positive plane, actually everywhere but at the singularity we can compute a value of the function. and through continuation then we're opening up more analytic manipulations that we can do to get the results that we want. and the same thing happens in the complex plane. When we assign complex values to a generating function, we have a more complicated kind of plot. It's a two-dimensional thing that I'll talk about soon. We've still have the idea of a singularity. We still have the idea of a series representation that holds in a certain domain and allows us to extract coefficients. We still have the same useful context and concepts, we can differenciate and identify singularities and we can continue to place as even where the series might diverge. So, all of those same basic concepts are useful even in the complex plane. And if you're not familiar with complex numbers, don't worry. I'm going to try to give you the concepts that we need in this lecture from first principals. But, really, I want to talk about complex values in this opening segment. because there's really a surprise that happens when we look at generating functions as complex functions. and in fact, the surprise is that all we need to look at is the singularities. And actually usually just one. To get full information on the growth, growth of the coefficient. As Philippe says of, singularities provide a royal road to coefficient asymptotics. There's no real reason why this should be the case it's serendipitous. we have this thing that looks like a function, let's treat it like a function on the complex plane. Our coefficients were supposed to be counting things Why should a complex variable have anything to do with it? well a complex variable has really a lot to do with it as we see. And it provides that analytic point of view provides a mechanism where, really, we can gain full understanding. Of the counting problems that we started with even though at the, at the start, we were working with generating functions just as formal objects. And at the end we're going to work with them as complicated functions in the complex plane. so, in general as we'll see what's going to happen is that the combinatorial generating functions that we're examining. they're functions in the complex plane with positive coefficients, since we're counting things. they have an exponential growth factor and a sub-exponential factor. and the first principal is that it's where the singularities are that dictates the exponential growth. and that's not, not too difficult to see and we'll, we'll see it specifically in many, many examples even today. in the subex, subexponential factor, that's our second principle, is the nature of singularities dictates what the subexponential factor looks like. depending on how the, what those singularities are. There's different kinds of singularities in the complex plane. and we'll talk about that in in some detail. Uh,[COUGH] not too many different kinds but a few different kinds, whichever one it is that's what dictates what the sub and ex-, exponential factor looks like. so just as a preview and again, I haven't defined re-, what the singularities are, the types of generating functions but, but anyway, it's it's worth showing how things distinguish themselves so for example, the generating function that counts all the strings with no 00 is, is that function there, we saw that in, in the first lecture. That's called a rational function. And first thing we're going to look at is rational functions. Its singularities are called poles. so, poles the location of the singularity gives the exponential growth And because it's a pole, it's got a particular, it's got a constant sub exponential factor in this case. for derangements. it's also a pole. it's location's at 1, so its exponential growth is 1 to the n, which goes away. And that's the subexponential factor again, is a constant. But for Catalan trees it's got a different kind of singularity. and so, it's got a different nature of its subexponential factor. Now that you, we won't see those for a couple of lectures. I forgot to mention that the arrangements, the kind of generating function that is, is called meromorphic, and that's the second kind of generating function that we're going to look at today. so that's a quick overview of how we're going to approach the idea of automatically extracting coefficients from generating functions. Next, we'll drive in, dive into first principals of complex analysis.
