40.08.06 · combinatorics / analytic-combinatorics-asymptotics

The Saddle-Point Method for Asymptotic Enumeration

shipped3 tiersLean: none

Anchor (Master): Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. VIII in full — the Cauchy-coefficient saddle-point analysis of entire and fast-growing functions, the saddle-point bound and method, Hayman's admissibility theorem and the closure properties of H-admissible functions, the Moser-Wyman analysis of Bell numbers, the involution and central-binomial coefficient examples, and the connection to the circle method (Theorems VIII.1-VIII.8); Hayman 1956 *A generalisation of Stirling's formula* (J. Reine Angew. Math. 196) for the admissibility theorem; de Bruijn 1981 *Asymptotic Methods in Analysis* Ch. 5-6; Moser-Wyman 1955 *An asymptotic formula for the Bell numbers* (Trans. Roy. Soc. Canada 49)

Intuition Beginner

Some counting sequences grow so fast that the usual asymptotic tools fail. The number of ways to pair people up, the number of ways to partition a set into groups, the factorial itself — these all outrun any fixed exponential rate. The generating functions that produce them, like the exponential of $z$ or the exponential of "the exponential of $z$ minus one", have no nearest bad point on the boundary to read the growth from. The previous chapters extracted growth rates from a singularity sitting at a fixed distance from the origin. Here there is no such fixed landmark, so a different idea is needed.

That idea starts from a way of pulling a single count back out of a generating function: a coefficient equals an average of the function around a circle, divided by the radius raised to a power. You get to choose the radius of that circle. Pick it too small and the radius-power in the denominator stays large, which inflates your estimate; pick it too large and the function itself blows up in the numerator. Somewhere in between is a best radius that balances these two opposing effects, and at that radius the estimate is sharpest.

The recipe is therefore: find the radius that balances the growing function against the shrinking radius-power, and read the count off there. The balance point is where a certain "tilt" of the function matches the size you are asking about. As the size grows, the best radius moves, tracking it. This balanced-radius method is the saddle-point method, and it is exactly what is needed for fast-growing, landmark-free sequences.

The everyday picture is a mountain pass. To cross a ridge you do not climb to a peak; you walk through the lowest gap, the pass, where the ground curves up on two sides and down on the other two. The best circle threads the function's integral through such a pass, and almost the entire value of the integral comes from the small stretch right at the gap.

Visual Beginner

Think of extracting a count as walking a loop around the origin and averaging the function as you go, then dividing by the radius raised to the size you want. The one free choice is how big to make the loop. The picture below shows the trade-off that fixes the best size.

The table records the balance and what the method delivers. Each row is a fact you can use without re-deriving it, and the rest of the unit explains why each holds.

idea in words	what it gives you
a count is a loop average of the function divided by the radius-power	an exact formula you may evaluate at any radius
the function grows with radius, the radius-power shrinks the estimate	two opposing effects to balance
the best radius is where the function's "tilt" equals the size $n$	one equation that fixes the circle
at the best radius almost all the loop value sits in a small arc	the estimate becomes a single clean term

Read top to bottom: a count is a loop average, the two effects fight, the best radius settles the fight, and the answer reads off in one term. The worked example below carries this through for the simplest fast-growing function and recovers a famous formula for the factorial.

Worked example Beginner

Let us estimate the number $1/ n!$ that the function $e^{z} = 1 + z + \frac{z ^{2}}{2 !} + \dots$ hangs on its size- $n$ peg, using the balance idea, and watch Stirling's formula for $n!$ fall out. We work the case $n = 5$ to keep numbers concrete, then state what the balance gives in general.

Step 1. The growing part is the function value $e^{r}$ on a circle of radius $r$ ; the shrinking part is $1$ divided by $r^{5}$ (the radius-power for size $5$ ). The estimate to balance is $e^{r}$ divided by $r^{5}$ .

Step 2. Find the best radius. The function's "tilt" for $e^{r}$ is just $r$ itself (the rate at which $ln e^{r} = r$ climbs, times $r$ , is $r$ ). Setting this tilt equal to the size gives $r = 5$ . So the best circle for the size- $5$ peg has radius $5$ .

Step 3. Read off the estimate. Plug $r = 5$ into "function over radius-power": $e^{5}$ divided by $5^{5}$ . That is about $148.4 \div 3125 \approx 0.0475$ .

Step 4. Sharpen with the pass width. The gap at the saddle has a spread measured by the square root of $2 π$ times the size, here $2 π \cdot 5 \approx 5.60$ . Dividing the Step 3 number by this width gives $0.0475 \div 5.60 \approx 0.00848$ .

Step 5. Compare. The true value is $1/5! = 1/120 \approx 0.00833$ . The estimate $0.00848$ is within about two percent.

Step 6. Read it as Stirling. Undoing the division, $n! \approx (n^{n} / e^{n}) 2 π n$ , which for $n = 5$ gives about $118$ against the true $120$ . This is Stirling's formula, and the balance produced it.

What this tells us: choosing the radius to balance growth against the radius-power, then dividing by the pass width, turns one loop average into a sharp count — and on the simplest fast-growing function it reproduces Stirling.

Check your understanding Beginner

Formal definition Intermediate+

Let $f (z) = \sum_{n \geq 0} a_{n} z^{n}$ be a power series with non-negative coefficients and radius of convergence $R \in (0, \infty]$ , analytic in the open disc $∣ z ∣ < R$ . The starting point is Cauchy's coefficient formula: for any $r$ with $0 < r < R$ , $$ a_n = [z^n] f(z) = \frac{1}{2\pi i} \oint_{|z| = r} \frac{f(z)}{z^{n+1}}, dz = \frac{1}{2\pi}\int_{-\pi}^{\pi} \frac{f(re^{i\theta})}{r^n e^{in\theta}}, d\theta, $$ the contour being the circle of radius $r$ , traversed once counterclockwise ^{[Flajolet-Sedgewick §VIII.1]}. The integrand is $g (z) = f (z) z^{- n - 1}$ , whose logarithm is $ln f (z) - (n + 1) ln z$ . The saddle-point method chooses $r$ so that the circle passes through a saddle point of $g$ on the positive real axis.

