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. And then the bound is Just e to the zeta over zeta to the N, which is e to the N plus one over N plus one to the N. so it's a saddle point bound. now if since n plus one to the n if you if you want to do a little more accurate asymptotics on that, 1 plus 1 over n to the n goes to e, so that's about e to the n over n to the n. and I'm just doing this sketch now cause we're working with [UNKNOWN], and we can be more precise and carry it out there [UNKNOWN] accuracy if we wanted. and so this is just to check how close this bound is to what we know. Well, what we know is from Sterling's approximation, one over N factorial is about e to the N over N to the N squared of 2 pi N. So we're off. This bound is too high, just by a factor of square root of 2 pi N. which is not bad considering it grows exponentially. So we get a pretty good approximation to Of the function with this really simple bound. So that's a saddle point bound. And the saddle point method, what is going to be just about getting rid of that factor or finding a proximation that's more accurate and brings that factor back in. Now let's look at another example. suppose we want to estimate 2N choose N. so that's the coefficient of z to the N in 1 plus z to the 2N. so so now we'll just take G of z to be 1 plus z to the 2N. the saddle point equation is to take the ratio G prime over G and set equal to N plus one so in this case that works out to 2NC equals N plus 1 times one plus C. Or the saddle point is N plus 1 over N minus 1. so that's where the exact saddle point is and then the saddle point bound is to take 1, To is to G of zeta over zeta to the N, so N plus 1 over N minus 1 to the N and then G of zeta, 1 plus that 2N and work it out, then we get 4N squared over N squared minus 1, to the N. And again that's about 4 to the N. And how close is that to what we know? Well we know that 2N. Is about 4dN over square root of pi N. Of what we did from Sterlid's approximation earlier on. So, again, the bound is off too high, only by a factor of about square root of pi N. so, s,s, simple method for estimating the value of coefficients just by determining the saddle point. and then plugging in that value to the function divide that by the Nth power. and, it's off by a little bit, but not much considering the exponential growth. That's the development of saddle point bounds.