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.

Â