Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.
Analytic Functions and Complex Integration
Loading...
来自 Princeton University 的课程
Analytic Combinatorics
19 个评分
从本节课中
Complex Analysis, Rational and Meromorphic Asymptotics
This week we introduce the idea of viewing generating functions as analytic objects, which leads us to asymptotic estimates of coefficients. The approach is most fruitful when we consider GFs as complex functions, so we introduce and apply basic concepts in complex analysis. We start from basic principles, so prior knowledge of complex analysis is not required.
与讲师见面
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Before we go on to the next kind of function that we'll be able to treat, we
need some more fundamental ideas from complex analysis.
it doesn't seem like it should be related at all, but we're going to talk about
complex integration. and to do that, we're going to go back to
the idea of an analytic function. remember, an analytic function is one
that we can represent as a power series and a singularity is a point where a
function is not analytic any more. So, for example, 1 over 1 minus z.
in a small neighborhood of 0, we can write that as some N greater than 0, z to
the n. So, 1 over 1 minus z is analytic at 0.
Actually, with a little algebra, you can show that 1 over 1 minus z is analytic
everywhere but at z equals 1. so, but the idea is representable by a
power series expansion. and if we look at all the generating
functions that we talked about they're analytic almost everywhere.
There's just a few points where they're not analytic.
and so and those are the points where the denominator blows up when it's a ratio
where [COUGH] the square root is a special case that we'll talk about later
on. but generally there analytic lots of
places. So, that the it's that's why it's
important to us. now as an aside I want to start talking
about computing with complex functions. because we can do plots that actually are
quite illuminating and we're going to start with that.
it's not really an aside. It really is the way we're going to talk
about the functions. and for computer scientists if we
reinforces the idea of abstraction that we can write programs that manipulate
complex numbers. Some programming languages have, have it
built in. but even if it's not it's very easy to
do. if you're not familiar with object
oriented programming you can look at one of our introductory textbooks.
in this example, we talked about this example in detail exactly this example
because it's such a good example of object-oriented programming.
So, we can define with code like this what a complex number is.
The first two lines say that a complex number is a real part and an imaginary
part. And the next line define how you create a
complex number. If you take a real part and an imaginary
part and you set those values. And if you have those values, you can
define the functions to compute with complex numbers just according to the
basic definitions that I gave. so, if I'm a complex and I want to add a
complex number another complex number b to my value, then I think I could take my
value as a. That's what that complex a of this means.
and I can compute the real part by adding a's real part and b's real part and the
imaginary part by adding a's imaginary part and b's imaginary part.
and then, make a new complex number, with that real imaginary part, that's the
result of the plus operation. and times has to cross multiply exactly
as defined, and we can go ahead and write code for other the other operations.
and that code will be posted with the website.
If you don't do programming fine, but it's maybe just as easy for you to learn
the programming as it is for the programmers to learn the complex.
So I hope everybody works with the code as well as with the mathematical
abstraction. and so we can talk about the idea of what
is a complex function. it's just something that given a complex
number evaluates and returns a complex number.
And so, this is an example of code that implements the complex function, 1 over 1
plus z cubed. 1 is a new complex number that's got a
real part of 1, imaginary part of 0. and then the denominator is going to be
we're going to take that number 1 and add a number to it.
That's what the dot plus means. What I'm going to add to it, we're
going to add z times z times z. So, that's 1 plus z cubed.
and then, we're going to take the reciprocal of that, that's the complex
number that we're going to return, 1 over 1 plus z cubed.
now it takes a little while to get used to this kind, kind of syntax, but not
that much. and I think again most people will find
it easy to look at the code and do simple things with it.
and so that's fine, so we can write programs that compute with complex
numbers. I just want to mention there's a design
choice here, and that is that we treat complex numbers as mutable.
that is, every complex number that we wind up computing with is different.
in computers nowadays that just seems to be a reasonable the way to go.
It's the same approach that with programming languages like Java use for
strings. and what's the point of all this is not
just to write code. what's the interesting and why, and why I
want to do it is that it's also pretty easy to plot complex functions.
Then, we're going to do a particular kind of plot where we do an image.
And all an image is, is a square array of pixels like everything you see on the
screen is an image. And we're just going to take a 512x512
square of pixels. Now, we're going to give, that's points
in the plane. Then, we're going to give, for a quart,
for a particular complex function, we're going to give every pixel a grayscale
value according to the magnitude of the value of the function.
If the function has got a high value, it's going to be black.
If it's got a low value, it's going to be white.
And the gray says how big it is. So that's what this [COUGH] code in here
is doing. so it's going to give an x and y which
are scaled the x-y coordinates in the image.
It's going to create a new complex number.
And then it's going to evaluate a function, a given function at that
complex number, compute the absolute value, and actually, we multiply by ten
to really emphasize the growth. That's an arbitrary factor.
and then we're going to convert that to a number between 0 and 255 to get the
grayscale, and then we'll set the color of the pixel.
And we'll do that for every one of the 200 and 512x512 pixels or whatever size
that we set it to. but that's the key, every point has a
color, which is black if the function is high and white, if it's low.
And this is it's a really simple code any program would have no trouble trouble
with this. and if you're not a programmer go to our
book sites for introductory courses and you can work with this code and it's,
it's not difficult. so, then what we can do is so this an
example where we implement 1 over 1 plus z cubed.
and all we have to do is call this function.
a new version of that function 1 over 1 plus z cubed and we get a plot like this.
this is for 1 over 1 plus z cubed. now our convention is we'll always draw a
2.5x2.5 square. so that's minus 1 over there.
and this is square over 3 over 2 and so forth.
So, the darkness of the pixel is proportional to absolute value of 1 over
1 minus 1 plus z cubed. So, most of the time it's pretty small.
It, unless you get close to a [COUGH] something who's cube is minus 1 like
minus 1 or these are whats called the roots of unity.
and that's a wonderful part of the lore of complex numbers that I haven't talked
about much, you know, just for the purpose of
[UNKNOWN].
But those are the numbers that if you cube them, you get a minus 1.
So that's what that plot looks like anyway.
so very easy to get a visual representation of a complex function.
And what we're really interested in is that this visual representation shows us
the singularities that is the points where it blows up and you can't represent
it with the power series. The points where it's not analytical the,
where the function goes to infinity. so there's all kinds of functions these
are just some examples. So, this is what 1 plus z plus z to the
5th looks like. and this is a little bit bigger square.
If we're not going to be showing the 2.5x2.5 square we'll show that one in the
white, because sometimes interesting things happen outside of that square.
Now, in a surprising amount of time, interesting stuff happens right within
that square. this is what e to the z plus z squared
over 2 looks like. So when z gets positive it starts to get
big. When z gets negative at a certain point,
it starts to get big, otherwise, it's small, that's kind of what these things
are saying. but those values are those functions are
analytic everywhere that they're going to infinity, but at a reasonable rate.
so, let's look at the rational functions we've looked at.
So, 1 over 1 minus z has a pole at 1. 1 over 1 plus z squared has poles at plus
and minus i. 1 over 1 minus z to the 5th, those are
the 5th roots of unity. this is what the generating function for
the number of binary strings with no occurrences of four zeros in a row, looks
like. it's got four poles, they're kind of
spread out like that. and so, we, we get a feeling for, at
least, how big the function is from these kinds of plots.
and then, this is that, that other one for set partitions.
And we'll, we'll look at the properties of these later on.
So, the ideas that we can with these plots, we can characterize the functions.
And we'll, we'll be doing that for a purpose later on.
but now, let's talk about complex integration.
and this is another very fascinating part of complex analysis.
and it's a simple idea. You just want to define a line in the
plane and you want to integrate along that line.
and so like a straight line it's pretty easy.
You just change variables to convert to real integrals, like if you're, integrate
along that line at x equals 2 and then you can pull the 2 out and just do y as
it changes, change to x plus iy. And another i comes out.
so the 2 comes out with, with an i because of, we're changing along the
y-axis. and then y squared over 2 from 3 to minus
the 1, because we're going down. so that's a complex number that's the
value of that integral. so that's a, a natural starting point.
now there's, but we can add to that an integral that goes in a different
direction and make a close contour. we can do around a circle.
we have a lot of variability in terms of trying to define an integral.
and some amazing facts is that if you have an analytic function in a region and
you have any path of integration that's a loop the integral is going to be 0.
and not only that relevant for analytic combinatorics, you can get the
coefficients of a complex function by complex integration.
So, that's what we're going to look at next.
this is due to Cauchy. and it, you know, these facts are, are
again, part of the foundation of a deep and beautiful theory that we're going to
take advantage of. so for analytic combinatorics what we're
going to use this for is to get exponential growth for this bigger set of
generating functions then, then a rational called meromorphic.
but let's look in more detail at some examples of integration.
So, let's say, we want to integrate f of z equals z on a rectangle.
So, we'll just integrate along the four lines just as I did before.
so if you're inte, integrating on x then you can just leave the y part alone and
just integrate. In this case, it's minus 6 plus 3i.
this next one is the one I did before, which is 2i plus 4.
this next one goes the other way. it it happens to be at i, so it's 6 minus
i. and this, this other one goes up the
other way. It turns out to be 4i minus 4.
So, if we want the integral all the way around that rectangle, we just to add
those four things up together. and so just add those, these four.
And what's amazing is that we get 0. we had lots of different values, they
just you can check my arithmetic, they all add up to 0.
here's another example. we're going to integrate f of z equals z
on a circle centered at 0. So now, we're going to hold the radius
fixed, and we're going to change theta. So, we write our complex numbers in a
polar coordinate, z equals re to the i theta, so then dz equals ir e to i theta
d theta. we plug that in, then we have zdz so we
have ir squared. We get e to the 2i theta e theta.
so the integral of that is either the 2i theta over 2i, same sorts of rules as
with the real, reals. evaluated from 0 to 2 pi, but 2 e to the
2 pi i equals 1. e to the 0 equals 1.
and that, that's from Euler's formula. e to the 0 equals 1, so it's 0.
the integral of f of z equals z on a circle centered at the origin is 0.
it doesn't matter what the radius of the circle is.
so that's interesting. let's look at another one.
What about 1 over z on a circle centered at 0?
So, integral of 1 over z, again applying so, you know, substituting re to the i
theta, z over dz is just d theta. and then i comes out, so it's just now,
dz over z here, all that's left is id theta.
And so, that integral is just going to be 2 pi i.
Integral of 1 over z in circle centered at 0 is 2 pi i.
So, that's the examples of integration. so here's another one.
let's say, it's z to a power not a circle centered at 0.
so again, same substitutions z equal to re to the i theta, dz equals i re to the
i theta. so z to the m is r to the me to the m
theta. multiply it out, now we have e to the i m
plus 1 theta would be theta. and now, there is two cases if M equals
minus 1 then we get 0, I'm sorry, if M equals minus 1, we get 2 pi i the same as
before because all that's left is 0, 0 2 pi b theta.
If M is not equal to minus 1 and [COUGH] we're going to have the same 1 minus 1
situation that we had before and we're going to get 0.
and, you know, even if it's a circle centered somewhere else, say, integral of
f is equal to z minus s to the M at a circle centered at s it's going to be and
I'm not going to go through all the steps.
It's almost the same as before. it's going to depend only on whether M
equals minus 1 or not. so z minus s to the 10th is always
going to be 0. but 1 over z minus s is always going to
be 2 pi i. these two are going to turn out to be
important for integrating analytic function.
so that's a couple of more examples of integration.
so now the null integral property. so, what that says is if you have an
analytic function in a region omega in the plane and you integrate that around
any closed loop in that region then you're going to get 0.
and again for the purposes this lecture, we're not going to prove this where this
is, this is going to be an axiom. And, and I'll talk about then why we say
it that way in just a minute. so this is what we saw.
if we had f of z equals z, which is analytic we integrate around a rectangle,
we get 0. Integrate around a circle, we get a 0.
whatever shape you want to make, go ahead and calculate the the in integrals, which
you can do you're always going to get 0 . another equivalent way to look at this is
if you have one path alpha and another path beta and they're homotopic.
That just means you can deform one to the other.
then the integrals are going to be equal. so that is, there's alpha and there's
beta. So, they start at the same point in, same
starting and ending point, but you can deform one into the other.
and the, the integral around is going to be 0, but if you switch the direction on
beta, it's a proof that the integral on alpha is equal to integral on beta.
So from the null integral property complex integration is quite a different
thing than in for real functions. because you have this property that in a
lot of cases, it doesn't matter what the path is you're still going to get the
same value. and that's is certainly fascinating and,
and key property. in fact I've mentioned the, really, the
basis of complex analysis that I just glossed over by stating these things as
axioms. If you want to see a proof that these
things are all equivalent that's in appendix of the blue book or a a course
in complex analysis really is, is about this.
The, the idea that a function can be expanded in a power series, the idea that
it's differentiable because the limit that defines differentiation exists no
matter what the direction you go. And, and the idea that the integral
around a closed loop should be 0 those are equivalent ideas and we actually, in
the the book actually proves that with the, with the circle of implication.
but now, what we're going to do is we're going to take that null integral property
and we're going to use that to help us extract coefficients from an important
class of generating functions. and that'll be our next topic.
but to do, before we do that, we're going to talk about Cauchy's coefficient
formula, which is an application of a null integral theorem.
It does exactly what we want. if we have an analytic function we want
to extract the coefficient of z to the n in that function.
and the formula says, that what you do is you take the function, divide by z to the
n plus 1, and integrate over any closed loop that now contains the origin.
and it's, it's not difficult to prove. so our condition is that the function has
to be analytic in in this region omega that contains the origin.
So, therefore, the function is analytic at the origin.
So therefore, we can express it as a power series at the origin or just f0
plus f1z plus f2z squared, and so forth. So, that's the first thing.
Now what were going to do is take the loop and deform it to a small circle
centered at zero or circle. And as long as the circle is within
omega, were fine. and then, just integrate.
and then, the integral is we can integrate term by term.
so we're dividing by z to the n plus 1. So, it's f0z to the n plus 1 and so
forth. Then fn over z, fn plus 1 times z to the
n plus 1, and z to the n plus 1 cancels out fn plus 2z and so forth, like that.
so that's the integral. now if we look at integration example 4,
those things are going to be all 0 because we did an integral set.
If you integrate z to the n around a circle containing the origin, it's
going to be 0 unless the exponent is minus 1.
So, the only thing that's left in the, and if exponent is minus 1, the value of
the integral is going to be 2pi i. So, the only thing that's left is f sub n
times 2pi i, that proves Cauchy, Cauchy's coefficient formula.
just a consequence of the low integral of, of, you know, complex integration.
So, in the context of analytic combinatorics this is going to lead to
the transfer theorems for a much broader class of functions called the meromorphic
functions. and that's what we're going to look at
next. the idea of complex integration is a deep
and powerful idea that's going to be very helpful to us in the analytic
combinatorics.
