# Analytic Combinatorics/Saddle-point Method

## Theorem

Theorem due to Flajolet and Sedgewick[1].

If ${\displaystyle F(z)}$ is an admissible function (we will discuss what this means later) then

${\displaystyle [z^{n}]F(z)\sim {\frac {F(\zeta )}{\zeta ^{n+1}{\sqrt {2\pi f^{''}(\zeta )}}}}}$ as ${\displaystyle n\to \infty }$

where ${\displaystyle e^{f(z)}={\frac {F(z)}{z^{n+1}}}}$ and ${\displaystyle \zeta }$ is such that ${\displaystyle F^{'}(\zeta )=0}$.

## Proof

Proof due to Flajolet and Sedgewick[2].

${\displaystyle [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 ${\displaystyle x}$ and ${\displaystyle y}$ axes are the real and imaginary parts of ${\displaystyle z}$ respectively and the ${\displaystyle z}$ axis is the real part of ${\displaystyle {\frac {F(z)}{z^{n+1}}}}$.

For the generating functions we are interested in, ${\displaystyle {\frac {F(z)}{z^{n+1}}}}$ has a saddle-point on the positive real axis[3]. This is the highest altitude of the green path in the above graph. Call this ${\displaystyle \zeta }$.

Being an analytic function (except at ${\displaystyle 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 ${\displaystyle C_{0}}$, which is the red part of the path in the graph below). The rest of the contour (call this ${\displaystyle C_{1}}$, the green part of the path) contributes relatively little.

${\displaystyle {\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}$

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). ${\displaystyle C_{0}}$ is deformed to a straight, vertical line, perpendicular to the real axis, crossing the saddle-point, starting from ${\displaystyle -ia}$ to ${\displaystyle ia}$. ${\displaystyle a}$ is chosen such that ${\displaystyle f^{''}(\zeta )a^{2}\to \infty }$ and ${\displaystyle f^{'''}(\zeta )a^{3}\to 0}$ as ${\displaystyle n\to \infty }$. This is so that the Taylor series expansion around ${\displaystyle \zeta }$

${\displaystyle 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 ${\displaystyle f(\zeta )+{\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}}$.

${\displaystyle f^{''}(\zeta )={\frac {F^{''}(\zeta )}{F(\zeta )}}+{\frac {n+1}{\zeta ^{2}}}}$ is real-valued because ${\displaystyle \zeta }$ is real and ${\displaystyle F(z)}$, being a generating function, has real coefficients. ${\displaystyle z=\zeta +ix}$, so ${\displaystyle (z-\zeta )^{2}=-x^{2}}$ is real. Therefore, ${\displaystyle {\frac {1}{2}}f^{''}(\zeta )(z-\zeta )^{2}}$ is real-valued.

So, any imaginary part of ${\displaystyle f(z)}$ can be moved outside the integral, leaving just a real-valued integrand:

${\displaystyle {\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 ${\displaystyle {\frac {F(z)}{z^{n+1}}}}$.

${\displaystyle 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 ${\displaystyle g^{-1}(x)={\frac {x-\zeta }{i}}}$:

${\displaystyle \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}$
${\displaystyle \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 ${\displaystyle e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}}$ is very small for large ${\displaystyle x}$:

${\displaystyle \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 ${\displaystyle a}$ before, as ${\displaystyle n\to \infty }$, ${\displaystyle 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:

${\displaystyle \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:

${\displaystyle {\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 )}}}}}$

## Theorem

Theorem due to Flajolet and Sedgewick[4].

If ${\displaystyle F(z)}$ is an admissible function then

${\displaystyle [z^{n}]F(z)\sim {\frac {F(\zeta )}{\zeta ^{n}{\sqrt {2\pi b(\zeta )}}}}}$ as ${\displaystyle n\to \infty }$

where ${\displaystyle b(z)=z^{2}{\frac {d^{2}}{dz^{2}}}\ln F(z)+z{\frac {d}{dz}}\ln F(z)}$ and ${\displaystyle \zeta }$ is the solution to the equation ${\displaystyle a(\zeta )=\zeta {\frac {F'(\zeta )}{F(\zeta )}}=n}$.

Definition from Flajolet and Sedgewick[5] and Wilf[6]. Also known as Hayman-admissibility[7].

The function ${\displaystyle F(z)}$ is admissible if:

• ${\displaystyle F(z)}$ is a function with radius of convergence ${\displaystyle R\quad (0
• There exists an ${\displaystyle R_{0} such that ${\displaystyle F(r)>0\quad (R_{0}
• H1: ${\displaystyle \lim _{r\to R}a(r)=+\infty }$ and ${\displaystyle \lim _{r\to R}b(r)=+\infty }$
• H2: There exists a function ${\displaystyle \delta (r)}$ defined for ${\displaystyle R_{0} such that ${\displaystyle 0<\delta (r)<\pi }$ and as ${\displaystyle r\to R}$
${\displaystyle F(re^{i\theta })\sim F(r)e^{i\theta a(r)-{\frac {1}{2}}\theta ^{2}b(r)}}$
uniformly for ${\displaystyle |\theta |\leq \delta (r)}$
• H3: Uniformly for ${\displaystyle \delta (r)\leq |\theta |\leq \pi }$ and as ${\displaystyle r\to R}$
${\displaystyle 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 H3).

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 H2.

## Proof

Proof due to Flajolet and Sedgewick[8]

${\displaystyle [z^{n}]F(z)={\frac {1}{2\pi i}}\int _{C}F(z){\frac {dz}{z^{n+1}}}}$

Converting to polar form ${\displaystyle z=re^{i\theta }}$ so we can apply our admissibility conditions

${\displaystyle {\frac {1}{2\pi i}}\int _{C}F(z){\frac {dz}{z^{n+1}}}={\frac {1}{r^{n}2\pi }}\int _{-\pi }^{\pi }F(re^{i\theta })e^{-ni\theta }d\theta }$

Split the integral into a central approximation crossing the saddle-point and a tail

${\displaystyle \int _{-\pi }^{\pi }F(re^{i\theta })e^{-ni\theta }d\theta =\int _{-\theta _{0}}^{\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta +\int _{\theta _{0}}^{2\pi -\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta }$

By H3

${\displaystyle \int _{\theta _{0}}^{2\pi -\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta <\int _{\theta _{0}}^{2\pi -\theta _{0}}{\frac {F(\zeta )}{\sqrt {b(\zeta )}}}e^{-ni\theta }d\theta \leq 2\pi \zeta {\frac {F(\zeta )}{\sqrt {b(\zeta )}}}}$[9]

therefore

${\displaystyle \int _{\theta _{0}}^{2\pi -\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta =o\left({\frac {F(\zeta )}{\sqrt {b(\zeta )}}}\right)}$

and this allows us to ignore the tail in our estimate.

By H2

${\displaystyle \int _{-\theta _{0}}^{\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta \sim F(\zeta )\int _{-\theta _{0}}^{\theta _{0}}e^{-\theta ^{2}b(\zeta )/2}d\theta }$

because ${\displaystyle a(\zeta )=n}$ by assumption in the theorem.

Changing variables with ${\displaystyle g(x)={\frac {x}{\sqrt {b(\zeta )}}}}$

${\displaystyle \int _{-\theta _{0}}^{\theta _{0}}e^{-\theta ^{2}b(\zeta )/2}d\theta ={\frac {1}{\sqrt {b(\zeta )}}}\int _{-\theta _{0}{\sqrt {b(\zeta )}}}^{\theta _{0}{\sqrt {b(\zeta )}}}e^{-t^{2}/2}dt\sim {\frac {1}{\sqrt {b(\zeta )}}}\int _{-\infty }^{\infty }e^{-t^{2}/2}dt}$[10]

because ${\displaystyle {\sqrt {b(\zeta )}}\to +\infty }$ as ${\displaystyle n\to +\infty }$.

${\displaystyle \int _{-\infty }^{\infty }e^{-t^{2}/2}dt={\sqrt {2\pi }}}$[11]

Putting it all together

${\displaystyle [z^{n}]F(z)={\frac {1}{2\pi i}}\int _{C}F(z){\frac {dz}{z^{n+1}}}={\frac {1}{r^{n}2\pi }}\int _{-\pi }^{\pi }F(re^{i\theta })e^{-ni\theta }d\theta \sim {\frac {1}{\zeta ^{n}2\pi }}\int _{-\theta _{0}}^{\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta \sim {\frac {F(\zeta )}{\zeta ^{n}2\pi }}\int _{-\theta _{0}}^{\theta _{0}}e^{-\theta ^{2}b(\zeta )/2}d\theta \sim {\frac {F(\zeta )}{\zeta ^{n}2\pi {\sqrt {b(\zeta )}}}}\int _{-\infty }^{\infty }e^{-t^{2}/2}dt={\frac {F(\zeta )}{\zeta ^{n}{\sqrt {2\pi b(\zeta )}}}}}$

## Example

Example from Wilf[12] and Flajolet and Sedgewick[13].

Say we want to estimate the coefficients of ${\displaystyle e^{z}}$:

1. ${\displaystyle e^{z}}$ has radius of convergence ${\displaystyle +\infty }$ and is positive for all ${\displaystyle z\geq 0}$.
2. H1: ${\displaystyle a(z)=z{\frac {(e^{z})'}{e^{z}}}=z{\frac {e^{z}}{e^{z}}}=z}$. Therefore, ${\displaystyle \lim _{z\to +\infty }z=+\infty }$.
3. H1: ${\displaystyle 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, ${\displaystyle \lim _{z\to +\infty }z=+\infty }$.
4. Find the saddle-point ${\displaystyle \zeta }$ by solving the equation ${\displaystyle a(\zeta )=\zeta =n}$. Therefore, ${\displaystyle \zeta =n}$ and the path of integration is the circle of radius ${\displaystyle n}$ centered at the origin.
5. Choose ${\displaystyle \delta (ne^{i\theta })=n^{-{\frac {2}{5}}}}$.
6. H3: For ${\displaystyle n^{-{\frac {2}{5}}}\leq |\theta |\leq \pi }$ as ${\displaystyle n\to +\infty }$
${\displaystyle |e^{ne^{i\theta }}|=e^{n\cos \theta }\leq e^{n\cos n^{-{\frac {2}{5}}}}=o\left({\frac {e^{n}}{\sqrt {n}}}\right)}$.
7. H2: For ${\displaystyle 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 ${\displaystyle e^{i\theta }}$).
8. Apply the theorem: ${\displaystyle [z^{n}]e^{z}\sim {\frac {e^{n}}{n^{n}{\sqrt {2\pi n}}}}}$.

## Saddle-points of higher order

Theorem from Flajolet and Sedgewick[14].

If ${\displaystyle F(z)}$ has a saddle-point of order ${\displaystyle p}$:

${\displaystyle [z^{n}]F(z)\sim {\frac {\omega }{p+1}}\Gamma ({\frac {1}{p+1}}){\frac {F(\zeta )}{\zeta ^{(n+1)}{\sqrt[{(p+1)}]{-f^{(p+1)}(\zeta )/(p+1)!}}}}}$

where ${\displaystyle \omega ^{p}=1}$.

## Notes

1. Flajolet and Sedgewick 2009, pp. 553.
2. Flajolet and Sedgewick 2009, pp. 551-554.
3. Flajolet and Sedgewick 2009, pp. 549.
4. Flajolet and Sedgewick 2009, pp. 565.
5. Flajolet and Sedgewick 2009, pp. 565.
6. Wilf 2006, pp. 199.
7. After Walter Hayman.
8. Flajolet and Sedgewick 2009, chapter VIII.
9. Flajolet and Sedgewick 2009, pp. 546-549.
10. This is Laplace's Method. See w:Laplace's_method or Widder 1941, pp. 277.
11. See, for example, w:List_of_integrals_of_exponential_functions#Definite_integrals.
12. Wilf 2006, pp. 198.
13. Flajolet and Sedgewick 2009, pp. 555-557.
14. Flajolet and Sedgewick 2009, pp. 603.

## References

• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
• Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.
• Widder, David Vernon (1941). The Laplace Transform. Princeton University Press.