# Analytic Combinatorics/Saddle-point Method
## Theorem

Theorem due to Flajolet and Sedgewick.
If $F(z)$ is an admissible function then
    $[z^{n}]F(z)\sim {\frac {F(\zeta )}{\zeta ^{n+1}{\sqrt {2\pi f^{''}(\zeta )}}}}$ as $n\to \infty$
where $\zeta$ is such that $F^{'}(\zeta )=0$ and ${\frac {F(z)}{z^{n+1}}}=e^{f(z)}$.

## Proof

Proof due to Flajolet and Sedgewick.
By Cauchy's coefficient formula:
    $[z^{n}]F(z)={\frac {1}{2\pi i}}\int _{C}{\frac {F(z)}{z^{n+1}}}dz$
We can visualise this as a 3D graph whose $x$ and $y$ axes are the real and imaginary parts of $z$ respectively and the $z$ axis is the real part of ${\frac {F(z)}{z^{n+1}}}$.
For the generating functions we are interested in, ${\frac {F(z)}{z^{n+1}}}$ has a saddle-point on the positive real axis. This is the highest altitude of the green path in the above graph. Call this $\zeta$.
Being an analytic function (except at $z=0$), we can deform the contour to go through the saddle-point. The biggest contributor to the integral is made by the part of the contour near the saddle-point (call this $C_{0}$, which is the red part of the path in the graph below). The rest of the contour (call this $C_{1}$, the green part of the path) contributes relatively little.
    ${\frac {1}{2\pi i}}\int _{C}{\frac {F(z)}{z^{n+1}}}dz={\frac {1}{2\pi i}}\int _{C_{0}}{\frac {F(z)}{z^{n+1}}}dz+{\frac {1}{2\pi i}}\int _{C_{1}}{\frac {F(z)}{z^{n+1}}}dz$
In the below, we set ${\frac {F(z)}{z^{n+1}}}=e^{f(z)}$
    $[z^{n}]F(z)={\frac {1}{2\pi i}}\int _{C}{\frac {F(z)}{z^{n+1}}}dz={\frac {1}{2\pi i}}\int _{C}e^{f(z)}dz$
We can deform the contour even more to make the part of the contour near the saddle-point a straight line (in the complex plane). $C_{0}$ is deformed to a straight, vertical line, perpendicular to the real axis, crossing the saddle-point, starting from $-ia$ to $ia$. $a$ is chosen such that $f^{''}(\zeta )a^{2}\to \infty$ and $f^{'''}(\zeta )a^{3}\to 0$ as $n\to \infty$. This is so that the Taylor series expansion around $\zeta$
    $f(z)=f(\zeta )+{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}+{\frac {1}{6}}f^{'''}(\zeta )(z-\zeta )^{3}+\cdots$.
can be reduced to just $f(\zeta )+{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}$.
$f^{''}(\zeta )={\frac {F^{''}(\zeta )}{F(\zeta )}}+{\frac {n+1}{\zeta ^{2}}}$ is real-valued because $\zeta$ is real and $F(z)$, being a generating function, has real coefficients. $z=\zeta +ix$, so $(z-\zeta )^{2}=-x^{2}$ is real. Therefore, ${\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}$ is real-valued.
So, any imaginary part of $f(z)$ can be moved outside the integral, leaving just a real-valued integrand:
    ${\frac {1}{2\pi i}}\int _{C_{0}}{\frac {F(z)}{z^{n+1}}}dz={\frac {1}{2\pi i}}\int _{C_{0}}e^{f(z)}dz\sim {\frac {e^{f(\zeta )}}{2\pi i}}\int _{C_{0}}e^{{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}}dz$
This also means that the real-valued surface we discussed in the beginning is a valid estimate of the potentially complex-valued ${\frac {F(z)}{z^{n+1}}}$.
$C_{0}:x\in [-a,a]\to ix+\zeta$
We change variables to remove the imaginary part of the interval and turn it into a real-valued integrand over the real line. Setting $g^{-1}(x)={\frac {x-\zeta }{i}}$:
    $\int _{C_{0}}e^{{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}}dz=\int _{-a}^{a}e^{{\frac {1}{2}}f^{''}(\zeta )(ix+\zeta -\zeta )^{2}}idx=i\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx$
    $\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx=\int _{-\infty }^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx-2\int _{a}^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx$
Because $e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}$ is very small for large $x$:
    $\left|\int _{a}^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx\right|\leq Ae^{-{\frac {1}{2}}f^{''}(\zeta )a^{2}}$
Due to our choice of $a$ before, as $n\to \infty$, $e^{-{\frac {1}{2}}f^{''}(\zeta )a^{2}}\to 0$.
Therefore, the integral can be estimated by a Gaussian integral which we know how to calculate:
    $\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx\sim \int _{-\infty }^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx={\sqrt {\frac {2\pi }{f^{''}(\zeta )}}}$
