Now we're going to look at the development of saddle point bounds for

generating function coefficients using [INAUDIBLE] integration.

the basic idea is very simple. Now, we start with Cauchy's coefficient

formula, which says that given an analytic function G of z.

The coefficient of z to the N and G of z is one over two pi i integral over a

circle that contains the origin, G of z, dz over z to the N+1.

so, just to look at an example, let's look at the function post G of z is e to

the z and we're looking for coefficient z to the fifth.

So that means the function that we're integrating, the e to the z over z to the

sixth. that's a plot of that function.

it's got a pole at zero, and then as the real part gets large it starts to get

large and there's obvious saddle point in there.

now, this plot is actually scaled substantially.

I think that it's only a point, a thousand pi or something.

We'll see some of the numbers in a minute.

But still that's what it looks like. so, the idea of a saddle-point bound is

to find a saddle-point and we always use zeta the Greek letter zeta for the

saddle-point. and then, for our circle we use the

circle of radius zeta. and that, so this is what the integral

will be, be adding up, the height under that circle.

And as you can see, for most of the range it's very, very small.

but even so, if we just take the highest point of the circle, which is the

saddle-point the integrand is going to be less than the value of the function

evaluated at zeta everywhere on that circle.

So then the value of the integral is just going to be as if we had that constant

and that will give us a, a very strong bound.

Now what's zeta it's the solution to the derivative this function equals zero.

and that's just doing the math. it's G prime over z to the N+1 minus N+1,

G over z to the N+2 multiplied by z to the N+2, we get z G prime over G is N

plus 1. That's known as the saddle-point

equation. so that's the idea.

Find zeta and just use the bound of G of zeta over zeta to, to the N+1.

So let's take a, a look at a couple of well here's a formal statement of the

bound. so if G is analytic finite radius of

convergence R with non negative coefficients which are generating

functions from analytic combinatorics always do.

Then the coefficient of z to the N and G of z is less than or equal to G of zeta

over zeta to the N, where zeta is the saddle-point.

Now, that's just a formal statement of the equation.

and again, it just is by Cauchy coefficient formula you take z to be

circle of a radius zeta, and change to polar coordinates.

then we're getting an extra zeta and then if we integrate and everything is

constant then the two pi goes away, and all that's left is G of zeta over zeta to

the n. so, so that's a, of, effective bound that

we can use to at least understand something about the growth of generating

functions coefficients. so for example in our example we're

trying to find a coefficient z to the 5th in E of z so that's we're looking at e to

the z. what's the saddle point?

the saddle point is zeta equals 6. so saddle point equation is G prime over

G which comes out to be 1, leaves us zeta equals 6.

and so the saddle point bound says that we know that coefficient of z to the 50

is z is 1 over 5 factorial. The bounds says that that's going to be

less than or equal to e to the 6th over 6 to the 5th.

and if we just compute those down the left side, it's, you know, 0.008, and on

the right side, it's 0.009. Pretty good bound, even for just the

small value. Five.

So, in general, just doing that same calculation.

let's see how well the saddle point method works for estimating one over N

factorial. so that's coefficient of z to the N and e

to the z. E to the z is the generating function

with no singularities. We're trying to estimate coefficient of z

to the N and e to the z. so saddle point methods, we take G of z

equals z to the z. Solve the saddle point equation.

Saddle point equation is G prime over G times Z equals N plus one so it's going

to tell us that the saddle point is zeta equals N plus one.