0:05

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.

Â