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.
Meromorphic Functions
Loading...
Do curso por Princeton University
Analytic Combinatorics
19 classificações
Na lição
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.
Conheça os instrutores
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Well complex integration, and all the properties of complex numbers and
functions, and the complex plane that we've been discussing might seem very
abstract, and quite far removed from the analytic combinatorics that is our goal.
and in this section, we're going to see how to apply those abstractions to get us
down to specific methods of getting accurate estimates, asymptotic estimates
of coefficients. and it's based on a much more general
class of functions than the rational functions, which are ratios of two
polynomials that we al, already considered.
its com, complex functions that are the ratio of two analytic functions.
Well, rational functions which are polynomials, are also meromorphic.
But now we're allowing functions like e to the minus z over 1 minus z, over, 1
over 2 minus e to the z. and so a ratio of, of two analytic
functions of any description, a much broader class of of functions.
Now approach, is, going to be to make use of contour integration, to, expand the
function into terms where we can get the coefficients.
and then focus on the largest term to approximate.
this is the same approach as we used for our rationals, but we're going to have a
much more general, transfer there. so first the, the definition.
so function is, is meromorphic if it can be represented as the ratio of two
analytic functions at, at a point in the neighborhood.
Now there's a lot of useful facts about meromorphic functions.
and again sometimes there the definitions in terms of these facts, and these things
are, are all related in complex analysis. But, let's, lets call them facts, that if
you have a function that's meromorphic, then you can expand it in terms of it's
just like the analytic expansion. except we can expand it in the negative
direction, in terms of negative powers of z minus z0 all the way up to some finite
level. and then the smallest term used in the
expansion or the biggest exponent 1 minus z minus z0 that's said to be the order of
the pole. so the singularities of the places where
the denominator is 0 or the poles, and the, where those where those things
happen allow us to do an expansion of, of this sort.
depending on, the order of the pole, or how big the polynomial is, locally.
and just to show this expansion, if, if you have a 0 of the denominator, then you
can write g of z, as z minus 0 to the n times, some analytic function.
And then just expand the analytic function f of z over that one, fz 0, and
that's how you get that kind of expansion.
not, not difficult, not to see at all. Now it turns out that the coefficient of
z over, 1 over z minus z 0 which is h minus 1.
that one turns out to be particularly important, and we'll see why in just a
minute. That's called the residue of the function
at the point. And, we have a special notation for that,
are the residue is equal z0, is h of, h of z.
so we can expand the function both ways from meromorphic and a we have a concept
of, of a residue. so if we multiply by z minus z0 to the n,
then we get something that's analytic. That's another way of just saying this,
here. and another way to say it, is that a
function is meromorphic, if its analytic, except for a set of isolated
singularities at its poles. And at those places is got expansions of
this type. that's, that's the characterization of
metamorphic functions that we're going to take advantage of.
And again, without going into details of complex analysis, I won't talk about
formal proofs of all these types of things.
but this sketch gives an understanding of the kind of functions that we're talking
about. They can be expressed as the ratio of two
analytic functions, and they can be expanded always in this form for each
pole near each pole. so in the functions that we've seen are,
it's usually quite easy to establish that they're meromorphic, and where the poles
are. so for example derangements.
That's meromorphic except there's a pole where z equals 1.
If you multiply it by 1 minus z, you get an analytic function.
in this one, it's you know, 1 over 1 plus z squared, it's meromorphic everywhere,
except at plus or minus i. For this one, for, this is the one for,
for set partitions there's a bunch of poles at 1 at 1 half, all the way up to 1
over r and so forth. So in practice it's fairly easy to
determine that the function's meromorphic, it's the ratio of two
analytic functions. And it's fairly easy to find the poles.
It's the places where the denominator is 0.
that's, that's really the key concepts that we need to know.
and this is what these things look like when we plot them so for example, 1 over
1 minus z to the 5th has five poles. those, those are called the, the roots of
unity and actually I'll talk some more about them later on.
and these are just plots of what the these other functions that arise look
like. And we'll look at more implications of
these later on. For example 1 over 2 minus e to the z,
that's going to pull whenever e to the z equals 2.
Well, if z equals log 2, then e of z equals 2.
But if you add 2 pi i for 2k pi i for any value of k, you also get a pole.
e to the log 2 plus 10 pi i, is also 2, so you're going to get a pole.
And then our plots, the poles turn up as black dots, because they get larger and
larger as you get closer to the pole. And we'll, revisit these kinds of
diagrams, later on. OK.
So the first idea is to extend the Koshi formula to integrate any curve that goes
around the pole. and so this is a result for a single
pole. If can have a meromorphic function, and
you've got a closed loop within its domain.
And there's a single pole inside that loop, and the interval around the loop is
2 pi i times the residue at, at the pole. that's the coefficient of h to the minus
1. and that's easy to prove from the things,
that we've seen. so for example if f of z is 1 over z then
that's got a pole at 0, and the residue is 1.
That's the coefficient 1 over z and we saw that the integral of 1 over z dz is
just 2pi i. just using the polar coordinates.
As such, you know, that's an easy example.
and let's look at a more, complicated example.
So what we can do is because s is a pole, we, we can expand h near that pole, and
write it as a power series of this form, starting at z minus s to the m, and and
going on. so and that's really the essence of being
meromorphic, is that you can write such an expansion near a pole.
so now we can then deform our curve. by the Koshi theorem to a circle that is
centered at s, and has no other poles. so because there's no other poles in
there, and then just integrate. so if we plug in the expansion and
integrate, then what's going to happen is, and we saw when we did our
integration example 5, that they're all 0, except for the one that is 1 over z
minus s. that's the only one that, that doesn't
cancel to 0. so that's what's left is just to go back
and look at that integration example. they all go to 0, except 2 pi i times the
the residue. so that's a single pole.
it gives us the residue the value of the integral is the residue at that pole.
so and this is a really significant kind of calculation, because what it says is
that the local properties of a function near the pole is connected somehow to
properties in the function elsewhere. In this case integral along a curve that
might be distant. it doesn't matter what the curve is, it's
only the local properties of the function near the pole that matter for a
meromorphic function. So generalizing the integrator around a
pole, we have what's called the Residue thereom.
If you have a meromorphic function, and you have a closed loop and it's where
it's defined to be meromorphic, then an integral around that loop, is equal to
sum of the residues, 2 pi i times the sum of the residues.
so take the residue i, at every pole and add them all up you get the value of the
integral. then, here's just a sketch of that proof
it's actually almost all of it. what we're going to do is we're going to
look at small circles, centered at each pole.
and what we're going to do is define a path.
this is kind of an intermediate version of the path.
That's the same as our original path, except it goes in and around, and out
again for each pole. In fact it'll do the perfect small
circle, and out again. So for every pole, we'll take our
original path, but for every pole we'll go in and grab it, and go and go out.
Now, actually in this curve, the poles are all outside the, the path.
So the integral around the path is 0, where we arranged it so their all
outside, even when it's, a circle like that, it's really outside the path.
So the integral 0 of the in and out lines cancel out.
One going one direction, one going the other way, direction.
And the circles is, the residues, by doing one pole at a time.
so that, immediately gives the result, that the, integral, around the path is
equal to, some of the residues. so that's a quite a general and powerful
theorem, and then we're going to be able to make, take advantage of that to get
coefficient asymptotics for meromorphic functions.
In fact the transfer theorem for that gives nearly exact results for
meromorphic functions. is, a direct application of the residue
theorem. So, the theorem says, if you have a
meromorphic function and you know the poles, then the coefficient of the
function is just polynomials over each pole to the nth power where the degree of
the polynomial has to do with the order of the pole.
And again I'll just quickly sketch this proof.
so now what we're going to do, is take an integral around a big circle of radius r.
we're going to take our function, and we're going to divide by z to the n, n
plus 1. and so by the residue theorem the value
of that integral is some of the residues inside.
and some of the residues inside, gives exactly these polynomials.
And just for example, if the pole of order 1, then the function grows like
this constant over z to the minus alpha and so therefore, the residue of the
function of over z to the n plus 1 is the same as the residue of this c over z
minus alpha to cvm minus 1. and that's just the z goes to alpha, that
just gives you alpha to the m plus 1. That's the coefficient of 1 over z minus
alpha. And there's is simply c over alpha to n
minus 1, n plus 1. You do that for every pole if it's of a
higher order, then you start to get the polynomials.
And I won't go through that detail. because we'll see another way to do that
in just a minute. so, value of that integral is is the,
these polynomials are a pole to the nth power and then it's easy to bound that
integral. because the value of the function on the
circle is going to be a constant that doesn't depend on n.
So when n gets exponentially small nm. so that's a quick sketch of a theorem
that gives us with exponentially small error a very accurate term equation for
the coefficients of a meramorphic generating function.
Now, but this is complicated. And what we what to do is, focus on the
leading term in the same way, as we did for polynomials.
but before doing that, we have to consider a few points.
So first one is some of the roots might be comp, complex.
Is that going to give complications? and the answer is it surely is, because
the leading term is going to depend on the distance for the origin of the pole.
and all the poles, are going to contribute to the leading term.
So for example, there's the nth roots of unity, so those are just e to the 2 pi ik
over n, of course 2 pi k over n plus i sin 2 pi k over n.
If you raise any one of those complex numbers to the nth power you get 1, and
they're all distance 1 from the origin. and so I already showed 1 over 1 minus z
to the 5th. So there's 1 over 1 minus z to the 25th.
there, so you have 1 over, those numbers to the nth power.
All of them, and they're all the same distance from the origin.
And we already saw an example of this phenomenon, when we did, the rational
generating function for 1 over 1 plus z squared.
that's a root of minus 1. so there is plus and minus i.
And then we saw that, these things mix up, so that the coefficient of z to the
end fluctuates and oscillates. so, you have to consider, all the poles
that are the same distance from the origin.
and that seems like that's going to be a problem because this kind of situation
might arrive and give us complicated expressions when we're trying to do
analysis of this sort. but, fortunately for combinatorial
generating functions, it's very often the case that's there's one route that's
closer to the origin, than all the others.
And not only that, there's a theorem called Pringsheim's theorem.
That says that if you've got a generating function that has non-negative
coefficients, and of course, the generating functions that we get for
analytic commenotoriac's always have non-negative coefficients, because
were're counting things. and then, if it's got radius and
convergence r, then the, the point z equals r, that's a real number, it's the
smallest positive real root. That one, is a singularity of the
function. Hm, so, you, it means that, for very many
of the cases that we need to consider. all we need to worry about, is the real
number that's closest to the origin. And the asymptotic growth, is that number
to the nth power. So for example, this is a generating
function, that we get when considering strings containing, no occurrence of four
zeroes in a row. It's got poles out there, but there's one
that's closer to the origin, and that's going to to determine the asymptotic
growth. And not only that, the contribution from
the other terms are exponentially small, they really can be safely ignored.
So, that's the implication, only the smallest positive real root matters, if
no others have the same magnitude. Now, if you do have a bunch of roots that
have the same magnitude, you can get really complicated periodicities.
and you can read about that starting on page 266, in the book if you're
interested. It's called the Daffodilemma, because the
curves that we have to consider maybe look a little bit like a a daffodil.
It can get very complicated. but so many of the combinatorial classes
that we've considered this doesn't, this doesn't come up
There's, a single root that's closest to the origin, and therefore, it's real, by
Pringsheim's theorem. so, that's going to lead us to a much
simpler theorem for the leading term, the asymptotics, the meromorphic generating
functions. so here's the theorem, it's the same
statement, conditions as for the general theorem.
meromorphic in a, a closed disc and size r, and it's analytic at the origin, and
everywhere on the circle. if alpha, is a unique closest pole to the
origin, that means all the other poles are furthered.
then it's real, and not only that, we know the coefficient asymptotics.
It's of the form, a constant times beta to the n times n to the m minus 1, where
m's the order of alpha. we have an explicit expression for the
constant. and Beta is 1 over alpha.
that's a theorem in that, this is just a quick proof sketch so near the pole we
can expand the function in this way. And again, since it's a poll of order 1,
where you're just going to prove a frame equals 1.
we just have the one term each one is, 1 over alpha minus z.
so you want to calculate h minus 1, one thing you can do, is take the limit z
goes to alpha, of alpha minus zh is z. and there are, the, approximation and I
add alpha to the function is approximated by h minus 1 over alpha minus z.
so then we can just go ahead and expand it.
So 1 over alpha, so it's h minus 1 over 1 minus 0 over alpha, 1 minus 0 over alpha,
is sum zdn over alpha to the n. and that gives us the, uh, [COUGH] the
coefficients that, the asymptotic growth is 1 over alpha to the n, and then the
constant is, well in this case m equals 1.
so it's minus 1 times f of alpha over, well, we'll look at this proof of exactly
where this constant comes from in a minute.
that's all going to be done on the next slide.
So just a couple of notes about this. So so I'll complete this, proof on the
next slide. So as I mentioned, the error is
exponentially small. now, if the, if they're close to the same
distance, there might be periodicities for some problems that you might have to
look at. you know, often the next term does
involve some kind of periodicities. now and the other thing to notice is, if
you go back and look at our transfer theorem for rational functions it's the
same. well and it ought to be the same, because
if f of g and g of 0 polynomials, you get the same kind of result.
but still, it's quite different paths, to this same result.
the residue calculus in Koshi's theorem and so forth, gives us the asymptotic
result that we need for a meromorphic functions.
And again, we've been through quite a bit of complicated abstractions in this
lecture. but really what you need to remember is
these simple formulas. and in very many cases, as we'll see in
the next lecture, it's simply a matter of, of plugging into these formulas to
get the coefficient asymptotic's. The essence of analytic commonotorics, is
we start with a commenotorial construction, and that gives us a
generating function equation. And then an analytic transfer theorem
like this takes, the generating function equation and immediately gives us the
coefficient asymptotic's. now before I go on, I want to justify
this constant that's the coefficient. so I mentioned before that when we
compute the constant if the poles of order 1, just by taking the limit of
alpha minus zh of z. Well, if you take that limit, then you
can use L'Hopital's rule, take the derivative of both sides.
Uh,and so that's alpha minus z times the derivative of f, plus f times the deriv
alpha minus c, which introduces a minus sign, on the bottom is g prime over z.
But, the pole of order 1, g prime of z is not going to be 0, so we can just plug in
alpha. It kills the first term, and we get minus
f of alpha over g prime of alpha. So that's an easy way to compute the
coefficient. if it's of order 2, then we have to apply
l'Hôpital's rule twice, and so we can do the expansion as before.
We have two terms now but we just take the leading term, and now our leading
term we're expanding 1 minus z over alpha squared.
and then that, because of the square, brings in a factor of n, into the leading
term, simply by elementary generating function exponentially.
and then the rest of the calculation is using l'Hôpital's rule twice.
take the first derivative, take the second derivative.
and if it's of order 2, the second derivative is non 0, and then taking z
equals alpha, kills all of the terms except 1.
and we're left with 2 f of alpha over g double prime of alpha, and then you can
convince yourself from that, that's of order m.
Then our coefficient that we need is minus 1 to the m, and f of alpha nth
derivative of a g, evaluated at alpha over alpha n, that's the coefficient.
and then the growth is, n to the n minus 1 over n, where m's the order of the pole
1 over alpha to the n. so a simple formula for the coefficient,
in terms of the order of the pole. And again there's a lot of calculations
here but I really think the bottom line is you can see some light at the end of
the tunnel. we've done a lot of calculations but what
we have in the end is for many, many examples.
of, First of all, we have an analytic transfer to take a meromorphic generating
function, into its asymptotic growth form.
In most of the cases that we're going to consider, that we have considered in
terms of commenotorial classes, the poles are order 1, so the growth is a constant
times Beta to the m, where beta's 1 over the closest route to the origin.
So all we have to do, is compute the dominant pole.
Now that's the smallest root where the denominator's 0.
maybe we have to use a ah, [COUGH] math package to do that but many times it's
simple, it's elementary. and you should check that no other no
other poles have the same magnitude, that's usually very easy, you usually
just do it with a plot. and then what's the residue from the
theorem? It's just f of alpha over g prime of
alpha an easy calculation. And, then the constant is just now, it
might, you might worry by g prime being 0, well if your prime is 0, then its not
order of 1, so you'll just have to adjust to do the order's of mk's, but we have a
formula for that, too. again that, doesn't come up, in a great
many of the commenotorial classes that we consider.
So the constant then, is just h minus 1 over alpha.
And the exponential growth factor, beta, is just 1 over alpha.
so that's the bottom line, is we've got a very simple method to transfer from
generating a function equation into constant times exponential growth factor.
so there has been no doubt a great deal of difficult and complicated mathematical
material in this lecture. but really the purpose of it, is to
persuade you that there's rigor in our being able to do these kinds of analytic
transfers. most of the time in applications we can
just use it without going back to the detail in difficult theorems that we've
talked about. so, just to give, just a couple of
examples so if our meromorphic function is rational like z over 1 minus z
squared, well there's, alpha, that's the root.
So it's phi hat, which is the same as 1 over phi, so the exponential growth's
going to be phi to the n. and what's the constant?
it's phi hat over 1 plus, 2 ha, 2 phi hat, which is 2 phi hat squared 5 minus
1. So that's just square root of 5.
and then, to get the coefficient we divide by phi n, which takes that out.
So that immediately gives the asymptotic's for that generating
function, which comes up in a couple of combinatorial classes.
this is the combinate generating functions for derangements.
so the pole is at 1, so f of alpha is e to the minus 1, is 1 over e.
g prime of alpha, is just 1. So, it's just 1 over e divided by 1, 1 to
the n. coefficient of z to the n, and hz is 1
over e. or to generalize, to generalize
derangements. so in, in that case f of, alpha again is
1. That's where the pole is, there's only 1
of them. evaluate the numerator at 1.
you get e to the minus h3, or one over e to the h3.
exponential growth is 1 to the n, which goes away, divide by alpha as 1.
so immediately we get the coefficient with a very simple calculation.
so just as an example, here, here's what we're going to be doing for the entire
next lecture is looking at how analytic combinatorics gets us from a
combinatorial specification, down to asymptotic results.
So we talked about generalized derangements.
That's a combinatorial construction and the symbolic method immediately gives
that generating function. And now, we have an analytic transfer, to
take us immediately from that generating function, right down to the asymptotic's
of the coefficients. you don't need to know too much about
Koshi's theorem or residues, or any of these things in order to be able to apply
this analytic transfer theorem. so, in the next lecture we're going to
see many, many, many more examples of this general idea that we can have an
analytic transfer that works for a, a broad variety of generating function
equations, and takes us right to the coefficient asymptotic's.
Ah, [COUGH] so just in terms of the general form of the coefficients that I
talked about at the beginning of this lecture.
and the first principle of coefficient asymptotic's is the location of the
singularities, tells us the exponential growth.
And the second one, is the nature tells us what about the sub, sub-expotential
factor. For meromorphic functions, if the
smallest real root is alpha, then the exponential growth factor is, 1 over
alpha. It's that location of the singularity,
closest singularity to the origin, that gives us the exponential growth.
And if it's a pole of order n, then it tells us the expo, the sub-exponential
factor is a polynomial n to the m minus 1.
that's a very, very general statement, and not only that, we have the specific
way to compute the constants as well. That immediately gets us, accurate
asymptotic results. And again, next lecture, you'll see many,
many, examples of this. I just want to to finish with, an idea
that this isn't, this approach to combinatorial analysis is, controversial
in some circles. so, for example, this is a quote from,
Riordan's book, which is a very important and influential book in combinatorics.
And what he said is that generating functions belong to algebra, not
analysis. so it's all about, using, manipulating
generating functions, and then setting coefficients equal, to learn things about
commentorial objects. and we saw some examples of that, in part
one of the course, early on, for those of you that took part one.
Like the Vandermon Convolution which is a sum on convolving polynomial
coefficients, that's easily proved via generating functions.
And what Reardon said in his second book, commentorial use recurrences generating
functions and such Transformations, as the Vandermon Convolution.
Others, that means people who are not combinatorialists, and so they should be
able to do what they want, but Riordan says, to my horror, they use contour
intervals, differential equations, and other resources in mathematical analysis.
Not sure what he means by, to my horror. But I can remember reading, quotes like
this and, Riordan's not the only one, as a student, and being completely, really
confused, about what to do. even for derangement's if you're looking
for the coefficient of z to the n, and e to the minus z over 1 minus z, you have
to do a convolution. and you have to do some reasoning with
that convolution, to get to the asymptotic result, 1 over e.
I can remember first learning these kinds of manipulations, and being a little
mystified by how we we get to 1 over e, particularly since it's such an accurate
result. And that's just for a derangement's which
are permutations without singleton cycles.
if you had a generalized derangement's like permutations without cycles of
length 1, 2 or 3, then you've got a four-way convolution.
how are you going to get from this kind of formula to the asymptotic result 1
over e to the 1 plus 1 half plus 1 1 3rd, a very simple asymptotic result.
and I still to this day, don't understand what Riordan's plan would be for trying
to solve this problem. A little known many, many more general
problems that we're able to address by using contour intervals, and other
resources of mathematical analysis. That's precisely what we're doing in
order to get simple way's to derive asymptotic estimate for enumerating, and
studying property of a very broad variety of combinatorial classes.
and next time I'll certainly convince you of that.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