Putting it all together:
    ${\frac {1}{2\pi i}}\int _{C}{\frac {F(z)}{z^{n+1}}}dz\sim {\frac {e^{f(\zeta )}}{2\pi i}}\int _{C_{0}}e^{{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}}dz={\frac {e^{f(\zeta )}i}{2\pi i}}\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx\sim {\frac {e^{f(\zeta )}}{2\pi }}{\sqrt {\frac {2\pi }{f^{''}(\zeta )}}}={\frac {F(\zeta )}{\zeta ^{n+1}{\sqrt {2\pi f^{''}(\zeta )}}}}$

## Admissibility

This formalises the conditions under which we can apply the saddle-point method. Definition from Flajolet and Sedgewick and Wilf. Also known as Hayman-admissibility.
The function $F(z)$ is admissible if:
* $F(z)$ is a function with radius of convergence $R\quad (0<R\leq \infty )$
* There exists an $R_{0}<R$ such that $F(r)>0\quad (R_{0}<r<R)$
* H$_1$: $\lim _{r\to R}a(r)=+\infty$ and $\lim _{r\to R}b(r)=+\infty$
* H$_2$: There exists a function $\delta (r)$ defined for $R_{0}<r<R$ such that $0<\delta (r)<\pi$ and as $r\to R$
          $F(re^{i\theta })\sim F(r)e^{i\theta a(r)-{\frac {1}{2}}\theta ^{2}b(r)}$
    uniformly for $|\theta |\leq \delta (r)$
* H$_3$: Uniformly for $\delta (r)\leq |\theta |\leq \pi$ and as $r\to R$
          $F(re^{i\theta })=o\left({\frac {F(r)}{\sqrt {b(r)}}}\right)$

### Intuitive explanation

To find the coefficients of a function, we can use the Cauchy coefficient formula. This requires us to find the integral of a path in the complex plane. Imagine trying to estimate this integral, displayed as the red and green line below.
The biggest contribution to the integral comes from around the saddle-point (displayed in red) and the tail's contribution (displayed in green) is negligible (by H$_3$).
Therefore, to estimate the integral of the entire path you can estimate the integral of just the red part of the path. This is the asymptotic relation described in H$_2$.

## Example

Example from Wilf and Flajolet and Sedgewick.
Say we want to estimate the coefficients of $e^{z}$:
* $e^{z}$ has radius of convergence $+\infty$ and is positive for all $z\geq 0$.
* H$_1$: $a(z)=z{\frac {(e^{z})'}{e^{z}}}=z{\frac {e^{z}}{e^{z}}}=z$. Therefore, $\lim _{z\to +\infty }z=+\infty$.
* H$_1$: $b(z)=z^{2}{\frac {d^{2}}{dz^{2}}}\ln e^{z}+z{\frac {d}{dz}}\ln e^{z}=z^{2}{\frac {d^{2}z}{dz^{2}}}+z{\frac {dz}{dz}}=z$. Therefore, $\lim _{z\to +\infty }z=+\infty$.
* Find the saddle-point $\zeta$ by solving the equation $a(\zeta )=\zeta =n$. Therefore, $\zeta =n$ and the path of integration is the circle of radius $n$ centred at the origin.
* Choose $\delta (ne^{i\theta })=n^{-{\frac {2}{5}}}$.
* H$_3$: For $n^{-{\frac {2}{5}}}\leq |\theta |\leq \pi$ as $n\to +\infty$
    $|e^{ne^{i\theta }}|=e^{n\cos \theta }\leq e^{n\cos n^{-{\frac {2}{5}}}}=o\left({\frac {e^{n}}{\sqrt {n}}}\right)$.
* H$_2$: For $n<1\quad e^{ne^{i\theta }}\sim e^{n+i\theta n-{\frac {1}{2}}\theta ^{2}n}=e^{n}e^{i\theta n-{\frac {1}{2}}\theta ^{2}n}$ (due to the power series expansion of $e^{i\theta }$).
* Apply the theorem: $[z^{n}]e^{z}\sim {\frac {e^{n}}{n^{n}{\sqrt {2\pi n}}}}$.

## Saddle-points of higher order

Theorem from Flajolet and Sedgewick.
The above assumes $F'(\zeta )=0$ and $F''(\zeta )\neq 0$. In the case where all derivatives up to the $p$th are zero but $F^{(p+1)}\neq 0$, we call it a saddle-point of order or multiplicity $p$.
If $F(z)$ has a saddle-point of order $p+1$:
    $[z^{n}]F(z)\sim {\frac {\omega }{p}}\Gamma \left({\frac {1}{p}}\right){\frac {F(\zeta )}{\zeta ^{(n+1)}{\sqrt[{p}]{-f^{(p)}(\zeta )/p!}}}}$
where $\omega ^{p}=1$.

## Notes

* ↑ Flajolet and Sedgewick 2009, pp. 553.
* ↑ Flajolet and Sedgewick 2009, pp. 551-554.
* ↑ Flajolet and Sedgewick 2009, pp. 549.
* ↑ Flajolet and Sedgewick 2009, pp. 565.
* ↑ Wilf 2006, pp. 199.
* ↑ After Walter Hayman.
* ↑ Wilf 2006, pp. 198.
* ↑ Flajolet and Sedgewick 2009, pp. 555-557.
* ↑ Flajolet and Sedgewick 2009, pp. 603.
* ↑ Flajolet and Sedgewick 2009, pp. 545.

## References

* Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
* Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.