40.08.03 · combinatorics / analytic-combinatorics-asymptotics

Meromorphic Coefficient Asymptotics

shipped3 tiersLean: none

Anchor (Master): Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. IV-V (rational and meromorphic asymptotics, applications to the supercritical sequence and to surjections, compositions, denumerants, and the analytic Perron-Frobenius reading); Titchmarsh 1939 *The Theory of Functions* 2e (Oxford) Ch. 7 for the meromorphic-function and Mittag-Leffler background; Odlyzko 1995 'Asymptotic enumeration methods' in *Handbook of Combinatorics* (Elsevier) §3-5 for the residue and subtraction-of-singularities technique

Intuition Beginner

The previous unit handed you a way to write a generating function by recipe: describe what your objects are made of, and a fixed dictionary spells out the series. That series packages every count at once, but it does not yet tell you the one thing you most often want — how fast do the counts grow? This unit reads the growth rate straight off the formula, without expanding a single extra term.

The key change in viewpoint is to stop treating the variable as a bookkeeping marker and start treating it as a real (in fact complex) number you can plug in. A generating function is then a genuine function with a graph, and that graph has trouble spots: places where it blows up to infinity, or otherwise stops being smooth. These trouble spots are called singularities. For the composition series $\frac{1 - z}{1 - 2 z}$ from last unit, the trouble spot is at $z = \frac{1}{2}$ , where the bottom hits zero and the value shoots off.

Here is the headline fact. The trouble spot nearest the origin sets the growth rate of the counts. If the nearest one sits at distance $ρ$ from zero, then the count of size- $n$ objects grows like $(1/ ρ)^{n}$ — one over that distance, raised to the power $n$ . For compositions, $ρ = \frac{1}{2}$ , so the counts grow like $2^{n}$ , matching the $2^{n - 1}$ you found by hand.

Visual Beginner

Picture the generating function as a landscape over a flat map. The flat map is the plane of input values, with the origin in the middle. The height of the landscape is how big the function is at each input. Most of the map is gently rolling, but at a singularity a thin spike rises to infinity — a pole, like a flagpole punched through the surface.

Now grow a circle outward from the origin. As long as the circle stays in the rolling part of the map, the series behaves; the moment the circle's edge reaches the first spike, the series stops converging. So the radius of the largest safe circle is exactly the distance to the nearest spike. That radius is the number $ρ$ , and the counts grow like $(1/ ρ)^{n}$ .

where the nearest spike sits	how the counts grow
at distance $ρ = \frac{1}{2}$ (compositions, $\frac{1 - z}{1 - 2 z}$ )	like $(1/ ρ)^{n} = 2^{n}$
at distance $ρ$ on the positive axis	like $(1/ ρ)^{n}$
farther out (bigger $ρ$ )	slower growth
closer in (smaller $ρ$ )	faster growth

A second spike farther away barely matters: its contribution is a smaller growth rate, swamped by the nearest one. So the nearest spike rules, and a useful bonus is that for honest counting series — whose counts are never negative — the nearest spike always sits on the positive axis, straight out to the right, where it is easy to find.

Worked example Beginner

Let us read the growth rate of surjections — the ways to split $n$ labelled tasks into an ordered list of nonempty groups (an ordered set partition). The number of these is called $R_{n}$ , and the labelled symbolic method gives the generating function $R (z) = \frac{1}{2 - e ^{z}}$ , with the count attached to the peg $z^{n} / n!$ . We will not need that derivation; we only need to find the nearest spike.

Step 1. Find where the function blows up. The value $\frac{1}{2 - e ^{z}}$ shoots to infinity exactly when the bottom is zero, that is when $e^{z} = 2$ . On the positive axis this happens at $z = lo g 2$ , which is about $0.693$ . That is a spike.

Step 2. Check it is the nearest one. Any other solution of $e^{z} = 2$ needs the same size for $e^{z}$ , so it sits at least as far out as $lo g 2$ (the others are off the axis and farther from the origin). So the nearest spike is at distance $ρ = lo g 2 \approx 0.693$ .

Step 3. Read the growth rate. The counts (per the $z^{n} / n!$ peg) grow like $(1/ ρ)^{n} = (1/ lo g 2)^{n}$ . Since $1/ lo g 2 \approx 1.4427$ , the growth base is about $1.4427$ .

Step 4. Sanity-check the size. The first few surjection numbers are $R_{0} = 1$ , $R_{1} = 1$ , $R_{2} = 3$ , $R_{3} = 13$ , $R_{4} = 75$ , $R_{5} = 541$ . Dividing each by the one before gives ratios drifting up toward roughly $7$ — and indeed the full count per object is about $\frac{1}{2} (1/ lo g 2)^{n + 1} n!$ , whose successive ratios are $(1/ lo g 2) \cdot n$ , growing because of the $n!$ . The base $1/ lo g 2 \approx 1.4427$ is the part the nearest spike pinned down.

What this tells us: locating one spike — solving $e^{z} = 2$ — handed us the exponential growth base $1/ lo g 2$ of the surjection numbers with no recurrence and no table.

Check your understanding Beginner

Formal definition Intermediate+

A generating function $f (z) = \sum_{n \geq 0} f_{n} z^{n}$ with positive radius of convergence is treated as an analytic function of a complex variable on its disc of convergence, following the formal-power-series substrate of 40.08.01 now read analytically. Two analytic facts anchor everything below; both are imported, not reproved here.

Cauchy's coefficient formula. If $f$ is analytic in a disc containing $0$ and $λ$ is a positively oriented simple loop around $0$ inside the disc of analyticity, then $$ f_n = [z^n]f = \frac{1}{2\pi i}\oint_\lambda \frac{f(z)}{z^{n+1}},dz, $$ the Cauchy integral formula of 06.01.02 applied to extract the $n$ -th coefficient. The radius of convergence $ρ$ of the series equals the modulus of a singularity of $f$ nearest the origin: $f$ is analytic on $∣ z ∣ < ρ$ and has at least one singularity on $∣ z ∣ = ρ$ .

A point $s$ on the circle $∣ z ∣ = ρ$ is a singularity of $f$ if $f$ has no analytic continuation to any neighbourhood of $s$ . The function $f$ is meromorphic on a domain (in the sense of 06.01.05) if it is analytic there except at isolated poles: points $s$ near which $f (z) = \sum_{k = 1}^{m} c_{- k} (z - s)^{- k} + g (z)$ with $g$ analytic at $s$ , $c_{- m} \neq = 0$ ; the integer $m \geq 1$ is the order of the pole, and $c_{- 1} = Res (f; s)$ is its residue. A pole of order $1$ is simple. A rational function $f = N / D$ ( $N, D$ polynomials, $g cd = 1$ , $D (0) \neq = 0$ ) is meromorphic on $C$ with poles exactly at the zeros of $D$ .

