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.