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.
Complex Functions
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
Next, we'll look at Complex Analysis. Now not everybody has had a full course
on complex analyses, but most people have some familiarity.
And the things that I'm going to talk about today are beautiful mathematics.
really everybody should understand that does mathematics should understand
complex analysis at this level. so I'm not going to go slowly, I'm not
going to go quickly. I'm just going to try to cover the
concepts that are really important for analytic combinatorial complex analysis
is really for, for people with interest in computer science.
it's the quintessential example of the power of abstraction.
it's just an idea that we build on. Really all of mathematics is like that,
but, but complex analysis is really a perfect example.
And the whole idea is that we've got minus one.
What happens if we want to take the square root of minus one.
No real number who's square is minus one. So what we'll do is we'll define a number
that's going to be the square root of minus 1 and we'll call that i squared is
minus 1. does i occur in the real world?
Well, no, it's an abstraction. but it's an abstraction that helps us
understand really a lot about the real world.
so then what we're going to do and all of these things are pretty simple.
they get more complicated as we go on. But, just starting with that idea then
we're going to want to do things with these numbers that involve this imaginary
number i, like we're going to want to add a multiple end of item.
We're going to want to do exponentiation, we're going to want to define functions.
We're going to want to be able to differentiate them and integrate them.
this leads to a whole theory that not only is beautiful in it's own right, but
also turns out to have many, many applications in science and mathematics.
And in particular analytic combinatorics. so there's many standard conventions and
again I'm going to go quickly through these things and but many of them are
elementary. It's really usually a matter of two
things. One is the representation of complex
numbers. is by correspondence with points in the
plane. So we're going to the point x y is
going to represent the complex number z equals x plus i y.
we refer to the real part of the complex number or of z, and that's the x part.
and we refer to the imaginary part, so that's that's the y part.
Then the distance from the origin so that's squared of x squared plus y
squared that's called the absolute value of the complex number.
so how far it is from the origin its sometimes how big it is?
And then there is a thing called the conjugate, if you have x plus iy then
that z then z bar is x minus iy. and so that's point flipped down on the
plane. and I haven't defined multiplication yet
but when you do you do a quick exercise to show that z time z bar equals absolute
value of z squared. So those are standard conventions of how
we refer to complex numbers. Everyone's got a real part and an
imaginary part. [COUGH] And we represent them by points
on the plain. Now to define the basic operations.
The natural approach. Is to just use algebra.
But, every time you see i squared. You just convert it to minus one.
So if you want to add to complex numbers. Well that's just algebra.
Add the real parts. Add the imagineary parts.
If you want to multiply, multiply em, use the distributed term law.
i squared to minus 1, and then collect term.
So, bdi squared, which is bi times di, becomes minus bd, that goes into the real
part. Uh,[COUGH], and then bci, and adi, those
go to the imaginary part. So that's the definition of
multiplication of two complex numbers. Uh,[COUGH], and this has all the right
properties it turns out that you'd expect.
The vision 1 over a plus bi to to make sense of that multiply top and bottom by
a minus bi. So then you have a minus vi, so then you
have a minus vi over a squared plus b squared.
That's the denominator is the number times its conjugate which is the square
of the absolute value. There's addition, multiplication, and
division, and if you're not comfortable with those you can try some examples with
the points on the plane, and so forth. What about something like, eh,
exponentiation well you can multiply a lot of times but now it gets complicated,
so now, we'll skip right to one of the basic ideas of complex analysis.
And that's the idea of an analytic function.
So and the analytic function is one that we can represent with a power series
expansion and we have the same concept with the reels with the tailored series
and so forth. So So we talk about omega being a region
in the plane. We talk about a function being defined in
a region of the plane, and it's analytic at some point in that region.
If for some little circle around that point you can write a power series
expansion of the function And, sure enough, this familiar power
series from the reals are effective for familiar functions on the complex.
So when z is a complex number, 1 over 1 minus z equals that power series where
the products are defined as products of complex.
and that's a valid series for as long as absolute z is less than 1, or e to the z
actually is valid except at infinity. and [COUGH] now, let's a bit of a jump
from defining multiplication to this. and I don't have the time to do the the
entire story leading up to this but the main point is that our familiar series do
translate through. And it's through the concept of the
analytic function. When I get, in just a few minutes, to
some more concepts I'll try to talk a little bit about Why we know all of this
to be true. It's, it's really part of deep and
beautiful theory that you'd need to take a course in complex analysis.
For the purposes of this course, we're going to be using these kinds of series.
And in this the idea of complex differentiation.
Well, we define that in the same way symbolically that we'd do for real
number. so it's complex differentiable a function
is complex differentiable, or there's a special word called holomorphic.
at a point, if the this limit, where f of z plus delta minus, of z not plus delta
minus of z not divided by delta as delta goes to 0.
If that limit exists for delta, a complex number and, and, and z, not complex, and
that's the complex function. so if that limit exists, it's holomorphic
or complex differentiable. now this is the same notation as for
reals, but it's a much stronger statement because the value is independent of the
way that delta approaches 0. It's a complex, it can come from any
direction. It's a much, much stronger concept,
complex differentiability. Now, there's a basic equivalence theorem,
that says that, a function is, that these concepts are the same, analyticity, and
complex differentiability are the same concept.
A function is analytic if and only if its complex differentiable.
we're not going to do a proof for that theorem and really for this lecture we
consider that to be an axiom. I'll talk about the proof in just a
second. So if its analytic, if you can express it
as a power series, you can differentiate it and of course that's useful from the
point of view of analysis. Because it means that we can
differentiate an analytic function term by term.
if it's complex diferenciatable in it's derivitive of any order because you can
always differenciate turn by turn. That's not really true in the real.
In particular, we can use the tailor series representations that I just talked
about. Of familiar functions e and 1 over 1
minus z and polynomials and so forth. so Taylor's theorem in terms of
derivatives and so forth just immediately applies and gives us the power series
that we're going to want. So that[COUGH] those are the kinds of
power series that we're going to be extracting coefficients from in order to
do our counting. there's a really famous particular
example of this called Euler's formula. so that you take the definition of the
exponential an evaluate at[UNKNOWN] So what's e to the i theta?
Well, it's 1 plus i theta over 1 factorial plus i theta squared over 2
factorial. And so forth.
That's just right from the definition. exponentials, analytic gets defined at
any point, and so it's defined at i theta.
now if you just convert I squared to minus 1, and I to the fourth to 1, then
you can get rid of every other term that has an I in it.
Every other term does not have an I in it, and then the terms alternate in sign.
So, i squared equals minus 1, so it's minus theta squared over two.
i 4th equals i squared squared, equals plus 1, so it's plus theta to the 4th
over 4, and so forth. So that's just getting, that's just
algebra getting rid of the i squared. and then if you just separate the terms
out, from the previous slide the first series is cosin theta, and the second
series is i sin theta. That's called Euler's formula.
E to the i theta, equals cosin theta plus i sin theta.
and this an amazingly useful formula in many forms of mathematics.
this quote from Feynman expresses what people think.
And he calls it our jewel, one of the most remarkable, almost astounding
formulas in all of mathematics. and again, this is just an example of
just starting with that idea, of square root of minus 1 we can get to
amazing constructs like, like this. that's what complex analysis is about.
Now that's a quick introduction. next, we'll start to apply, some of these
things, to the combinatorial problems that we've been working with.
one thing that Euler's formula does is it gives us another way to find a
correspondence between complex numbers and points in the plane.
so e to the i theta equals cosign theta plus i sin theta, so re to the i theta
equals r cosign theta plus ir sin theta. And so we can use polar coordinates to
refer to a point on the plane. If it's at angle theta and distance of r.
then we can write it as r e to the i theta and we can sometimes its more
convienent to use that form of a complex number and if we definitely often do so.
So for any complex number we can use these ways to convert between the polar
coordinates and the Cartesian coordinates, the same we, same way as we
do for points in the plane. That's an introduction to complex
functions. And next we'll take a look at how to use
this information to extract coefficients from combinatorial generating functions.