The dominant singularities of $f$ are those of smallest modulus, all lying on $∣ z ∣ = ρ$ ; the subdominant singularities lie strictly farther out. The notation $[z^{n}]$ , $\oint$ , $Res$ , $lim sup$ , and $ρ$ (radius / dominant-singularity modulus) is recorded in _meta/NOTATION.md.

Exponential Growth Formula. Writing $ρ$ for the radius of convergence, $lim sup_{n} ∣ f_{n} ∣^{1/ n} = 1/ ρ$ , so $f_{n} = ρ^{- n} θ (n)$ with $θ$ subexponential ( $∣ θ (n) ∣^{1/ n} \to 1$ ). The first principle of coefficient asymptotics is this statement: the location of the dominant singularity fixes the exponential growth factor $ρ^{- n}$ . The second principle, the subject of 40.08.04, is that the nature (type) of the dominant singularity fixes the subexponential factor $θ (n)$ .

Counterexamples to common slips Intermediate+

"The nearest singularity can always be read off the positive real axis." Only for series with nonnegative coefficients — there Pringsheim's theorem guarantees a singularity at $z = ρ$ itself. A series such as $\frac{1}{1 + z ^{2}}$ has coefficients $1, 0, - 1, 0, 1, \dots$ of mixed sign, and its dominant singularities are the non-real points $z = \pm i$ ; nothing sits on the positive axis. Combinatorial OGFs, having nonnegative counts, are the favourable case.
"A pole of order $m$ gives growth $ρ^{- n}$ ." The exponential factor is $ρ^{- n}$ regardless of order, but the subexponential factor depends on the order: a pole of order $m$ at $ρ$ contributes $\sim C ρ^{- n} n^{m - 1} / (m - 1)!$ . A simple pole ( $m = 1$ ) gives a pure $C ρ^{- n}$ ; a double pole gives $C n ρ^{- n}$ .
"All singularities contribute equally." Only the dominant ones contribute to the leading asymptotic. A subdominant pole at $ρ^{'} > ρ$ contributes $O ((ρ^{'})^{- n})$ , exponentially smaller than $ρ^{- n}$ , so it appears only in lower-order correction terms obtained by subtracting the dominant singular part.
"There is always a unique dominant singularity." Several singularities can share the modulus $ρ$ . When two simple poles sit at $\pm ρ$ , their residues combine into an oscillating factor $(- 1)^{n}$ -style term; more generally $d$ poles equally spaced on $∣ z ∣ = ρ$ produce coefficients that are nonzero only on a residue class mod $d$ (periodicity). Pringsheim guarantees one of these is the positive real point, but it need not be alone.

Key theorem with proof Intermediate+

The signature theorem is the residue expansion of meromorphic coefficients: it converts coefficient extraction into a finite sum of residues by deforming the Cauchy contour outward past the poles, and the dominant pole's residue is the leading asymptotic term ^{[Flajolet-Sedgewick Ch. IV.5]}.

Theorem (meromorphic coefficient asymptotics). Let $f$ be analytic at $0$ and meromorphic in the closed disc $∣ z ∣ \leq R$ , with no pole on $∣ z ∣ = R$ , and let its poles in $∣ z ∣ < R$ be $s_{1}, \dots, s_{p}$ . Then $$ [z^n]f = -\sum_{k=1}^{p}\mathrm{Res}\Big(\frac{f(z)}{z^{n+1}};, z = s_k\Big) + \frac{1}{2\pi i}\oint_{|z|=R}\frac{f(z)}{z^{n+1}},dz, $$ and the remainder integral is $O (R^{- n})$ . In particular, if the dominant pole $s_{1} = ρ$ is the unique pole of smallest modulus and has order $m$ with singular part $\sum_{k = 1}^{m} c_{- k} (z - ρ)^{- k}$ , then $$ [z^n]f \sim \frac{c_{-m}}{(m-1)!},(-1)^m,\rho^{-m}\binom{n+m-1}{m-1}\rho^{-n} \sim \frac{c_{-m}(-1)^m}{(m-1)!,\rho^{m}},n^{m-1}\rho^{-n}. $$

Proof. By Cauchy's coefficient formula, $[z^{n}] f = \frac{1}{2 π i} \oint_{∣ z ∣ = r} \frac{f ( z )}{z ^{n + 1}} d z$ for any $r$ with $0 < r < ∣ s_{1} ∣$ (a circle inside the disc of analyticity at the origin). The integrand $f (z) z^{- n - 1}$ is meromorphic in $∣ z ∣ \leq R$ with poles at $0$ (from $z^{- n - 1}$ , with residue $[z^{n}] f$ — but that pole is inside the small circle and already accounted as the integral itself) and at $s_{1}, \dots, s_{p}$ . Deform the contour from $∣ z ∣ = r$ outward to $∣ z ∣ = R$ . By the residue theorem of 06.01.03, the two circular integrals differ by $2 π i$ times the sum of residues of $f (z) z^{- n - 1}$ at the poles crossed, namely $s_{1}, \dots, s_{p}$ : $$ \frac{1}{2\pi i}\oint_{|z|=R}\frac{f(z)}{z^{n+1}},dz - \frac{1}{2\pi i}\oint_{|z|=r}\frac{f(z)}{z^{n+1}},dz = \sum_{k=1}^{p}\mathrm{Res}\Big(\frac{f(z)}{z^{n+1}};, s_k\Big). $$ Rearranging and using the inner integral $= [z^{n}] f$ gives the stated identity. For the remainder, $f$ is continuous hence bounded on the compact circle $∣ z ∣ = R$ , say $∣ f ∣ \leq M$ ; then $\frac{1}{2 π i} \oint_{∣ z ∣ = R} \frac{f}{z ^{n + 1}} \leq \frac{1}{2 π} \cdot 2 π R \cdot \frac{M}{R ^{n + 1}} = M R^{- n}$ , which is $O (R^{- n})$ .

