Summary

Loading...

來自 Princeton University 的課程

Analytic Combinatorics

16 個評分

Princeton University

Analytic Combinatorics

16 個評分

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.

從本節課中

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

與講師見面

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science

All right, so let's summarize what we've done in this lecture.

as promised, we've looked at from an analytic combinatorics point of view a

whole range of classic combinatorial classes.

from bit strings to derangements, to surjections, to alignments, to set

partitions, integers, compositions. In every single one of 'em, we took a

specification, immediately to a generating function with the, via the

symbolic method, and then, immediately to coefficient asymptotics, using the

meromorphic transfer theorem. Not only that, not only are we able to do

these classic combinatorial classes but also we can do variations.

Like restrict the bit strings to not contain a particular pattern.

Or generalize derangements where We parameterize the number of cycles that

are disallowed. same way with the surjections and for

compositions all different types of restrictions and as well as the

numerants. all of those things, again, are the same

basic idea of a speck that goes into a generating function, goes to coefficient

asymptotics immediately. Handling these types of problems without

analytic combinatorics, which you can find in the literature is possible

because underlying the calculations, there's nothing particularly novel or

important to this point. it's possible, but it requires a huge

amount of calculation. And analytic combinatorics allows us to

skip over the top. to immediately derive asymptotic results

without much calculation. and that's important because the idea of

a speck gives us an open ended way to specify combinatorial classes.

without having to worry that we may not be able to understand their coefficient

asymptotics. actually we can for this huge set of

combinatorial classes. so as promised I, I think in this lecture

you've seen that our transfer theorem for mero, meromorphic generating functions

gives immediate analysis of a large variety of classes.

We can just as easily handle variations. And then, we have the idea of a schema,

which unifies the analysis for a whole family of classes, including analysis of

parameters. now and also there have been several

other schemas developed that are talked about in the text.

so what we have do next is look at generating functions that are not

meromorphic. and that's going to be the topic of the

next two lectures when we get functions with singularities that are not isolated

that are not poles. and that'll be our topic for the next two

lectures.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取