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.

Applications

Analytic Combinatorics

Meet the Instructors