For the asymptotic form, compute the dominant residue. Near $z = ρ$ write $f (z) = \frac{c _{- m}}{( z - ρ ) ^{m}} + \dots$ ; then $\frac{f ( z )}{z ^{n + 1}}$ has the residue at $ρ$ equal to the coefficient of $(z - ρ)^{- 1}$ in $\frac{c _{- m}}{( z - ρ ) ^{m}} z^{- n - 1}$ plus lower-order pole contributions. Expanding $z^{- n - 1} = ρ^{- n - 1} (1 + \frac{z - ρ}{ρ})^{- n - 1}$ in powers of $(z - ρ)$ and extracting the $(z - ρ)^{m - 1}$ coefficient gives $$ \mathrm{Res}\Big(\frac{f}{z^{n+1}}; \rho\Big) = c_{-m},\rho^{-n-1}\binom{-n-1}{m-1}\rho^{-(m-1)} = c_{-m}\frac{(-1)^{m-1}}{\rho^{n+m}}\binom{n+m-1}{m-1}, $$ using $(m - 1 - n - 1) = (- 1)^{m - 1} (m - 1 n + m - 1)$ . Since $[z^{n}] f = - \sum_{k} Res + O (R^{- n})$ and the subdominant residues are each $O (∣ s_{k} ∣^{- n})$ with $∣ s_{k} ∣ > ρ$ , the dominant term is $- Res (\cdot; ρ) = c_{- m} \frac{( - 1 ) ^{m}}{ρ ^{n + m}} (m - 1 n + m - 1)$ , and $(m - 1 n + m - 1) \sim \frac{n ^{m - 1}}{( m - 1 )!}$ gives the claimed $n^{m - 1} ρ^{- n}$ form. $□$

Corollary (simple dominant pole). If $ρ$ is a simple dominant pole with $f (z) \sim \frac{c}{1 - z / ρ}$ near $ρ$ (equivalently residue of $f$ at $ρ$ equal to $- c ρ$ ), then $[z^{n}] f \sim c ρ^{- n}$ . For compositions $\frac{1 - z}{1 - 2 z}$ the pole is at $ρ = \frac{1}{2}$ , simple, with $f (z) = \frac{1 - z}{1 - 2 z}$ and local form $\frac{c}{1 - 2 z}$ , $c = \frac{1}{2}$ , recovering $[z^{n}] f = 2^{n - 1}$ exactly for $n \geq 1$ .

Bridge. This theorem is the foundational reason rational and meromorphic enumeration are governed by a finite amount of local data: the entire infinite sequence $[z^{n}] f$ is captured, up to an exponentially small error, by the residues of $f (z) z^{- n - 1}$ at finitely many poles, and the dominant pole's order and residue alone fix the leading asymptotic. This is exactly the analytic completion of the partial-fraction reading of 40.01.04, where a rational $f = N / D$ was expanded as $\sum_{j} c_{j} (1 - γ_{j} z)^{- r_{j}}$ and its coefficients read as $\sum_{j} p_{j} (n) γ_{j}^{n}$ ; the residue at each reciprocal root $γ_{j}^{- 1}$ is precisely the partial-fraction coefficient, so the residue sum is the partial-fraction sum, and the dominant root $γ$ with largest modulus is the reciprocal of the nearest pole, the central insight tying spectral radius to growth rate. The simple-pole corollary builds toward the supercritical-sequence schema previewed in 40.08.01, where $\frac{1}{1 - A ( z )}$ acquires a simple pole at the root of $A (σ) = 1$ , and it appears again in 40.08.04 as the rational/meromorphic base case of the singularity-analysis transfer, where algebraic and logarithmic singularities replace poles. Putting these together, the residue expansion generalises the dominant-eigenvalue asymptotics of the transfer matrix of 40.01.04: the largest eigenvalue is the reciprocal of the nearest pole of $det (I - z A)^{- 1}$ , so meromorphic coefficient asymptotics and Perron-Frobenius are the same statement read analytically.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Let $f (z) = \frac{1}{( 1 - z ) ( 1 - z /3 )}$ . Identify the dominant pole, compute the residue of $f (z) z^{- n - 1}$ there, and give the leading asymptotic of $[z^{n}] f$ with the subdominant correction.

Hint

Partial fractions: $\frac{1}{( 1 - z ) ( 1 - z /3 )} = \frac{A}{1 - z} + \frac{B}{1 - z /3}$ . The dominant pole is the nearer one, $z = 1$ .

Answer

Partial fractions give $A (1 - z /3) + B (1 - z) = 1$ ; at $z = 1$ , $A (2/3) = 1$ so $A = \frac{3}{2}$ ; at $z = 3$ , $B (- 2) = 1$ so $B = - \frac{1}{2}$ . Thus $f = \frac{3/2}{1 - z} - \frac{1/2}{1 - z /3}$ and $[z^{n}] f = \frac{3}{2} - \frac{1}{2} \cdot 3^{- n}$ . The dominant pole is $z = 1$ ( $ρ = 1$ , the nearer of $1$ and $3$ ), simple, with $[z^{n}] \frac{3/2}{1 - z} = \frac{3}{2}$ ; the subdominant pole at $z = 3$ contributes the exponentially small correction $- \frac{1}{2} 3^{- n}$ . So $[z^{n}] f \to \frac{3}{2}$ with error $O (3^{- n})$ . Rubric: full credit for the partial fractions, the dominant constant $\frac{3}{2}$ , and the $O (3^{- n})$ correction.

Exercise 6 (medium, symbolic).

Compositions into parts of size $1$ or $2$ have OGF $f (z) = \frac{1}{1 - z - z ^{2}}$ (a sequence of parts with part-OGF $z + z^{2}$ ). Find the dominant pole and the exponential growth rate $ρ^{- 1}$ , and identify it as a familiar constant.

Hint

The poles are the roots of $1 - z - z^{2} = 0$ , i.e. $z = \frac{- 1 \pm 5}{2}$ . The dominant one is the root of smaller modulus.

Answer

The denominator $1 - z - z^{2}$ has roots $z = \frac{- 1 \pm 5}{2}$ , namely $ρ = \frac{5 - 1}{2} \approx 0.618$ and the negative root $\approx - 1.618$ . The dominant (nearer) pole is $ρ = \frac{5 - 1}{2} = 1/ φ$ where $φ = \frac{1 + 5}{2}$ is the golden ratio, so the growth base is $ρ^{- 1} = φ \approx 1.618$ . These counts are the Fibonacci numbers $F_{n + 1}$ , whose growth base is indeed $φ$ , recovering the rational-GF reading of 40.01.04 analytically. Rubric: full credit for the roots, the dominant $ρ = 1/ φ$ , and the identification of $φ$ .

