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.
Other Familiar Examples
Loading...
From the course by Princeton University
Analytic Combinatorics
16 ratings
From the lesson
Applications of Rational and Meromorphic Asymptotics
We consider applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes that we encountered in Lectures 1 and 2. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction.
Meet the Instructors
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Alright, next, let's look at some other examples that we use the symbolic method
for to get generating function equations. And we'll look at several of the examples
that we considered in the first two lectures.
And see that mero-, meromorphic asymptonics directly gets us to accurate
asymptotic estimates of coefficients. So derangements that's one of our classic
problems. Where we want to know the number of
permutations of size n that have no singleton cycles.
So, that's a familiar combinatorial construction.
A derangement is a set of cycles where the length of all the cycles is greater
than one. That immediately translates to this
generating function or equation, e to the minus z over 1 minus z.
That's a meromorphic function. It's the ratio of two analytic functions.
So our basic procedure is going to apply. what's the singularity?
There's only one. It's z equals 1.
it's got a, a, a strange structure outside but as for negative z it gets
large, but the singularity is that z equals 1.
so then we can easily compute the residue the derivative of the denominator is
minus 1, which cancels the minus. And the numerator valued at the
singularity is just e to the minus 1. so then the meramorphic transfer theorem
tells us that the coefficient is this e to the minus one over one in the
exponential growth, is one to the n. So our asymptotic result is that the
coefficient of z to the n, which n factorial coefficient z to the n, in that
generating function is asymptotic to and factorial over e.
[COUGH] and that comes immediately from the meromorphic transfer theorem.
And this one also we can generalize. Well one thing first to notice is that
these estimates are extremely accurate, even for small, and for n equals 5 we're
within point 1. And that's because the in this case
there's the Error term is simply to do with the numerics of the function.
Other cases are singularities, but they're exponentially smaller.
so let's look at the class of all permutations.
with no cycles of length less then or equal to m or m's a perameter.
so the again, the comonotorial construction through the symbolic method
immedietly gives a generating function an equation that can be pretty complicated
to try to find exact expressions for coefficiants in that equation.
But the meromorphic transfer theorem immediately gives us the asymptotics just
as before again, the, there's a pole at one and I'll show the since I have m, I
don't have any plot. [LAUGH] and the residue is the same as
before. evaluating the numerator at one is e to
the minus h m. 1 plus 1 plus one third minus a e to
minus a h and the derivative of the denominator is minus 1, which cancels the
minus. So we get e to the minus hm.
and again exactly the same argument, there's no exponential growth, so it
approaches 1 over ehdm. So, whatever m is, you can approximate
the number of permutations with no cycles of length less or equal to m by that
simple formula, about 1 over e to the h m of em.
Of all permutations have no cycles of length list in the recall of m.
And that's a very accurate going to be accurate result.
and lets look at the singularities of those.
So that's the one I showed for no cycles of size 1.
here's with node cycles of size 2. Still, there's just one singularity but
the growth of the what goes on outside changes in interesting ways.
And it's still only one singularity, and it's on the real line and it's, it's
closer to the origin by Pringsheim's Theorem, so we know all this from the
theorems. In terms of the calculation or we can
all, the whole growth of this complicated thing, is even though it's a fantastic
thing, looks like an integrated circuit or something.
the whole growth is just determined by the value of that singularity that's
closest to the origin. so that's that's derangements, and again,
that's kind of a poster child for analytic combinatorics, because it's so
easy to get to that asymptotic result. Apply the symbolic method apply the
meromorphic transfer theorem, and you're there.
well, that was the same for strings, and actually that's going to be the same for
many, many of the combinatorial classes that we've considered.
here's another one that we talked about. surjections.
so these are the coupon collector sequences and so they're words of length
n With the property that for some m, each
of the fir-, first m letters appears at least once.
So these are all the ones where for m equals 2 here's the one's for m equals 3,
and here's the one's for m equals 4 in this case.
So that's surjections. And that's one way to look at it, so how
many surjections are there. We saw the comminitorial construction for
surjections. A surjection is just a sequence of sets,
that are, none of which are empty. And that immediately translates to the
generating function equation. set that's not empty is z, z minus 1.
Sequence is 1 over 1 minus. So that's equal to 1 over 2 minus e to
the z. That's a meromorphic function, it's a
ratio of two analytic functions. So what we care about is the poles.
This one has a lot of poles. whenever z equals log 2 plus or minus 2
to the, 2 pi i. there's going to be a pole.
the only one we care about is the one that's on the real line, closest to the
origin. and we just go ahead and turn the crank,
and apply the theorem to compute the residue.
so differentiate the bottom you get minuses, you cancel g minus log 2 is just
one half. so, the coefficient is going to be 1 over
2 log 2 in the exponential growth is going to be log 2 to the n.
1 over 2 log to the n plus 1. Again, immediately from the construction
to the generating function, through the transfer theorem, to the asymptotic
result. again the, these other poles might
contribute something to the growth but it's exponentially small.
And these are pretty far away. This is extremely accurate.
Even for 3 it's accurate to three decimal places.
and we can look at general versions of this like double surjec, surjections.
So that's like Coupon collector sequences, where you want to have two of
everything. so for sum m, each of the first m letters
appears at least twice. and, and again, there's lo-, the
applications for wanting to study these types of combinatorial objects.
in terms of the analytic combinatorics is just generalizing the one that we just
did. It's a sequence of sets where the sets
are all two or more. translates to the generating function.
So sets all two or more is e to the z minus z minus 1.
Sequence is 1 over 1 minus that so we have this generating function for r of z.
Again, that's meromorphic ratio of two analytic functions.
What we care about is when the denominator is 0.
this one's a little, getting to be a little more complicated in terms of the
singularities but the keypoint is that there's only one on the real line.
its closet to the origin. The others are going to be exponentially
small. so we have to do a calculation to find
the value where on the real line where e to the z equals z plus two and that turns
out to be 1.14 in this case. And we go ahead and calculate the
residue, which is just the derivative of that evaluated here and turns out to be
just 1 over that plus 1. so again that little calculation
immediately gives the asymptotic growth for a number of double serjections.
Bing, bing, bing no matter how complicated the generating function gets,
we go right through it to get the simple asymptotic result.
and this one also generalizes so that's one, that's two.
Now you can see the extra poles are getting their influence is getting
weaker. well there's one of the imaginary axis
that is getting more, and then that one turns into two, and these other ones that
are out here are very tiny. and then, turns into three, and starts to
look a little bit more like what we saw for strength.
but still, there's only one of those poles on the real line that's closest to
the origin, and that's the one whose growth determines completely the
asymptotics of the coefficient. and this is a big one for surjections.
and these, these poles, it actually In fact, gets a little bit less accurate.
These are this, this one is closer than all these other ones.
The on the real line is closer to the origin than all the others.
But now they're going to start to contribute possibly to what we see when
we do calculations and it's a little bit like the roots of unity and then there's
going to be therefor some oscillation. But all of that is explained by
properties of the function in the complex plane.
And we can do results as precise as we want.
Not as long as we're willing to do some calculations.
All right. And here's another one alignments.
so this is sequences of labelled cycles. It's not quite like permutations, which
are sets of labelled cycles. so this is sequences where the order
matters. It's called alignments.
and this is just an example giving the number of alignments for one, two, three,
and four. And by now pretty much everyone can
figure out what's going to happen next. we're going to build a common atorial
construction, sequence of cycles. cycle is log of 1 over 1 minus, the
sequence is 1 over 1 minus that, so there's the generating function for
alignments. without really much thought at all.
That's a meromorphic function. it's ratio of two analytic functions, so,
it's when the denominator gets out to be zero, that, that we care about.
This one has got one giant singularity, where log of 1 over 1 minus z equals 1,
and that's exactly when z equals, 1 minus, 1 over e.
you plug that in, then you get a check, that's the dominant singularity.
And there's others out there. so, but then we just do the calculation
numerator is 1 differentiate that, you get 1 over 1 minus z.
Evaluate it, one over one minus z, just get one over e again.
so that tells us that the exponential growth is 1 over 1 minus e to the n.
and the constant is this divided by that. Which gives the m plus 1.
so that's again, enumerating the alignments.
In a combinatorial class maybe we never heard of.
But we can immediately get to coefficient asymptotics that's extremely accurate.
Uh,[COUGH] and this again shows how accurate it is even for small and
And a final example that we looked at is set partitions,[COUGH] how many ways are
there to partition an n element set into r subsets, and we talked about this one
in Lecture 3. And this is the one that the application
is rhyming schemes. How many ways are there to rhyme a poem.
so you start by putting the first line in set a and anybody that rhymes with that
goes into set a. The first one that doesn't rhyme goes
into set b and so forth. and so there's a correspondence between
pa, partitioning and allows an our set, our sub sets and and different rhyming
scenes on these other applicat, many other applications of this.
So how do we do the asymptotics of this one.
Well, eh, and we did this combinatorial construction in lecture three, it's,
it's, the first, eh, times the sequence of them.
Times the second, times the sequences of both of them.
Times the third, times the sequence of all three.
And so forth up to R. and that immediately translates to a
simple generating function. And again this is a rational that is
meromorphic. It's the ratio of two analytic functions.
We're interested in the root that;s closest to the origin.
what root is that? well there's 1, 1 half and so far 1 over
r is going to be closest to the origin and actually the one that's closest to
the origin is the little one but that's the one that matters.
and so now we just again go trhough the procedure.
1 over r is the pole closest to the origin.
So, that's going to give us the exponential growth which is going to be r
to the n, the inverse of that. The residue is evaluate the numerator at
1 over r and value the derivative of the denominator at 1 over r.
there's a little calculation there involving r to the rs that cancel.
The result is 1 over r times r factorial. that immediately gives the asymptotic
growth that the number of poems with r rhymes is asymptotic to r to the n over r
factorial. And so that's four familiar classes and
generalizations that are immediately handled by meromorphic asymptotics.
All showing, with analytic combinatorics, we can do a construction, immediately to
a generating function, immediately to asymptotics of the coefficients.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
