Other Familiar Examples

Loading...

En provenance du cours de Princeton University

Analytic Combinatorics

19 notes

Princeton University

Analytic Combinatorics

19 notes

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. All the features of this course are available for free. It does not offer a certificate upon completion.

À partir de la leçon

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.

Bitstrings16:51

Other Familiar Examples 15:29

Restricted Compositions 9:42

Supercritical Sequence Schema 14:49

Rencontrer les enseignants

Robert Sedgewick
William 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.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play