Exercise 7 (hard, symbolic).

Prove Pringsheim's theorem for the meromorphic case relevant here: if $f (z) = \sum_{n} f_{n} z^{n}$ has all $f_{n} \geq 0$ and radius of convergence $ρ \in (0, \infty)$ , then $z = ρ$ is a singularity of $f$ . Deduce that the dominant singularity of a combinatorial OGF can be sought on the positive real axis.

Hint

Suppose $f$ were analytic at $ρ$ ; then it has a Taylor expansion at the interior point $z_{0} = ρ /2$ with radius $> ρ /2$ . Bound the coefficients of that expansion using $f_{n} \geq 0$ to extend convergence past $∣ z ∣ = ρ$ , contradicting the definition of $ρ$ .

Answer

Assume for contradiction that $f$ is analytic at $z = ρ$ . Then $f$ is analytic on a disc $∣ z - ρ ∣ < δ$ for some $δ > 0$ . Take the interior point $z_{0} = ρ /2$ ; the Taylor series of $f$ at $z_{0}$ , $f (z) = \sum_{k} \frac{f ^{(k)} ( z _{0} )}{k !} (z - z_{0})^{k}$ , has radius of convergence at least $dist (z_{0}, nearest singularity)$ . The derivatives are $f^{(k)} (z_{0}) = \sum_{n \geq k} f_{n} \frac{n !}{( n - k )!} z_{0}^{n - k} \geq 0$ since every $f_{n} \geq 0$ and $z_{0} > 0$ .

Evaluate the Taylor series at a real point $z = ρ + η$ with small $η > 0$ : every term $\frac{f ^{(k)} ( z _{0} )}{k !} (ρ + η - z_{0})^{k}$ is nonnegative, and the partial sums are bounded by rearranging the double series $\sum_{k} \frac{1}{k !} (ρ /2 + η)^{k} \sum_{n \geq k} f_{n} (k n) (ρ /2)^{n - k} = \sum_{n} f_{n} (ρ /2 + η + ρ /2)^{n} = \sum_{n} f_{n} (ρ + η)^{n}$ (binomial theorem, all terms nonnegative so the interchange is valid). If the Taylor series at $z_{0}$ converges at $ρ + η$ — which it does whenever $ρ /2 + η < δ$ , i.e. $η$ small, since the disc of analyticity at $z_{0}$ reaches past $ρ$ — then $\sum_{n} f_{n} (ρ + η)^{n} < \infty$ , so the original series converges at $z = ρ + η > ρ$ , contradicting that $ρ$ is the radius of convergence. Hence $ρ$ is a singularity. For a combinatorial OGF the counts $f_{n} \geq 0$ , so its dominant singularity lies at the positive real $ρ$ ; one solves for the nearest positive zero of the denominator (rational/meromorphic case) to find it. Rubric: full credit for the nonnegativity of the $z_{0}$ -derivatives, the binomial resummation to $\sum f_{n} (ρ + η)^{n}$ , the contradiction with the radius, and the OGF corollary.

Exercise 8 (hard, symbolic).

For the surjection EGF $f (z) = \frac{1}{2 - e ^{z}}$ , show the dominant pole at $ρ = lo g 2$ is simple, compute its residue, and derive the full leading asymptotic $R_{n} / n! \sim \frac{1}{2} (lo g 2)^{- n - 1}$ .

Hint

A simple pole of $\frac{1}{g ( z )}$ at $ρ$ where $g (ρ) = 0$ , $g^{'} (ρ) \neq = 0$ has residue $1/ g^{'} (ρ)$ . Here $g (z) = 2 - e^{z}$ . Then use the simple-pole corollary $[z^{n}] f \sim c ρ^{- n}$ with $f \sim \frac{c}{1 - z / ρ}$ .

Answer