Definition (saddle point / saddle-point equation). A saddle point of $g (z) = f (z) z^{- n - 1}$ is a zero of $\frac{d}{d z} ln g (z)$ . On the positive real axis the saddle-point equation is $$ \frac{d}{dr}\Big(\ln f(r) - (n+1)\ln r\Big) = 0 \quad\Longleftrightarrow\quad \frac{r f'(r)}{f(r)} = n+1, $$ and for asymptotic purposes one uses the simpler $r f^{'} (r) / f (r) = n$ , defining the saddle radius $r = r_{n}$ . The function $$ \alpha(r) := \frac{r f'(r)}{f(r)} = r,\frac{d}{dr}\ln f(r) $$ is the first log-derivative on the circle (a tilt or mean-value parameter); for $f$ with positive coefficients $α$ increases from $0$ and the equation $α (r_{n}) = n$ has a unique positive root for each large $n$ .

Definition (saddle-point variance). The second log-derivative on the circle is $$ b(r) := r,\frac{d}{dr}\Big(r,\frac{f'(r)}{f(r)}\Big) = r,\alpha'(r) = \frac{d^2}{d\theta^2}\Big[\ln f(re^{i\theta})\Big]{\theta = 0}, $$ the curvature of $ln f (r e^{i θ}) - in θ - n ln r$ along the circle at $θ = 0$ . It is non-negative for the functions treated here and plays the role of a variance: it is the width of the Gaussian into which the integrand collapses near the saddle. The notation $[z^{n}]$ , $α (r)$ , $b (r)$ , $r_{n}$ , and the contour integral $\oint{|z|=r}$ are recorded in _meta/NOTATION.md.

Definition (saddle-point estimate). When the integrand concentrates at $θ = 0$ , the saddle-point estimate is $$ a_n = [z^n] f(z) \sim \frac{f(r_n)}{r_n^{,n},\sqrt{2\pi, b(r_n)}}, \qquad n \to \infty. $$ The numerator $f (r_{n}) / r_{n}^{n} = e^{l n f (r_{n}) - n l n r_{n}}$ is the value of the integrand at the saddle; the factor $(2 π b (r_{n}))^{- 1/2}$ is the Gaussian width of the pass. This is the same Laplace-method reduction that produces Stirling's formula in 06.01.15, here run on the circle rather than the real line.

Counterexamples to common slips Intermediate+

"Singularity analysis and the saddle-point method are interchangeable." They are complementary. Singularity analysis reads the growth of $a_{n}$ off a dominant singularity at a fixed finite radius $ρ$ , giving $a_{n} \sim C ρ^{- n} n^{α - 1}$ . The saddle-point method applies precisely when there is no usable finite singularity: $f$ entire ( $R = \infty$ , as $e^{z}$ , $e^{e^{z} - 1}$ , $e^{z + z^{2} /2}$ ) or with a singularity so violent that the transfer theorems fail. The saddle radius $r_{n}$ then moves with $n$ instead of sitting at a fixed $ρ$ .
"The saddle radius is a constant determined by $f$ ." It is a function of $n$ : $r_{n}$ solves $α (r_{n}) = n$ , so as $n$ grows the best circle expands. For $e^{z}$ , $r_{n} = n$ ; for $e^{z + z^{2} /2}$ , $r_{n} \sim n$ ; for $e^{e^{z} - 1}$ , $r_{n} e^{r_{n}} = n$ gives $r_{n} \sim ln n - ln ln n$ . A fixed-radius reading would miss the growth entirely.
"The saddle-point bound $a_{n} \leq f (r) / r^{n}$ already gives the asymptotic." The bound holds for every $r$ and is one-sided; minimising it over $r$ (which lands at the saddle radius) gives the correct exponential order but overestimates by the Gaussian-width factor $2 π b (r_{n})$ . The bound captures $f (r_{n}) / r_{n}^{n}$ ; the method supplies the missing $(2 π b (r_{n}))^{- 1/2}$ and turns an inequality into an asymptotic equality.
"Any function admits the saddle-point estimate." The Gaussian localisation requires that the contribution away from $θ = 0$ be negligible and that the local expansion be genuinely quadratic. Hayman's admissibility conditions (capture, divergence, width) are a clean sufficient package; a function like $f (z) = e^{z} + e^{- z} \cdot (small)$ with competing saddles on the circle, or one whose coefficients oscillate in sign, can violate the concentration hypothesis and fail the estimate.

Key theorem with proof Intermediate+

The signature theorem is the basic saddle-point estimate for the Cauchy coefficient integral: under concentration at the real saddle, the coefficient is the saddle value of the integrand divided by the Gaussian width. Every worked enumeration in this unit — Stirling, involutions, Bell numbers — is one instance, and the admissibility theory of the next section is the certification that the concentration hypothesis holds ^{[Flajolet-Sedgewick §VIII.2]}.

Theorem (basic saddle-point estimate). Let $f (z) = \sum_{n} a_{n} z^{n}$ have non-negative coefficients and radius of convergence $R \in (0, \infty]$ . Let $r_{n} \in (0, R)$ solve the saddle-point equation $α (r_{n}) = r_{n} f^{'} (r_{n}) / f (r_{n}) = n$ , with $b_{n} = b (r_{n}) = r_{n} α^{'} (r_{n}) \to \infty$ . Suppose the integrand concentrates: for a suitable angular range $∣ θ ∣ \leq θ_{0} (n)$ with $θ_{0} \to 0$ and $b_{n} θ_{0}^{2} \to \infty$ ,

(central regime) $ln f (r_{n} e^{i θ}) = ln f (r_{n}) + in θ - \frac{1}{2} b_{n} θ^{2} + o (1)$ uniformly for $∣ θ ∣ \leq θ_{0}$ , and
(tail negligibility) $\int_{θ_{0} \leq ∣ θ ∣ \leq π} ∣ f (r_{n} e^{i θ}) ∣ d θ = o (f (r_{n}) θ_{0})$ ,

then $$ a_n \sim \frac{f(r_n)}{r_n^{,n},\sqrt{2\pi, b_n}}, \qquad n \to \infty. $$

Proof. Apply Cauchy's formula on the saddle circle $∣ z ∣ = r_{n}$ : $$ a_n = \frac{1}{2\pi}\int_{-\pi}^{\pi} \frac{f(r_n e^{i\theta})}{r_n^{,n}, e^{i n \theta}}, d\theta = \frac{f(r_n)}{2\pi, r_n^{,n}}\int_{-\pi}^{\pi} \exp!\Big(\ln f(r_n e^{i\theta}) - \ln f(r_n) - i n\theta\Big), d\theta. $$ Split the integral at $\pm θ_{0}$ . On the central range $∣ θ ∣ \leq θ_{0}$ , hypothesis (1) gives the exponent $- \frac{1}{2} b_{n} θ^{2} + o (1)$ , the linear term $in θ$ having cancelled against the saddle choice $α (r_{n}) = n$ (which is exactly the vanishing of the first-order term in $θ$ : $\frac{d}{d θ} [ln f (r_{n} e^{i θ})]_{θ = 0} = i α (r_{n}) = in$ ). Hence the central contribution is $$ \frac{f(r_n)}{2\pi, r_n^{,n}}\int_{-\theta_0}^{\theta_0} e^{-\frac{1}{2}b_n\theta^2},(1 + o(1)), d\theta. $$ Substitute $u = θ b_{n}$ . Because $b_{n} θ_{0}^{2} \to \infty$ , the limits $\pm θ_{0} b_{n}$ tend to $\pm \infty$ , so $\int_{- θ_{0}}^{θ_{0}} e^{- \frac{1}{2} b_{n} θ^{2}} d θ = b_{n}^{- 1/2} \int_{- θ_{0} b_{n}}^{θ_{0} b_{n}} e^{- u^{2} /2} d u \to b_{n}^{- 1/2} 2 π$ , the standard Gaussian integral ^{[de Bruijn Ch. 5]}. The central contribution is therefore $$ \frac{f(r_n)}{2\pi, r_n^{,n}}\cdot \frac{\sqrt{2\pi}}{\sqrt{b_n}}(1 + o(1)) = \frac{f(r_n)}{r_n^{,n}\sqrt{2\pi, b_n}}(1 + o(1)). $$ By hypothesis (2) the tail $θ_{0} \leq ∣ θ ∣ \leq π$ contributes $o (f (r_{n}) θ_{0} / r_{n}^{n})$ , which is $o (f (r_{n}) (r_{n}^{n} 2 π b_{n})^{- 1})$ since $θ_{0} b_{n} \to \infty$ forces $θ_{0} ≫ b_{n}^{- 1/2}$ , making the tail subdominant to the central term. Summing the two ranges gives $a_{n} \sim f (r_{n}) / (r_{n}^{n} 2 π b_{n})$ . $□$

Corollary (Stirling from $e^{z}$ ). For $f (z) = e^{z}$ one has $α (r) = r$ , so $r_{n} = n$ , and $b (r) = r$ , so $b_{n} = n$ . The estimate reads $[z^{n}] e^{z} = 1/ n! \sim e^{n} / (n^{n} 2 π n)$ , i.e. $n! \sim n^{n} e^{- n} 2 π n$ , Stirling's formula. This is the same conclusion derived by the Laplace method on the real Gamma integral in 06.01.15; here it is the circle-method shadow of that real-line computation.

Bridge. This estimate builds toward every fast-growth enumeration in the chapter and appears again in 40.08.07, where the same Gaussian localisation, now carried out with a secondary variable marking a parameter, produces quasi-power limit laws. The foundational reason the method works is that taking logarithms turns the product $f (z) z^{- n - 1}$ into a sum whose real part has a strict maximum on the saddle circle exactly at $θ = 0$ , so the integral is a Laplace integral on the circle; this is exactly the steepest-descent picture of 06.01.15 transported from the real axis to the contour, and it generalises Stirling's single computation into a uniform machine. The saddle radius moving with $n$ is dual to the fixed dominant singularity of singularity analysis: putting these together, a fixed singularity gives $ρ^{- n} n^{α - 1}$ growth while a moving saddle gives the faster-than-exponential growth of entire generating functions, and the central insight is that both are one Cauchy integral read at the location where the integrand peaks.

Exercises Intermediate+

Exercise 7 (hard, symbolic).

Verify Hayman's closure rule that $e^{P (z)}$ is admissible for $P (z) = z + z^{2} /2$ (the involution case) by checking that $b_{n} = r_{n} α^{'} (r_{n}) \to \infty$ and that the angular width $θ_{0} (n) = b_{n}^{- 2/5}$ satisfies both $b_{n} θ_{0}^{2} \to \infty$ and $θ_{0} \to 0$ .

Hint

From Exercise 3, $b_{n} \sim 2 n$ . Check the two limits for $θ_{0} = b_{n}^{- 2/5}$ .

Answer

From Exercise 3, $α (r) = r + r^{2}$ and $b (r) = r + 2 r^{2}$ , so $b_{n} \sim 2 n \to \infty$ , the divergence condition. Take $θ_{0} = b_{n}^{- 2/5} \sim (2 n)^{- 2/5} \to 0$ (width condition: the central arc shrinks). Then $b_{n} θ_{0}^{2} = b_{n} \cdot b_{n}^{- 4/5} = b_{n}^{1/5} \sim (2 n)^{1/5} \to \infty$ (capture condition: the Gaussian scale $b_{n}^{- 1/2}$ is far inside the arc, since $θ_{0} = b_{n}^{- 2/5} ≫ b_{n}^{- 1/2}$ ). With $∣ θ ∣ \leq θ_{0}$ the cubic remainder in $ln f (r_{n} e^{i θ})$ is $O (b_{n} θ_{0}^{3}) = O (b_{n}^{- 1/5}) \to 0$ , so the quadratic approximation of Theorem hypothesis (1) holds; the monotone decay of $∣ f (r e^{i θ}) ∣ = e^{r c o s θ + \frac{r ^{2}}{2} c o s 2 θ}$ away from $θ = 0$ gives the tail bound (2). Hence the saddle-point estimate is valid, certifying $e^{z + z^{2} /2}$ as H-admissible. Rubric: full credit for $b_{n} \to \infty$ , $θ_{0} \to 0$ , $b_{n} θ_{0}^{2} \to \infty$ , and the cubic-remainder control.

Exercise 8 (hard, symbolic).

The partition function $p (n) = [z^{n}] \prod_{k \geq 1} (1 - z^{k})^{- 1}$ has a generating function with a singularity at $z = 1$ on the unit circle. Show that the real saddle radius $r_{n} < 1$ solves a transcendental equation, and explain why this heuristic saddle gives the correct exponential rate $e^{π 2 n /3}$ but must be made rigorous by the circle method 21.16.02.

Hint

Use $ln f (r) = \sum_{k \geq 1} ln \frac{1}{1 - r ^{k}}$ and the approximation $ln f (r) \approx \frac{π ^{2}}{6} \frac{r}{1 - r}$ as $r \to 1^{-}$ (the Euler-Maclaurin / dilogarithm estimate). Set $α (r) = n$ .

Answer

As $r \to 1^{-}$ , $ln f (r) = \sum_{k} ln \frac{1}{1 - r ^{k}} \sim \frac{1}{1 - r} \cdot \frac{π ^{2}}{6}$ (Euler-Maclaurin: $\sum_{k} ln \frac{1}{1 - r ^{k}} \approx \frac{1}{∣ l n r ∣} \int_{0}^{\infty} ln \frac{1}{1 - e ^{- t}} d t = \frac{π ^{2} /6}{∣ l n r ∣} \sim \frac{π ^{2} /6}{1 - r}$ ). Then $α (r) = r \frac{d}{d r} ln f (r) \sim \frac{π ^{2} /6}{( 1 - r ) ^{2}}$ , and $α (r_{n}) = n$ gives $1 - r_{n} \sim \frac{π}{6 n}$ , a real saddle approaching $1$ . Substituting back, $ln f (r_{n}) - n ln r_{n} \sim \frac{π ^{2} /6}{1 - r _{n}} + n (1 - r_{n}) \sim 2 \cdot \frac{π ^{2} /6}{1 - r _{n}} = π 2 n /3$ , recovering the Hardy-Ramanujan exponential rate $p (n) \approx e^{π 2 n /3}$ . The heuristic is not rigorous because the singularity at $z = 1$ is one of infinitely many on the unit circle (at each root of unity), and the contributions of the other arcs — negligible to leading order but essential for the full Rademacher expansion — are controlled only by the modular transformation of the Dedekind eta function in the circle method of 21.16.02. Rubric: full credit for the dilogarithm estimate of $ln f$ , the saddle $1 - r_{n} \sim π / 6 n$ , the exponential rate $π 2 n /3$ , and the explanation that the other roots of unity require the circle method.

Advanced results Master

The basic estimate is the analytic kernel; its systematic deployment rests on the saddle-point bound as a one-sided estimate, Hayman's admissibility theorem certifying the concentration hypothesis once and for all, the closure calculus of H-admissible functions, and the canonical Moser-Wyman analysis of the Bell numbers as the worked frontier case.

Theorem 1 (saddle-point bound). For $f (z) = \sum_{n} a_{n} z^{n}$ with non-negative coefficients and radius of convergence $R$ , and every $0 < r < R$ , $$ a_n \le \frac{f(r)}{r^{n}}, \qquad\text{minimised at } r = r_n \text{ where } \alpha(r_n) = n, $$ giving $a_{n} \leq f (r_{n}) / r_{n}^{n} = exp (in f_{0 < r < R} [ln f (r) - n ln r])$ . The bound is immediate from $a_{n} r^{n} \leq \sum_{m} a_{m} r^{m} = f (r)$ (all terms non-negative), and it is sharp on the exponential scale: the true coefficient is smaller only by the polynomial Gaussian-width factor $2 π b_{n}$ ^{[Flajolet-Sedgewick §VIII.1]}. The bound alone fixes the exponential growth rate $lim sup_{n} a_{n}^{1/ n}$ and is the workhorse for upper estimates where the full asymptotic is not needed.

Theorem 2 (Hayman's admissibility theorem). Call $f$ analytic in $∣ z ∣ < R$ with positive Taylor coefficients H-admissible if, writing $a (r) = r f^{'} (r) / f (r)$ and $b (r) = r a^{'} (r)$ , there is a function $θ_{0} : (0, R) \to (0, π)$ such that, as $r \to R^{-}$ :

(capture) $b (r) \to \infty$ ;
(central / divergence) $f (r e^{i θ}) \sim f (r) e^{i θ a (r) - \frac{1}{2} θ^{2} b (r)}$ uniformly for $∣ θ ∣ \leq θ_{0} (r)$ ;
(width / negligibility) $f (r e^{i θ}) = o (f (r) / b (r))$ uniformly for $θ_{0} (r) \leq ∣ θ ∣ \leq π$ .

Then for $n \to \infty$ the saddle-point estimate holds in its sharp form: $$ a_n = [z^n]f(z) \sim \frac{f(r_n)}{r_n^{,n}\sqrt{2\pi, b(r_n)}}, \qquad \alpha(r_n) = n. $$ The three conditions are exactly the hypotheses of the Key theorem made into properties of $f$ alone, so that admissibility is checked once and the asymptotic follows for every $n$ ^{[Hayman 1956]}. Hayman proved this as a generalisation of Stirling's formula, the case $f = e^{z}$ being the prototype.

Theorem 3 (H-admissible function calculus). The class of H-admissible functions is closed under the following operations ^{[Flajolet-Sedgewick §VIII.4]}: if $f, g$ are H-admissible and $P$ is a polynomial with real coefficients and positive leading coefficient, then (i) $e^{f}$ is H-admissible; (ii) $f \cdot g$ is H-admissible; (iii) $f + P$ and $P \cdot f$ are H-admissible; (iv) $e^{P}$ is H-admissible whenever $\sum_{k} (Re c_{k}) > 0$ ensures positive coefficients, in particular $e^{P (z)}$ for $P$ with non-negative coefficients and $de g P \geq 1$ ; (v) if $f$ is H-admissible and $g$ has positive coefficients with $g = o (f)$ in the relevant sense, then $f + g$ is H-admissible. The rules certify $e^{z}$ , $e^{z + z^{2} /2}$ (involutions), $e^{e^{z} - 1}$ (Bell numbers), $e^{z / (1 - z)}$ (fragmented permutations from 40.08.02), and more, by composition rather than by re-checking the contour integral. The closure under $f \mapsto e^{f}$ is the engine: each application of $exp$ to an admissible exponent stays admissible, which is why "exponential of a generating function" — the SET construction of 40.08.02 — is the natural saddle-point input.

Theorem 4 (Moser-Wyman asymptotics for Bell numbers). The Bell numbers $B_{n} = n! [z^{n}] e^{e^{z} - 1}$ satisfy $$ B_n \sim \frac{n!; e^{e^{r_n} - 1}}{r_n^{,n}\sqrt{2\pi, b_n}}, \qquad r_n e^{r_n} = n, \quad b_n = r_n(1 + r_n)e^{r_n} = n(1 + r_n), $$ with $r_{n} = W (n) = ln n - ln ln n + o (1)$ the Lambert-W value; equivalently $B_{n} \sim \frac{1}{n} λ (n)^{n + 1/2} e^{λ (n) - n - 1}$ in the Moser-Wyman variable $λ (n) = e^{r_{n}} = n / r_{n}$ ^{[Moser-Wyman 1955]}. The function $e^{e^{z} - 1}$ is entire, H-admissible by Theorem 3 (it is $e^{f}$ with $f = e^{z} - 1$ admissible), and the saddle is the doubly-exponential balance point $r e^{r} = n$ rather than the linear $r = n$ of $e^{z}$ ; the Lambert-W saddle is the signature of a doubly-exponential generating function. The same analysis with $e^{z} - 1$ replaced by $\frac{1}{2} (e^{2 z} - 1) + \dots$ handles the $r$ -associated Bell and Stirling families.

Theorem 5 (saddle-point asymptotics versus singularity analysis: the boundary). Let $f$ be entire of finite order $ρ$ and lower order equal to its order (regular growth). Then $[z^{n}] f$ admits a saddle-point asymptotic, with saddle radius $r_{n}$ determined by $α (r_{n}) = n$ , and $r_{n} \to \infty$ . By contrast, if $f$ has a finite dominant singularity at $ρ < \infty$ of an integrable-singularity type, $[z^{n}] f$ is governed by singularity analysis with $r_{n} \to ρ$ fixed. The two regimes meet at functions with a finite singularity of exponential type (an essential singularity on the boundary, as $e^{1/ (1 - z)}$ or the partition product near $z = 1$ ): there the relevant saddle approaches the boundary singularity, $r_{n} \to ρ^{-}$ , and the analysis is a boundary saddle-point method, the analytic precursor of the circle method of 21.16.02 ^{[Flajolet-Sedgewick §VIII.5]}. The classification by where $r_{n}$ goes — to $\infty$ , to a fixed $ρ$ , or to a boundary singularity — organises the whole asymptotic landscape of the chapter.

Synthesis. The saddle-point method is the foundational reason that entire and fast-growing generating functions are not beyond asymptotic reach: where singularity analysis reads growth off a fixed singularity, the saddle-point method reads it off a moving circle whose radius $r_{n}$ is pinned by the balance $α (r_{n}) = n$ between the function and the radius-power, and at that radius the Cauchy integral collapses to a Gaussian of width $2 π b_{n}$ . The central insight is that taking the logarithm of the integrand $f (z) z^{- n - 1}$ converts a product into a sum with a strict real-part maximum on the saddle circle, so the contour integral is a Laplace integral on the circle — exactly the steepest-descent computation that gives Stirling in 06.01.15, now run as a uniform machine. This is dual to singularity analysis construction by construction: a fixed singularity gives $ρ^{- n} n^{α - 1}$ , a moving saddle gives faster-than-exponential growth, and putting these together with Theorem 5 shows the two are one Cauchy integral classified by where its saddle goes — to infinity (entire $f$ ), to a fixed $ρ$ (polar/algebraic $f$ ), or to a boundary essential singularity (the circle-method regime of 21.16.02).

The bridge to enumeration is that Hayman's admissibility makes the concentration hypothesis a property of $f$ closed under $exp$ , sums, and products, so the SET-construction outputs of 40.08.02 — $e^{e^{z} - 1}$ for Bell numbers, $e^{z + z^{2} /2}$ for involutions, $e^{z / (1 - z)}$ for fragmented permutations — are admissible by the calculus and surrender their asymptotics to one formula. This appears again in the quasi-power limit laws of 40.08.07, where the same saddle, perturbed by a marking variable, yields Gaussian fluctuations of combinatorial parameters; the construction calculus, the singularity calculus, and the saddle-point calculus are one analytic combinatorics read at three resolutions.

Full proof set Master

Proposition 1 (Cauchy coefficient formula and saddle-point bound). For $f (z) = \sum_{n} a_{n} z^{n}$ analytic in $∣ z ∣ < R$ with $a_{n} \geq 0$ , and any $0 < r < R$ : $a_{n} = \frac{1}{2 π} \int_{- π}^{π} f (r e^{i θ}) r^{- n} e^{- in θ} d θ$ , and $a_{n} \leq f (r) r^{- n}$ .

Proof. Analyticity in $∣ z ∣ < R$ gives the uniformly convergent series $f (r e^{i θ}) = \sum_{m} a_{m} r^{m} e^{im θ}$ on the circle. Multiply by $r^{- n} e^{- in θ}$ and integrate over $[- π, π]$ ; by orthogonality $\frac{1}{2 π} \int_{- π}^{π} e^{i (m - n) θ} d θ = δ_{mn}$ , term-by-term integration (justified by uniform convergence) leaves only $m = n$ , yielding $\frac{1}{2 π} \int_{- π}^{π} f (r e^{i θ}) r^{- n} e^{- in θ} d θ = a_{n}$ . For the bound, $a_{n} r^{n} = ∣ a_{n} r^{n} ∣ \leq \sum_{m} a_{m} r^{m} = f (r)$ since all $a_{m} r^{m} \geq 0$ ; divide by $r^{n}$ . $□$

Proposition 2 (uniqueness and monotonicity of the saddle radius). If $f$ has positive coefficients $a_{n} > 0$ for all $n$ in an unbounded set and $R \in (0, \infty]$ , then $α (r) = r f^{'} (r) / f (r)$ is strictly increasing on $(0, R)$ with $α (0^{+}) = ord (f) \geq 0$ and $α (R^{-}) = + \infty$ ; hence for each sufficiently large $n$ the equation $α (r) = n$ has a unique root $r_{n}$ , and $r_{n}$ increases to $R$ as $n \to \infty$ .

Proof. Write $α (r) = \frac{\sum _{m} m a _{m} r ^{m}}{\sum _{m} a _{m} r ^{m}}$ , the mean of $m$ under the probability weights $w_{m} (r) = a_{m} r^{m} / f (r)$ . Its derivative is $α^{'} (r) = \frac{1}{r} Var_{w (r)} (m) = \frac{b ( r )}{r}$ , the variance of $m$ under $w (r)$ divided by $r$ ; since $f$ has at least two distinct exponents with positive coefficients, the variance is strictly positive, so $α^{'} > 0$ and $α$ is strictly increasing. As $r \to R^{-}$ the weights $w_{m} (r)$ shift mass to arbitrarily large $m$ (the radius of convergence being $R$ ), so $α (r) = E_{w (r)} [m] \to \infty$ . As $r \to 0^{+}$ , $α (r) \to ord (f)$ , the least exponent. By the intermediate value theorem and strict monotonicity, $α (r) = n$ has the unique root $r_{n}$ for $n > ord (f)$ , and monotonicity of $α^{- 1}$ gives $r_{n} ↑ R$ . $□$

Proposition 3 (Gaussian localisation; the basic estimate). Under the hypotheses of the Key theorem (central quadratic expansion and tail negligibility at the saddle radius $r_{n}$ with $b_{n} \to \infty$ ), $a_{n} \sim f (r_{n}) / (r_{n}^{n} 2 π b_{n})$ .

Proof. This is the Key theorem; we record the localisation cleanly. By Proposition 1, $a_{n} = \frac{f ( r _{n} )}{2 π r _{n}^{n}} \int_{- π}^{π} exp (h_{n} (θ)) d θ$ with $h_{n} (θ) = ln f (r_{n} e^{i θ}) - ln f (r_{n}) - in θ$ . At the saddle, $h_{n} (0) = 0$ and $h_{n}^{'} (0) = i (α (r_{n}) - n) = 0$ , while $h_{n}^{''} (0) = - b_{n}$ (the second log-derivative on the circle, real and negative). Thus $Re h_{n} (θ) = - \frac{1}{2} b_{n} θ^{2} + O (b_{n} θ^{3})$ near $0$ . Over $∣ θ ∣ \leq θ_{0}$ with $b_{n} θ_{0}^{3} \to 0$ and $b_{n} θ_{0}^{2} \to \infty$ , $exp (h_{n} (θ)) = exp (- \frac{1}{2} b_{n} θ^{2}) (1 + o (1))$ , and $\int_{∣ θ ∣ \leq θ_{0}} exp (- \frac{1}{2} b_{n} θ^{2}) d θ \to 2 π / b_{n}$ by the substitution $u = θ b_{n}$ and dominated convergence against $e^{- u^{2} /2}$ . Over $θ_{0} \leq ∣ θ ∣ \leq π$ , tail negligibility gives a contribution $o (2 π / b_{n})$ . Hence $\int_{- π}^{π} e^{h_{n} (θ)} d θ \sim 2 π / b_{n}$ and $a_{n} \sim \frac{f ( r _{n} )}{2 π r _{n}^{n}} 2 π / b_{n} = \frac{f ( r _{n} )}{r _{n}^{n} 2 π b _{n}}$ . $□$

Proposition 4 (Stirling, involutions, Bell numbers from the estimate). The estimate yields $n! \sim n^{n} e^{- n} 2 π n$ ; $I_{n} \sim \frac{1}{2} n^{n /2} e^{- n /2 + n - 1/4}$ for involution numbers; and $B_{n} \sim n! e^{e^{r_{n}} - 1} / (r_{n}^{n} 2 π n (1 + r_{n}))$ with $r_{n} e^{r_{n}} = n$ for Bell numbers.

Proof. For $f = e^{z}$ : $α (r) = r$ , $r_{n} = n$ ; $b (r) = r$ , $b_{n} = n$ . The estimate gives $[z^{n}] e^{z} = 1/ n! \sim e^{n} / (n^{n} 2 π n)$ , i.e. $n! \sim n^{n} e^{- n} 2 π n$ , agreeing with the Laplace-method derivation of 06.01.15. For $f = e^{z + z^{2} /2}$ : $α (r) = r + r^{2}$ , so $r_{n} = n - \frac{1}{2} + O (n^{- 1/2})$ ; $b (r) = r + 2 r^{2}$ , $b_{n} \sim 2 n$ . Then $f (r_{n}) = e^{r_{n} + r_{n}^{2} /2}$ and $r_{n}^{- n} = e^{- n l n r_{n}}$ ; substituting $r_{n}^{2} = n - r_{n}$ and $ln r_{n} = \frac{1}{2} ln n + O (n^{- 1/2})$ collects the exponent to $- \frac{n}{2} ln n + \frac{n}{2} + n + O (1)$ , and $I_{n} = n! [z^{n}] f \sim \frac{n ! e ^{r_{n} + r_{n}^{2} /2}}{r _{n}^{n} 4 π n}$ reduces, via Stirling for $n!$ , to $\frac{1}{2} n^{n /2} e^{- n /2 + n - 1/4}$ . For $f = e^{e^{z} - 1}$ : $α (r) = r e^{r}$ , $r_{n} = W (n)$ ; $b (r) = r e^{r} (1 + r) = n (1 + r_{n})$ ; the estimate is the displayed $B_{n}$ asymptotic. Each is admissible by Theorem 3, so Proposition 3 applies. $□$

Proposition 5 (admissibility of $e^{z}$ ). The function $f (z) = e^{z}$ is H-admissible, with the saddle-point estimate giving Stirling's formula.

Proof. Here $a (r) = r$ , $b (r) = r \to \infty$ as $r \to \infty$ , so capture holds. For the central condition take $θ_{0} (r) = r^{- 2/5}$ : then $f (r e^{i θ}) = exp (r e^{i θ}) = exp (r cos θ + i r sin θ)$ , and for $∣ θ ∣ \leq θ_{0}$ , $r cos θ = r - \frac{r θ ^{2}}{2} + O (r θ^{4})$ with $r θ^{4} = O (r^{- 3/5}) \to 0$ , and $r sin θ = r θ + O (r θ^{3})$ with $r θ^{3} = O (r^{- 1/5}) \to 0$ , so $f (r e^{i θ}) = f (r) e^{i θ r - \frac{1}{2} θ^{2} r} (1 + o (1))$ , matching $a (r) = b (r) = r$ . For width: on $θ_{0} \leq ∣ θ ∣ \leq π$ , $∣ f (r e^{i θ}) ∣ = e^{r c o s θ} \leq e^{r c o s θ_{0}} = e^{r - \frac{r θ _{0}^{2}}{2} (1 + o (1))} = f (r) e^{- \frac{1}{2} r^{1/5} (1 + o (1))}$ , which is $o (f (r) / r) = o (f (r) / b (r))$ since $r^{1/5} ≫ ln r$ . All three conditions hold, so $e^{z}$ is H-admissible; the estimate then reads $1/ n! \sim e^{n} / (n^{n} 2 π n)$ , Stirling. $□$

Connections Master

The generating functions this unit extracts are exactly the labelled SET-construction outputs of 40.08.02: the Bell-number EGF $e^{e^{z} - 1}$ (sets of nonempty blocks), the involution EGF $e^{z + z^{2} /2}$ (sets of $1$ - and $2$ -cycles), and the fragmented-permutation EGF $e^{z / (1 - z)}$ (sets of nonempty sequences). That unit produces these functions exactly by the symbolic method; this unit reads their large- $n$ coefficient asymptotics off a moving saddle, and the H-admissibility closure under $exp$ is precisely why "exponential of an admissible exponent" — the SET construction — is the canonical saddle-point input.
The Laplace-method derivation of Stirling's formula in 06.01.15 is the real-line prototype of this unit's circle computation: there the integral $Γ (z + 1) = \int_{0}^{\infty} e^{z l n t - t} d t$ is localised at its real maximum $t = z$ and reduced to a Gaussian; here the Cauchy integral on the saddle circle is localised at $θ = 0$ and reduced to the same Gaussian. The $e^{z}$ base case of the saddle-point method is Stirling, and that unit's Stirling asymptotic and Gamma function supply the $n!$ normalisation converting EGF coefficients to counts throughout this unit.
The partition-function heuristic of Exercise 8 — a real saddle $r_{n} \to 1^{-}$ giving the exponential rate $e^{π 2 n /3}$ — is made rigorous by the Hardy-Ramanujan-Rademacher circle method of 21.16.02: where the saddle-point method uses the single dominant saddle near $z = 1$ , the circle method partitions the unit circle into Farey arcs around every root of unity and sums the modular-transformed contributions, yielding the full convergent Rademacher series. The boundary saddle-point regime of Theorem 5 (where $r_{n} \to ρ$ , an essential singularity on the circle of convergence) is the analytic bridge between the two methods.
The perturbed saddle, where a secondary variable $u$ marks a combinatorial parameter and the saddle-point analysis is carried out for $f (z, u)$ , produces the quasi-power limit laws and Gaussian fluctuations developed in the co-produced 40.08.07; this unit fixes the one-variable saddle machinery and the H-admissibility calculus that 40.08.07 perturbs to obtain central limit theorems for parameters such as the number of blocks of a random set partition or the number of fixed points of a random involution.

Historical & philosophical context Master

The saddle-point method descends from the method of steepest descent, introduced by Riemann in unpublished work on hypergeometric functions and developed in print by Debye (1909) for the asymptotics of Bessel functions of large order ^{[Flajolet-Sedgewick §VIII]}. The idea of deforming a contour through a zero of the derivative of the exponent, along the path where the imaginary part of the exponent is constant so that the modulus decreases as fast as possible, gives the real Laplace integral its complex-analytic generalisation; Laplace's own method for real integrals (eighteenth century, in the asymptotics of factorials and probability integrals) is the real-axis special case. The application to coefficient extraction — combining steepest descent with Cauchy's formula on a circle whose radius is tuned to the coefficient index — became the standard tool for entire and fast-growing generating functions.

The decisive enumerative results are Moser and Wyman's 1955 asymptotic formula for the Bell numbers ^{[Moser-Wyman 1955]}, which fixed the saddle at the Lambert-W point $r e^{r} = n$ and computed the full asymptotic of set-partition counts, and Walter Hayman's 1956 A generalisation of Stirling's formula ^{[Hayman 1956]}, which isolated the three conditions — capture, central convergence, and width — under which the saddle-point estimate holds, and proved the closure of the admissible class under exponentiation, sums, and products. Hayman's admissibility turned the method from a case-by-case contour computation into a calculus: a function built from $z$ by $exp$ , polynomial multiplication, and addition is admissible without re-examination of the integral, and its coefficients obey $a_{n} \sim f (r_{n}) / (r_{n}^{n} 2 π b_{n})$ at once. The codification within analytic combinatorics, with the saddle-point bound, the basic method, the admissibility theory, and the boundary-regime classification linking to the circle method, is due to Flajolet and Sedgewick, whose Analytic Combinatorics (2009) Chapter VIII is the reference treatment on which the asymptotic readings of 40.08.02 rest; de Bruijn's Asymptotic Methods in Analysis (1958) remains the canonical exposition of the underlying steepest-descent technique.

Bibliography Master

@book{flajoletsedgewick2009,
  author    = {Flajolet, Philippe and Sedgewick, Robert},
  title     = {Analytic Combinatorics},
  publisher = {Cambridge University Press},
  year      = {2009}
}

@book{debruijn1981asymptotic,
  author    = {de Bruijn, N. G.},
  title     = {Asymptotic Methods in Analysis},
  publisher = {Dover Publications},
  year      = {1981},
  note      = {Corrected reprint of the 1958 North-Holland edition}
}

@article{hayman1956generalisation,
  author  = {Hayman, W. K.},
  title   = {A generalisation of {S}tirling's formula},
  journal = {Journal f\"{u}r die reine und angewandte Mathematik},
  volume  = {196},
  year    = {1956},
  pages   = {67--95}
}

@article{moserwyman1955bell,
  author  = {Moser, Leo and Wyman, Max},
  title   = {An asymptotic formula for the {B}ell numbers},
  journal = {Transactions of the Royal Society of Canada, Section III},
  volume  = {49},
  year    = {1955},
  pages   = {49--54}
}

@article{debye1909asymptotische,
  author  = {Debye, Peter},
  title   = {N\"{a}herungsformeln f\"{u}r die Zylinderfunktionen f\"{u}r gro\ss{}e Werte des Arguments und unbeschr\"{a}nkt ver\"{a}nderliche Werte des Index},
  journal = {Mathematische Annalen},
  volume  = {67},
  year    = {1909},
  pages   = {535--558}
}

@book{wilf2006gfology,
  author    = {Wilf, Herbert S.},
  title     = {generatingfunctionology},
  edition   = {3},
  publisher = {A K Peters},
  year      = {2006}
}

Prerequisites

40.08.02

Tier anchors

beginner: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. VIII read for the picture-first 'best radius' story — the Cauchy-coefficient circle, the competition between a growing numerator and a shrinking denominator, and the involutions/Bell-number examples; Wilf 2006 *generatingfunctionology* 3e (A K Peters) Ch. 5 for the by-hand saddle-point estimate of a single coefficient
intermediate: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) §VIII.1-VIII.4 (the saddle-point bound, the basic saddle-point method, the saddle-point algorithm, Hayman-admissibility and the H-admissible function calculus); de Bruijn 1981 *Asymptotic Methods in Analysis* (Dover) Ch. 5-6 (the saddle-point method for real and complex integrals); Wilf 2006 *generatingfunctionology* 3e Ch. 5
master: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. VIII in full — the Cauchy-coefficient saddle-point analysis of entire and fast-growing functions, the saddle-point bound and method, Hayman's admissibility theorem and the closure properties of H-admissible functions, the Moser-Wyman analysis of Bell numbers, the involution and central-binomial coefficient examples, and the connection to the circle method (Theorems VIII.1-VIII.8); Hayman 1956 *A generalisation of Stirling's formula* (J. Reine Angew. Math. 196) for the admissibility theorem; de Bruijn 1981 *Asymptotic Methods in Analysis* Ch. 5-6; Moser-Wyman 1955 *An asymptotic formula for the Bell numbers* (Trans. Roy. Soc. Canada 49)

References

Flajolet, P. & Sedgewick, R. — Analytic Combinatorics · Cambridge University Press (2009), Chapter VIII 'Saddle-Point Asymptotics'. §VIII.1 starts from the Cauchy coefficient formula $[z^n]f(z) = \frac{1}{2\pi i}\oint f(z)\,z^{-n-1}\,dz$ and the saddle-point bound $[z^n]f(z) \le f(r)\,r^{-n}$ valid for every $r$ in the disc of convergence (the modulus bound on the circle $|z|=r$), minimised at the radius $r$ solving $r f'(r)/f(r) = n$. §VIII.2 develops the basic saddle-point method: choosing $r$ to pass the contour through the saddle of the integrand $f(z)z^{-n-1}$, where $\frac{d}{dz}[\ln f(z) - (n+1)\ln z] = 0$, expanding $\ln(f(z)z^{-n-1})$ to second order on the circle, recognising the local Gaussian integral, and obtaining $[z^n]f(z) \sim \frac{f(r)}{r^n\sqrt{2\pi b(r)}}$ with $b(r) = r\frac{d}{dr}\big(r\frac{f'(r)}{f(r)}\big)$ the second log-derivative of the integrand on the circle. §VIII.3-VIII.4 give Hayman's admissibility theorem (a sufficient condition — the capture, divergence, and width conditions — under which the saddle-point estimate holds) and the H-admissible function calculus (if $f,g$ are H-admissible then $e^f$, $f+g$ with one admissible, $fg$, $e^{f}$, and $f$ times a polynomial with positive leading coefficient are H-admissible; $e^{P(z)}$ for a polynomial $P$ with the right sign pattern is H-admissible). Worked examples: $e^z$ recovering $1/n! \sim e^n/(n^n\sqrt{2\pi n})$ (Stirling), the involution numbers $I_n$ from $e^{z+z^2/2}$ with saddle $r \sim \sqrt{n}$, the Bell numbers $B_n$ from $e^{e^z-1}$ with the Moser-Wyman saddle $r e^r = n$ (the Lambert-W point), the central binomial coefficient $\binom{2n}{n}$ from $(1+z)^{2n}$, and the partition function $p(n)$ from $\prod(1-z^k)^{-1}$ as a heuristic pointing to the rigorous circle method. The saddle-point method is the complement of singularity analysis (Ch. IV-VI): it applies precisely when the generating function is entire or has a singularity too 'violent' or too distant for singularity analysis, so that the growth is read from a saddle on a circle whose radius depends on $n$.
de Bruijn, N. G. — Asymptotic Methods in Analysis · Dover (1981, corrected reprint of the 1958 North-Holland edition), Chapters 4-6. Ch. 4 treats the Laplace method for real integrals $\int e^{N\phi(t)}\,dt$, localising near the maximum of $\phi$ and reducing to a Gaussian. Ch. 5 develops the saddle-point method (method of steepest descent) for contour integrals $\int e^{w(z)}\,dz$: deform the contour through a zero of $w'(z)$ (the saddle point) along the path of steepest descent where $\operatorname{Im} w$ is constant, so that the integral becomes a real Laplace integral with the local quadratic $w(z_0) + \frac{1}{2}w''(z_0)(z-z_0)^2$ giving the Gaussian factor $\sqrt{2\pi/|w''(z_0)|}$. Ch. 6 applies the method to the asymptotics of $n!$ (Stirling), the partition function, and coefficients of generating functions, with careful treatment of the contribution of the tails and the validity conditions.
Wilf, H. S. — generatingfunctionology · A K Peters, 3rd edition (2006), Chapter 5 'Analytic and Asymptotic Methods'. Develops Hayman's method for the asymptotics of coefficients of admissible power series, the saddle-point heuristic of choosing the radius $r=r_n$ by $r f'(r)/f(r) = n$, the resulting formula $a_n \sim f(r_n)/(r_n^n\sqrt{2\pi b_n})$, and worked applications to $e^z$ (giving Stirling), $e^{e^z-1}$ (Bell numbers), and other entire generating functions; states Hayman's admissibility conditions and the closure rules that certify a function admissible without re-checking the integral each time.

Estimated time

beginner: 22m
intermediate: 54m
master: 94m