Applications

Loading...

来自 Princeton University 的课程

Analytic Combinatorics

22 个评分

Princeton University

Analytic Combinatorics

22 个评分

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.

从本节课中

Saddle Point Asymptotics

We consider the saddle point method, a general technique for contour integration that also provides an effective path to the development of coefficient asymptotics for GFs with no singularities. As usual, we consider the application of this method to several of the classic problems introduced in Lectures 1 and 2.

Modulus Surfaces17:54

Saddle Point Bounds 9:15

Saddle Point Asymptotics 18:47

Applications 5:13

AC Wrap-up 11:43

与讲师见面

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

So let's look at some applications of Saddle-Point Asymptotics to combinatorial

problems. so, one problem that we saw very early on

is that we can write down generating function equations for the number of

permutations that have no long cycles. So in simplest cases, involutions where

all the cycles of link one or two. so immediately from the symbolic method

we get the generating function for involutions.

Is i of z equals e to the z plus e squared over two.

that's a function that's got no singularities and it's immediately

amenable to the saddle point method. so, so we have, e2, a function.

All we need to do is take the derivatives, of that function and set the

first one to zero to find the saddle point.

and then so, that's the function, We take, z plus z squared over 2, then

minus n plus 1 log z, because of the, z to the n plus 1, we put in for Crouch's

formula. saddle-point is where the first

derivative is equal to 0 and so that's turns out to be a quadratic equation in

this example and it's about square root of n minus one half.

Again, we want to work with approximation to the saddle-point to simplify

calculations. and so then, the saddle-point

approximation says that we plug that square root of n to the n minus one half

into the original equation and that immediately gives the saddle-point in

asymptotics. E to the square root of n, square root of

m plus n over 2 minus one fourth. over 2 and the end of the two squared of

pie n. That's a kind of a complicated equation

but that's the asymptotics for this problem.

in, actually, we're interested in factorial time set coefficients, so just

plugging in a Stirling's approximation. gives, that asymptotic expression for

involutions. Fairly straightforward calculation using

saddle point asymptotics. now again, you have to check

susceptibility or give up on the square root to 2 pi N factor.

it's here's another example set partitions that we looked at.

How many ways are there to partition a sentence size n?

from the symbolic method we immediately get e to e [UNKNOWN] e to the e to the z

minus 1 that's now immediately amenable to saddle point.

we start with ez minus 1 minus m plus 1 log z so, our saddle point is where zeta,

e to the zeta equals n plus 1. That's at about log n minus log log n.

Now that one, you can plug in, but you get a fairly complicated, complex

expression. And just since we're near the end of the

lecture, just look at the bound. The bound says just plug in g is zeta

over zeta to the n. And you see that it's about n over log n

to the n is the saddle point bound for this problem.

And we could get rid of the square root of 2 pi n factor with some work and some

basic asymptotics. but, as is illustrated by so many of

these problems, maybe using the bound is a good place to start.

so there's many combinatorial applications.

So, so we looked at e to the z which is generating function just for [UNKNOWN]

and central binomial or catalan. And involutions and set partitions didn't

go as far as doing the coefficient asymptotics.

there's a few other examples in the book. but definitely some of these calculations

are quite complex, and it would be more in advanced analysis.

so, I'm not going to claim that the saddle point asymptotics is as simple as

a transfer theorem as we saw for many other examples early on.

but still this place is the whole idea in context and illustrates that.

We do have approaches to cover all the generating functions that we can get from

this symbolic method. that's applications of the saddle point

method.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2019 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取