With $g (z) = 2 - e^{z}$ , the dominant zero is $ρ = lo g 2$ (where $e^{ρ} = 2$ ), and $g^{'} (z) = - e^{z}$ , so $g^{'} (ρ) = - 2 \neq = 0$ : the pole is simple. The residue of $f = 1/ g$ at $ρ$ is $\frac{1}{g ^{'} ( ρ )} = \frac{1}{- 2} = - \frac{1}{2}$ . To extract coefficients, write the local form $f (z) \sim \frac{- 1/2}{z - l o g 2} = \frac{- 1/2}{- l o g 2} \cdot \frac{1}{1 - z / l o g 2} = \frac{1}{2 l o g 2} \cdot \frac{1}{1 - z / l o g 2}$ , a simple pole with $\frac{c}{1 - z / ρ}$ and $c = \frac{1}{2 l o g 2}$ , $ρ = lo g 2$ . By the corollary $[z^{n}] f \sim c ρ^{- n} = \frac{1}{2 l o g 2} (lo g 2)^{- n} = \frac{1}{2} (lo g 2)^{- n - 1}$ . Since the EGF attaches $R_{n}$ to $z^{n} / n!$ , this is $R_{n} / n! \sim \frac{1}{2} (lo g 2)^{- n - 1}$ , equivalently $R_{n} \sim \frac{n !}{2} (lo g 2)^{- n - 1}$ . Numerically $R_{5} /5! = 541/120 \approx 4.51$ against $\frac{1}{2} (lo g 2)^{- 6} \approx 4.90$ , converging as $n$ grows. Rubric: full credit for the simple-pole check $g^{'} (ρ) \neq = 0$ , the residue $- \frac{1}{2}$ , the local $\frac{c}{1 - z / ρ}$ rewriting with $c = \frac{1}{2 l o g 2}$ , and the asymptotic $\frac{1}{2} (lo g 2)^{- n - 1}$ .

Advanced results Master

Beyond the single dominant pole, the meromorphic theory extends through the systematic subtraction of singular parts, the treatment of several singularities on the circle of convergence, the supercritical-sequence schema as the canonical simple-pole source, the denumerant / multiple-pole-at-roots-of-unity case, and the analytic recasting of Perron-Frobenius.

Theorem 1 (full singular expansion by subtraction of singularities). Let $f$ be meromorphic in $∣ z ∣ \leq R$ with poles $s_{1}, \dots, s_{p}$ ordered by increasing modulus, $s_{j}$ of order $m_{j}$ and singular part $S_{j} (z) = \sum_{k = 1}^{m_{j}} c_{- k}^{(j)} (z - s_{j})^{- k}$ . Then $f - \sum_{j} S_{j}$ is analytic in $∣ z ∣ \leq R$ , so its coefficients are $O (R^{- n})$ , and $$ [z^n]f = \sum_{j=1}^{p}[z^n]S_j(z) + O(R^{-n}), \qquad [z^n]\frac{c_{-k}}{(s_j - z)^k} = c_{-k}\binom{n+k-1}{k-1}s_j^{-n-k}, $$ giving an asymptotic expansion to any prescribed exponential precision by taking $R$ past successively more poles. Each pole contributes a polynomial-in- $n$ times $s_{j}^{- n}$ , and ordering by $∣ s_{j} ∣$ orders the terms by decreasing exponential weight ^{[Flajolet-Sedgewick Ch. IV.5, Odlyzko 1995 §4]}.

Theorem 2 (several dominant singularities and periodicity). If $f$ has $d \geq 2$ poles of equal smallest modulus $ρ$ , located at $ρ ω_{j}$ with $ω_{j}$ on the unit circle, the leading coefficient asymptotics is the sum of the $d$ dominant residues, $[z^{n}] f \sim ρ^{- n} \sum_{j} c_{j} ω_{j}^{- n}$ . When the $ω_{j}$ are roots of unity (the typical case for combinatorial OGFs with a periodicity / gcd structure in the allowed sizes), the factor $\sum_{j} c_{j} ω_{j}^{- n}$ is periodic in $n$ , so $[z^{n}] f$ is a periodic modulation of $ρ^{- n}$ ; the period is the order of the group generated by the $ω_{j}$ . A function $f (z) = h (z^{d})$ has all its dominant singularities at the $d$ -th roots of $ρ^{d}$ , the structural source of period- $d$ coefficients ^{[Flajolet-Sedgewick Ch. IV.6]}.

Theorem 3 (supercritical sequence, analytic form). If $F = SEQ (A)$ with $A (z)$ analytic at $0$ , $A (0) = 0$ , radius of convergence $r_{A} > 0$ , and $A (z) \to A (r_{A}^{-}) > 1$ , then $F (z) = \frac{1}{1 - A ( z )}$ has a dominant singularity at the unique $σ \in (0, r_{A})$ with $A (σ) = 1$ , which is a simple pole because $A^{'} (σ) > 0$ (positive coefficients). By the simple-pole corollary, $$ [z^n]F(z) = [z^n]\frac{1}{1 - A(z)} \sim \frac{1}{\sigma A'(\sigma)},\sigma^{-n}, $$ the residue $- 1/ A^{'} (σ)$ of $F$ at $σ$ producing the clean $σ^{- n}$ growth previewed combinatorially in 40.08.01. The number of $A$ -components in a random size- $n$ object is then asymptotically Gaussian with mean and variance linear in $n$ ^{[Flajolet-Sedgewick Ch. V.2]}.

Theorem 4 (denumerants and poles at roots of unity). The denumerant $d (n; a_{1}, \dots, a_{k})$ counting representations $n = a_{1} x_{1} + \dots + a_{k} x_{k}$ in nonnegative integers has OGF $\prod_{i = 1}^{k} \frac{1}{1 - z ^{a_{i}}}$ , a rational function all of whose poles lie on the unit circle (at roots of unity), with the pole at $z = 1$ of order $k$ dominant. Hence $d (n; a) \sim \frac{n ^{k - 1}}{( k - 1 )! a _{1} \dots a _{k}}$ , a quasi-polynomial in $n$ of degree $k - 1$ : the order- $k$ pole at $1$ gives the polynomial growth $n^{k - 1}$ , while the lower-order poles at the other roots of unity contribute the periodic (quasi-polynomial) fluctuations. This is the Sylvester-Schur denumerant, the prototype of Ehrhart quasi-polynomials ^{[Flajolet-Sedgewick Ch. IV.6]}.

Theorem 5 (analytic Perron-Frobenius). For a strongly connected weighted digraph with nonnegative transfer matrix $A$ , the walk-generating function $[(I - z A)^{- 1}]_{ij} = \frac{N _{ij} ( z )}{d e t ( I - z A )}$ of 40.01.04 is rational with denominator $det (I - z A) = \prod_{i} (1 - λ_{i} z)$ , $λ_{i}$ the eigenvalues of $A$ . Its dominant pole is $ρ = 1/ λ_{PF}$ , the reciprocal of the Perron-Frobenius eigenvalue $λ_{PF} = max_{i} ∣ λ_{i} ∣$ , which is simple by Perron-Frobenius; therefore $(A^{n})_{ij} \sim c_{ij} λ_{PF}^{n}$ with $c_{ij}$ built from the left/right Perron eigenvectors. The meromorphic residue at $1/ λ_{PF}$ is exactly the Perron projector, so coefficient asymptotics and spectral dominance coincide ^{[Flajolet-Sedgewick Ch. V.5]}.

Synthesis. Meromorphic coefficient asymptotics is the foundational reason a generating function's finite local data — the location, order, and residue of its dominant pole — determines the infinite asymptotic profile of its coefficients. The central insight is that Cauchy's coefficient formula turns coefficient extraction into a contour integral, and pushing that contour outward past the poles, by the residue theorem of 06.01.03, replaces the integral with a finite residue sum plus an exponentially small remainder; the dominant pole's residue is the leading term, and this is exactly the analytic completion of the partial-fraction reading of 40.01.04, where each residue at a reciprocal characteristic root is the partial-fraction coefficient. Pringsheim's theorem is the foundational reason combinatorics is the favourable case: nonnegative counts force the dominant singularity onto the positive real axis, so the growth base $ρ^{- 1}$ is found by solving a real equation — $1 - 2 z = 0$ for compositions, $A (σ) = 1$ for supercritical sequences, $2 - e^{z} = 0$ for surjections. This is dual to the spectral reading of the transfer matrix: the nearest pole is the reciprocal Perron-Frobenius eigenvalue, so meromorphic asymptotics and Perron-Frobenius dominance are one statement, and the residue at the dominant pole is the Perron projector — a reading that generalises the dominant-eigenvalue growth of 40.01.04.

Putting these together, the first principle (singularity location fixes the exponential factor $ρ^{- n}$ ) is complete for the rational and meromorphic world, where every singularity is a pole and the subexponential factor is the polynomial $n^{m - 1}$ of the pole order; the bridge to 40.08.04 is that the second principle — singularity type fixes the subexponential factor — generalises this to the algebraic and logarithmic singularities ( $1 - z / ρ$ , $lo g \frac{1}{1 - z / ρ}$ ) where the factor becomes $n^{- 3/2}$ , $n^{- 1/2}$ , or $1/ lo g n$ , and the residue calculus is replaced by the Hankel-contour transfer theorems. The recipe-to-series dictionary of 40.08.01 and the series-to-growth reading of this unit are one analytic-combinatorics pipeline.

Full proof set Master

Proposition 1 (Cauchy's coefficient formula and the radius as nearest singularity). If $f = \sum_{n} f_{n} z^{n}$ is analytic on $∣ z ∣ < ρ$ , then for $0 < r < ρ$ , $f_{n} = \frac{1}{2 π i} \oint_{∣ z ∣ = r} \frac{f ( z )}{z ^{n + 1}} d z$ ; and $ρ$ equals the distance from $0$ to the nearest singularity of $f$ .

Proof. On $∣ z ∣ = r < ρ$ the series $\sum_{m} f_{m} z^{m}$ converges uniformly, so it may be integrated term by term against $\frac{1}{2 π i} z^{- n - 1}$ : $\frac{1}{2 π i} \oint \frac{f ( z )}{z ^{n + 1}} d z = \sum_{m} f_{m} \frac{1}{2 π i} \oint z^{m - n - 1} d z = \sum_{m} f_{m} [m = n] = f_{n}$ , using $\frac{1}{2 π i} \oint_{∣ z ∣ = r} z^{k} d z = [k = - 1]$ . This is the Cauchy integral formula for the $n$ -th derivative, 06.01.02. For the radius statement: $f$ is analytic on $∣ z ∣ < ρ$ by hypothesis, so the nearest singularity is at distance $\geq ρ$ ; conversely if $f$ were analytic on an open disc of radius $ρ^{'} > ρ$ about $0$ , its Taylor series there would converge on $∣ z ∣ < ρ^{'}$ and agree with $\sum f_{n} z^{n}$ , contradicting that $ρ$ is the radius of convergence (Cauchy-Hadamard). Hence a singularity sits on $∣ z ∣ = ρ$ and none nearer. $□$

Proposition 2 (exponential growth formula). With $ρ$ the radius of convergence of $f = \sum f_{n} z^{n}$ , $lim sup_{n} ∣ f_{n} ∣^{1/ n} = 1/ ρ$ , so $f_{n} = ρ^{- n} θ (n)$ with $lim sup ∣ θ (n) ∣^{1/ n} = 1$ .

Proof. This is Cauchy-Hadamard: the radius of convergence of a power series is $ρ = 1/ lim sup_{n} ∣ f_{n} ∣^{1/ n}$ . Indeed if $∣ z ∣ < 1/ lim sup ∣ f_{n} ∣^{1/ n}$ then $∣ f_{n} z^{n} ∣^{1/ n} = ∣ f_{n} ∣^{1/ n} ∣ z ∣ < 1$ eventually, so $\sum f_{n} z^{n}$ converges by the root test; and if $∣ z ∣ > 1/ lim sup ∣ f_{n} ∣^{1/ n}$ the terms do not tend to $0$ . Thus $lim sup ∣ f_{n} ∣^{1/ n} = 1/ ρ$ . Setting $θ (n) = f_{n} ρ^{n}$ gives $lim sup ∣ θ (n) ∣^{1/ n} = ρ lim sup ∣ f_{n} ∣^{1/ n} = ρ \cdot ρ^{- 1} = 1$ , the subexponential normalisation. $□$

Proposition 3 (residue expansion with remainder). Let $f$ be analytic at $0$ , meromorphic in $∣ z ∣ \leq R$ with poles $s_{1}, \dots, s_{p}$ in $0 < ∣ z ∣ < R$ and none on $∣ z ∣ = R$ . Then $[z^{n}] f = - \sum_{k} Res (f (z) z^{- n - 1}; s_{k}) + \frac{1}{2 π i} \oint_{∣ z ∣ = R} f (z) z^{- n - 1} d z$ , with the last term $O (R^{- n})$ .

Proof. The function $ϕ (z) = f (z) z^{- n - 1}$ is meromorphic in $∣ z ∣ \leq R$ with poles among ${0, s_{1}, \dots, s_{p}}$ . By the residue theorem 06.01.03 applied to the circle $∣ z ∣ = R$ (which encloses all of them and meets none), $\frac{1}{2 π i} \oint_{∣ z ∣ = R} ϕ = Res (ϕ; 0) + \sum_{k} Res (ϕ; s_{k})$ . The residue at $0$ : near $0$ , $f (z) = \sum_{m} f_{m} z^{m}$ is analytic, so $ϕ (z) = \sum_{m} f_{m} z^{m - n - 1}$ and the coefficient of $z^{- 1}$ is $f_{n}$ , giving $Res (ϕ; 0) = f_{n} = [z^{n}] f$ . Rearranging, $[z^{n}] f = \frac{1}{2 π i} \oint_{∣ z ∣ = R} ϕ - \sum_{k} Res (ϕ; s_{k})$ . The bound on the boundary integral is $\frac{1}{2 π i} \oint_{∣ z ∣ = R} ϕ \leq \frac{1}{2 π} (2 π R) sup_{∣ z ∣ = R} ∣ f (z) ∣ R^{- n - 1} = R^{- n} sup_{∣ z ∣ = R} ∣ f ∣$ , and $sup_{∣ z ∣ = R} ∣ f ∣ < \infty$ by continuity on the compact circle, so the term is $O (R^{- n})$ . $□$

Proposition 4 (order- $m$ pole asymptotic). If the dominant pole $ρ > 0$ of $f$ is unique of smallest modulus and has order $m$ with leading Laurent coefficient $c_{- m}$ , then $[z^{n}] f \sim \frac{( - 1 ) ^{m} c _{- m}}{( m - 1 )! ρ ^{m}} n^{m - 1} ρ^{- n}$ .

Proof. By Proposition 3 with $R$ chosen between $ρ$ and the next-smallest $∣ s_{k} ∣$ , $[z^{n}] f = - Res (f (z) z^{- n - 1}; ρ) + O (R^{- n})$ with $R > ρ$ (no other pole is dominant). Near $ρ$ , write $f (z) = \frac{c _{- m}}{( z - ρ ) ^{m}} + (lower-order poles and analytic)$ ; the residue of $\frac{c _{- m}}{( z - ρ ) ^{m}} z^{- n - 1}$ at $ρ$ is the coefficient of $(z - ρ)^{m - 1}$ in the Taylor expansion of $c_{- m} z^{- n - 1}$ about $ρ$ , namely $c_{- m} \frac{1}{( m - 1 )!} \frac{d ^{m - 1}}{d z ^{m - 1}} z^{- n - 1}_{z = ρ} = c_{- m} \frac{( - 1 ) ^{m - 1} ( n + 1 ) ( n + 2 ) \dots ( n + m - 1 )}{( m - 1 )!} ρ^{- n - m}$ . The lower-order singular terms $(z - ρ)^{- j}$ , $j < m$ , contribute residues of order $n^{j - 1} ρ^{- n}$ , subleading. Thus $- Res = c_{- m} \frac{( - 1 ) ^{m}}{( m - 1 )!} (m - 1 n + m - 1) (m - 1)! ρ^{- n - m} / (m - 1)!$ ; using $(n + 1) \dots (n + m - 1) = \frac{( n + m - 1 )!}{n !} \sim n^{m - 1}$ , the leading term is $\frac{( - 1 ) ^{m} c _{- m}}{( m - 1 )! ρ ^{m}} n^{m - 1} ρ^{- n}$ , and the remainder $O (R^{- n})$ with $R > ρ$ is exponentially smaller. $□$

Connections Master

This unit is the analytic completion of the rational-generating-function and transfer-matrix theory of 40.01.04: there the closed form $a_{n} = \sum_{i} p_{i} (n) γ_{i}^{n}$ was obtained algebraically by partial fractions, and here each $γ_{i} = s_{i}^{- 1}$ is the reciprocal of a pole $s_{i}$ , the partial-fraction coefficient is the residue of $f (z) z^{- n - 1}$ at that pole, and the dominant root $γ$ of largest modulus is the reciprocal of the nearest pole $ρ$ . The transfer-matrix denominator $det (I - z A)$ has its dominant root at the reciprocal Perron-Frobenius eigenvalue, so the analytic Perron-Frobenius theorem of the Advanced results is the meromorphic reading of that unit's spectral asymptotics.
The generating functions this unit dissects are produced by the symbolic method of the prerequisite 40.08.01: the supercritical-sequence schema $\frac{1}{1 - A ( z )}$ with its simple pole at $A (σ) = 1$ , the composition OGF $\frac{1 - z}{1 - 2 z}$ , and the partition / denumerant products $\prod (1 - z^{a_{i}})^{- 1}$ all arise from the dictionary there, and this unit supplies the residue calculus that reads their growth rates. The labelled half 40.08.02 supplies the surjection EGF $\frac{1}{2 - e ^{z}}$ and the set-partition / permutation EGFs whose meromorphic poles this unit's method locates.
The first/second-principle split previewed here is completed in the co-produced singularity-analysis unit 40.08.04: when the dominant singularity is algebraic ( $1 - z / ρ$ , from tree recursions and the implicit-function schema) or logarithmic rather than a pole, the residue calculus fails and is replaced by the Hankel-contour transfer theorems, which read the subexponential factor $n^{α - 1}$ off the singular exponent. This unit is the rational/meromorphic base case ( $α$ a positive integer, factor $n^{m - 1}$ ) of that general scale; the co-produced saddle-point unit 40.08.06 handles the remaining case of entire generating functions with no finite singularity, where growth is read from the saddle of $f (z) z^{- n - 1}$ rather than from a pole.
The complex-analytic substrate is imported wholesale from the Riemann-surfaces chapter: Cauchy's integral formula 06.01.02 supplies the coefficient integral, the residue theorem 06.01.03 supplies the contour-deformation residue sum, and the theory of meromorphic functions 06.01.05 supplies the pole/Laurent/residue vocabulary. This unit is one of the principal combinatorial consumers of that machinery, and the denumerant quasi-polynomials of the Advanced results connect forward to the Ehrhart theory of lattice-point counting in 40.03.02, where poles at roots of unity reappear as the periodic part of the Ehrhart quasi-polynomial.

Historical & philosophical context Master

The use of complex analysis to extract the growth of combinatorial sequences begins with the circle method and the saddle-point estimates of Hardy and Ramanujan's 1918 asymptotic for the partition function $p (n)$ , and with Darboux's late-nineteenth-century method of reading coefficient asymptotics from the singularities of a generating function on its circle of convergence. The clean statement that the radius of convergence is the distance to the nearest singularity, and that nonnegative coefficients force a singularity onto the positive axis, is Alfred Pringsheim's theorem (1894), foundational for the favourable combinatorial case ^{[Titchmarsh 1939]}.

The systematic residue / partial-fraction treatment of rational and meromorphic coefficient asymptotics, with the dominant pole giving $C ρ^{- n} n^{m - 1}$ and the subtraction-of-singularities method exposing lower-order terms, was consolidated as the entry point to analytic combinatorics by Philippe Flajolet and Robert Sedgewick, whose Analytic Combinatorics (2009) ^{[Flajolet-Sedgewick Ch. IV]} organises it as the rational/meromorphic precursor to the algebraic-singularity transfer theory; Andrew Odlyzko's 1995 Handbook of Combinatorics survey ^{[Odlyzko 1995]} gives the parallel systematic account with explicit error bounds. The recognition that the dominant pole of a transfer-matrix generating function is the reciprocal Perron-Frobenius eigenvalue, tying meromorphic asymptotics to the spectral theory of nonnegative matrices, runs back to the statistical-mechanics transfer-matrix tradition of Kramers and Wannier (1941) and was made combinatorially explicit in Stanley's enumerative-combinatorics framework and in Flajolet-Sedgewick's Chapter V.

Bibliography Master

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

@book{titchmarsh1939functions,
  author    = {Titchmarsh, E. C.},
  title     = {The Theory of Functions},
  edition   = {2},
  publisher = {Oxford University Press},
  year      = {1939}
}

@incollection{odlyzko1995asymptotic,
  author    = {Odlyzko, Andrew M.},
  title     = {Asymptotic enumeration methods},
  booktitle = {Handbook of Combinatorics},
  editor    = {Graham, R. L. and Gr\"{o}tschel, M. and Lov\'{a}sz, L.},
  volume    = {2},
  publisher = {Elsevier and MIT Press},
  year      = {1995},
  pages     = {1063--1229}
}

@book{henrici1974applied,
  author    = {Henrici, Peter},
  title     = {Applied and Computational Complex Analysis, Volume 1},
  publisher = {John Wiley \& Sons},
  year      = {1974}
}

@article{hardyramanujan1918,
  author  = {Hardy, G. H. and Ramanujan, S.},
  title   = {Asymptotic formulae in combinatory analysis},
  journal = {Proceedings of the London Mathematical Society},
  volume  = {17},
  year    = {1918},
  pages   = {75--115}
}

@article{pringsheim1894,
  author  = {Pringsheim, Alfred},
  title   = {\"{U}ber Functionen, welche in gewissen Punkten endliche Differentialquotienten jeder endlichen Ordnung, aber keine Taylor'sche Reihenentwickelung besitzen},
  journal = {Mathematische Annalen},
  volume  = {44},
  year    = {1894},
  pages   = {41--56}
}

@article{kramerswannier1941,
  author  = {Kramers, H. A. and Wannier, G. H.},
  title   = {Statistics of the two-dimensional ferromagnet. Part I},
  journal = {Physical Review},
  volume  = {60},
  year    = {1941},
  pages   = {252--262}
}

Prerequisites

40.08.01

Tier anchors

beginner: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. IV.1-IV.3 (the generating function as a complex-analytic object, the radius of convergence as the distance to the nearest singularity, and the first principle 'location of singularities controls exponential growth'); Wilf 2006 *generatingfunctionology* 3e (A K Peters) Ch. 5 for the rate-of-growth heuristic read off the nearest pole
intermediate: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. IV (Complex Analysis, Rational and Meromorphic Asymptotics): Cauchy's coefficient formula, the exponential growth formula, Pringsheim's theorem, and the residue/partial-fraction expansion $[z^n]f = -\sum \mathrm{Res}\, f(z)/z^{n+1}$ giving $[z^n]f \sim C\,\rho^{-n}n^{m-1}$ for a pole of order $m$; Henrici 1974 *Applied and Computational Complex Analysis, Vol. 1* (Wiley) Ch. 4 for the Cauchy-integral / residue substrate
master: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. IV-V (rational and meromorphic asymptotics, applications to the supercritical sequence and to surjections, compositions, denumerants, and the analytic Perron-Frobenius reading); Titchmarsh 1939 *The Theory of Functions* 2e (Oxford) Ch. 7 for the meromorphic-function and Mittag-Leffler background; Odlyzko 1995 'Asymptotic enumeration methods' in *Handbook of Combinatorics* (Elsevier) §3-5 for the residue and subtraction-of-singularities technique

References

Flajolet, P. & Sedgewick, R. — Analytic Combinatorics · Cambridge University Press (2009). Chapter IV 'Complex Analysis, Rational and Meromorphic Asymptotics' is the source for this unit. §IV.1 reinstates the generating function as an analytic function of a complex variable and records Cauchy's coefficient formula $[z^n]f = \frac{1}{2\pi i}\oint f(z)\,z^{-n-1}\,dz$ over a contour inside the disc of analyticity. §IV.2 proves that the radius of convergence of $f = \sum f_n z^n$ equals the modulus of a singularity of $f$ nearest the origin (the Cauchy-Hadamard radius is the distance to the nearest singularity), and states the Exponential Growth Formula $f_n = \rho^{-n}\theta(n)$ with $\limsup |f_n|^{1/n} = 1/\rho$ and $\theta(n)$ subexponential. §IV.3 is Pringsheim's theorem: a function with a power-series expansion at $0$ having nonnegative coefficients and finite radius of convergence $\rho$ has a singularity at the point $z = \rho$ on the positive real axis. §IV.4-IV.5 develop rational and meromorphic coefficient asymptotics: for $f = N/D$ rational, partial fractions give $f_n = \sum_j c_j \binom{n+r_j-1}{r_j-1}\alpha_j^{-n}$; in general, $[z^n]f = -\sum_{\text{poles }s} \mathrm{Res}\big(f(z)z^{-n-1}; z = s\big)$ obtained by pushing the Cauchy contour outward and collecting residues, and a pole of order $m$ at $z=\rho$ contributes $\sim C\,\rho^{-n} n^{m-1}/(m-1)!$, the dominant pole giving the lead term and subdominant poles the exponentially smaller corrections; multiple poles on $|z|=\rho$ produce oscillatory (periodic) coefficient behaviour. §IV.6-IV.7 work the examples: surjections / ordered set partitions $1/(2-e^z)$ with dominant pole at $z=\log 2$, compositions with restricted summands, the supercritical-sequence schema, and linear recurrences / denumerants. The 'first principle of coefficient asymptotics' (singularity location $\to$ exponential growth $\rho^{-n}$) and the 'second principle' (singularity type $\to$ subexponential factor) frame the passage to singularity analysis of algebraic-logarithmic singularities.
Titchmarsh, E. C. — The Theory of Functions · Oxford University Press, 2nd edition (1939). Chapter 7 develops the theory of meromorphic functions: a function meromorphic in a region is analytic there except for isolated poles; the Laurent expansion at a pole of order $m$, $f(z) = \sum_{k=1}^{m} c_{-k}(z-s)^{-k} + (\text{analytic})$; the residue $\mathrm{Res}(f;s) = c_{-1}$ and the residue theorem $\frac{1}{2\pi i}\oint f = \sum \mathrm{Res}$ over enclosed poles; and the Mittag-Leffler theorem constructing a meromorphic function with prescribed principal parts, which underlies the partial-fraction expansion of a rational function and the singular-part subtraction used in meromorphic coefficient asymptotics. Chapters 2-3 supply the Cauchy integral theorem and formula and the Cauchy-Hadamard determination of the radius of convergence as the distance from the centre to the nearest singularity.
Odlyzko, A. M. — Asymptotic enumeration methods · in Handbook of Combinatorics (R. Graham, M. Grötschel, L. Lovász eds.), Elsevier / MIT Press (1995), Vol. 2, Ch. 22, pp. 1063-1229. §3-5 survey the analytic methods: the generating function as an analytic function, the radius of convergence as the location of the nearest singularity, Cauchy's coefficient integral and its evaluation by residues for rational and meromorphic functions, the subtraction-of-singularities method (subtract the principal part of the dominant singularity to expose the next-order term), the role of subdominant singularities and of multiple singularities on the circle of convergence (periodicity), and the systematic computation $[z^n]f = -\sum \mathrm{Res}(f(z)z^{-n-1})$ with explicit error bounds from the remaining contour integral. The surjection and composition examples and the transfer from the dominant simple pole to $C\rho^{-n}$ are treated as the model rational/meromorphic cases before the algebraic-singularity (singularity-analysis) machinery.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m