0:04
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.
2:39
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.
3:14
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.
3:59
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.
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
