Singularity Analysis and the Transfer Theorems

Intuition Beginner

The previous unit read the growth rate of counts off a single feature of the generating function: the trouble spot — the singularity — nearest the origin. When that trouble spot is a clean spike (a pole, where the function shoots to infinity like one-over-a-distance), the recipe is complete: the spike's distance fixes the base of the growth, and the spike's sharpness fixes a whole-number power of $n$ riding on top.

But not every trouble spot is a clean spike. The generating function for trees, for instance, does not blow up at its trouble spot — it stays finite there but turns a sharp corner, the way a square-root graph does at zero. You can stand at the trouble spot and the height is perfectly ordinary; what misbehaves is the slope, which becomes vertical. The pole calculus of the last unit has nothing to say about a corner like this, because there is no infinity to take a residue of.

This unit handles those softer trouble spots. The headline idea stays the same — the nearest trouble spot rules — but now a second message is added: the shape of the trouble spot sets the polynomial correction. A spike gives a rising power of $n$; a square-root corner gives a falling power, $n$-to-the-minus-three-halves; a gentle logarithmic kink gives a one-over-log-$n$ factor. Read the shape, and you read the correction.

Visual Beginner

Picture the generating function again as a landscape over a flat map, with the origin in the middle and a circle grown outward until its edge first meets a trouble spot. Last unit, the trouble spot was an infinite spike. This unit, the trouble spot is gentler: the surface stays at a finite height but develops a sharp feature — a fold, a corner, a vertical cliff in the slope — right where the circle's edge touches.

shape of the trouble spot at distance $\rho$	polynomial correction on the counts
a spike (pole) — function blows up	a rising whole power of $n$
a square-root fold — slope goes vertical	$n$ to the power $-\frac{3}{2}$ (a falling power)
a logarithmic kink — a soft crease	a factor of about $1÷\log n$
a flat touch (function value $0$ there)	a falling power like $n$ to the $-\frac{1}{2}$

The distance to the trouble spot still gives the base of the growth, exactly as before. The new content is the right-hand column: each shape of feature comes with its own correction factor, and once you recognise the shape you can write the correction down from a short table.

Worked example Beginner

Let us read the growth of the Catalan numbers $C_n$, which count binary trees of size $n$ (among many other things). Their generating function is $C(z)=\frac{1-\sqrt{1-4z}}{2z}$, found in an earlier unit. We will read its growth from the shape of its trouble spot, with no expansion of extra terms.

Step 1. Find the trouble spot. The only place the formula misbehaves is where the square root $\sqrt{1-4z}$ turns its corner, namely where $1-4z=0$, that is $z=\frac{1}{4}$. At that point the function value is finite (the top becomes $1-0=1$, divided by $2\cdot \frac{1}{4}$), so this is not a spike — it is a square-root fold. The distance is $\rho =\frac{1}{4}$.

Step 2. Read the base. The base of the growth is one over the distance: $1÷\frac{1}{4}=4$. So the counts carry a factor $4^n$.

Step 3. Read the shape correction. The trouble spot is a square-root fold — the function behaves like a constant minus a multiple of $\sqrt{1-4z}$ near $z=\frac{1}{4}$. The table says a square-root fold gives the correction $n^{-3/2}$ (with a constant $\frac{1}{\sqrt{\pi }}$ from the standard scale). Putting the base and the correction together: $C_n$ grows like $\frac{4^n}{n^{3/2}\sqrt{\pi }}$.

Step 4. Sanity-check. The first Catalan numbers are $1,1,2,5,14,42,132,429$. Take $n=6$: $C_6=132$, and the estimate $\frac{4^6}{6^{3/2}\sqrt{\pi }}=\frac{4096}{14.70\cdot 1.772}\approx \frac{4096}{26.05}\approx 157$. For $n=10$, $C_{10}=16796$ against $\frac{4^{10}}{10^{3/2}\sqrt{\pi }}\approx \frac{1048576}{56.05}\approx 18708$. The estimate runs a little high but closes in as $n$ grows — the falling power $n^{-3/2}$ is exactly the square-root fold's fingerprint.

What this tells us: recognising the shape of one trouble spot — a square-root fold at $\frac{1}{4}$ — handed us both the base $4^n$ and the correction $n^{-3/2}$, with no recurrence and no table of values.

Check your understanding Beginner

Formal definition Intermediate+

Singularity analysis extracts the asymptotics of $[z^n]f$ from the type of the dominant singularity of $f$ when that singularity is algebraic-logarithmic rather than polar, so that the residue calculus of 40.08.03 does not apply. The method rests on a fixed scale of comparison functions and a region of analytic continuation.

The standard function scale. For $\alpha \in \mathbb{C}$, the basic singular function is $(1-z{)}^{-\alpha }$, analytic on $\mathbb{C}\setminus [1,\infty )$ with the principal branch, singular at $z=1$. Its coefficients are the generalised binomial coefficients, and their asymptotics are governed by the Gamma function $\Gamma$ of 06.01.15: $$ [z^n](1 - z)^{-\alpha} = \binom{n + \alpha - 1}{n} = \frac{\Gamma(n + \alpha)}{\Gamma(\alpha),\Gamma(n + 1)} \sim \frac{n^{\alpha - 1}}{\Gamma(\alpha)}\qquad (\alpha \notin \mathbb{Z}{\le 0}). $$ When $\alpha \in \mathbb{Z}{\le 0}$thefunctionisapolynomialandthecoefficientsvanishforlarge$n$($1/\Gamma(\alpha) = 0$atthepolesof$\Gamma$,consistentwiththeformula).The\ast \ast logarithmicvariants\ast \ast$(1 - z)^{-\alpha}\big(\tfrac{1}{z}\log\tfrac{1}{1 - z}\big)^k$extendthescale;for$k = 1$, $$ [z^n](1 - z)^{-\alpha}\log\tfrac{1}{1 - z} \sim \frac{n^{\alpha - 1}}{\Gamma(\alpha)}\big(\log n + \gamma - \psi(\alpha)\big), $$ with $\gamma$ the Euler-Mascheroni constant and $\psi ={\Gamma }^{\prime }/\Gamma$ the digamma. A singularity at a general $\rho \ne 1$ is reduced to this scale by the rescaling $z\mapsto z/\rho$, which multiplies coefficients by ${\rho }^{-n}$.

The $\Delta$-domain. For $0<\varphi <\frac{\pi }{2}$ and $R>1$, the $\Delta$-domain at $1$ is $$ \Delta(\phi, R) = {z \in \mathbb{C} : |z| < R,\ z \ne 1,\ |\arg(z - 1)| > \phi}, $$ the open disc of radius $R$ with a closed sector of half-angle $\varphi$ removed around the point $1$ — a region extending beyond the unit circle except for a thin wedge cut out at the singularity (the "pac-man" or camembert domain). A function is $\Delta$-analytic if it is analytic in some $\Delta (\varphi ,R)$. A general $\rho$-singularity uses the rotated-scaled domain $\rho \cdot \Delta (\varphi ,R)$.

A function $f$ admits a singular expansion at $1$ in the scale if, as $z\to 1$ in a $\Delta$-domain, $f(z)={\sum }_j{c}_j(1-z{)}^{-{\alpha }_j}+O((1-z{)}^{-\beta })$ for a finite decreasing sequence of exponents ${\alpha }_j$ and an error exponent $\beta <{\min }_j{\alpha }_j$. The symbols $\Delta (\varphi ,R)$, $(1-z{)}^{-\alpha }$, $\Gamma$, $\psi$, $\gamma$, and the Hankel contour $\mathcal{H}$ are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "The transfer theorems need only a bound at the singularity." They need a bound and analytic continuation into a $\Delta$-domain. A function analytic only inside the unit disc, with no continuation past $|z|=1$ (a natural boundary, e.g. $\sum z^{2^n}$), is outside the method's reach however it behaves as $z\to 1$ radially; the $\Delta$-domain is what lets the Cauchy contour be pushed past the circle.

• "$[z^n](1-z{)}^{-\alpha }\sim n^{\alpha -1}/\Gamma (\alpha )$ holds for every $\alpha$." It holds for $\alpha \notin {\mathbb{Z}}_{\le 0}$. At $\alpha =0,-1,-2,\dots$ the function $(1-z{)}^{-\alpha }=(1-z{)}^{|\alpha |}$ is a polynomial, its coefficients are eventually zero, and the formula reports this correctly only because $1/\Gamma$ vanishes at the nonpositive integers — but the leading-term reading "$n^{\alpha -1}$" is then meaningless and must be replaced by "eventually $0$".

• "A square-root singularity always gives $n^{-3/2}$." The exponent is $-\alpha$ in $(1-z{)}^{\alpha }$. A pure $(1-z{)}^{1/2}$ ($\alpha =-\frac{1}{2}$) gives $n^{-3/2}$; but a tree generating function $y(z)\sim y(\rho )-c\sqrt{1-z/\rho }$ has its $n^{-3/2}$ from the ​ term, while its derivative $y^{\prime }(z)\sim \frac{c}{2\rho }(1-z/\rho {)}^{-1/2}$ has $\alpha =\frac{1}{2}$ and gives $n^{-1/2}$. The exponent must be read from the actual singular term, not from the word "square root".

• "Subdominant singularities never matter." Only for the leading term. The full asymptotic expansion $[z^n](1-z{)}^{-\alpha }\sim \frac{n^{\alpha -1}}{\Gamma (\alpha )}{\sum }_{j\ge 0}{e}_j(\alpha )n^{-j}$ keeps lower-order terms from the same singularity, and other singularities on $|z|=\rho$ contribute terms of the same exponential order ${\rho }^{-n}$ with different shape constants, which must be summed when several dominant singularities coexist.

Key theorem with proof Intermediate+

The signature theorem is the Flajolet-Odlyzko big-O transfer theorem: a $\Delta$-analytic function bounded by a standard scale element near its singularity has coefficients bounded by the transfer of that element, proved by deforming the Cauchy coefficient contour onto a Hankel contour wrapping the singularity at distance $1/n$ ^{[Flajolet-Odlyzko 1990]}.

Theorem (big-O transfer). Let $f$ be analytic in a $\Delta$-domain $\Delta (\varphi ,R)$ at $1$, and suppose that as $z\to 1$ in $\Delta (\varphi ,R)$, $$ f(z) = O\big((1 - z)^{-\alpha}\big),\qquad \alpha \in \mathbb{R}. $$ Then $[z^n]f=O(n^{\alpha -1})$. The same statement holds with $O$ replaced throughout by $o$, and if $f(z)\sim c(1-z{)}^{-\alpha }$ then $[z^n]f\sim c{n}^{\alpha -1}/\Gamma (\alpha )$.

Proof. By Cauchy's coefficient formula 06.01.02, $[z^n]f=\frac{1}{2\pi i}{\oint }_{\gamma }f(z)z^{-n-1}dz$ for any contour $\gamma$ around $0$ inside the domain of analyticity. Because $f$ is $\Delta$-analytic, the contour may be taken outside the unit circle except near the singularity. Fix $n$ and deform $\gamma$ to the contour ${\gamma }_n={\gamma }_n^{(1)}\cup {\gamma }_n^{(2)}\cup {\gamma }_n^{(3)}\cup {\gamma }_n^{(4)}$, a Hankel-type contour: $$ \begin{aligned} \gamma_n^{(1)} &: z = 1 + \tfrac{t}{n},\ t = e^{i\theta},\ \theta \text{ from } \phi \text{ down to } -\phi &&\text{(inner loop, radius } 1/n\text{)},\ \gamma_n^{(2,3)} &: z = 1 + \tfrac{t}{n},\ t = re^{\pm i\phi},\ r \text{ from } 1 \text{ to } \nu n &&\text{(two rays)},\ \gamma_n^{(4)} &: |z| = R_0,\ \ 1 < R_0 < R,\ \text{the large outer arc closing the contour}, \end{aligned} $$ where the inner loop has radius $1/n$ about $z=1$, the rays leave at angle $\pm \varphi$ (inside the removed sector's complement, so within $\Delta$), and the outer arc lies on a fixed circle of radius $1<R_0<R$. The hypothesis $|f(z)|\le K|1-z{|}^{-\alpha }$ on $\Delta (\varphi ,R)$ controls each piece.

Outer arc. On $|z|=R_0>1$, $|z^{-n-1}|=R_0^{-n-1}$ is exponentially small while $|f|$ is bounded (the arc stays a fixed distance from $1$), so the arc contributes $O(R_0^{-n})$, negligible against any power of $n$.

Rays. On a ray $z=1+\frac{r}{n}{e}^{i\varphi }$, $|1-z|=\frac{r}{n}$ so $|f|\le K(r/n{)}^{-\alpha }=K{n}^{\alpha }{r}^{-\alpha }$, and $|z^{-n-1}|=|1+\frac{r{e}^{i\varphi }}{n}{|}^{-n-1}\le \exp (-cr)$ for a constant $c=\cos \varphi >0$ (since $|1+w|\ge 1+\mathrm{Re}w$ gives $|1+\frac{r{e}^{i\varphi }}{n}{|}^n\ge (1+\frac{r\cos \varphi }{n}{)}^n\to e^{r\cos \varphi }$). With $dz=\frac{e^{i\varphi }}{n}dr$, the ray integral is bounded by $$ \frac{1}{2\pi}\int_1^{\infty} K n^{\alpha} r^{-\alpha}, e^{-c r},\frac{dr}{n} = \frac{K n^{\alpha - 1}}{2\pi}\int_1^{\infty} r^{-\alpha} e^{-c r},dr = O(n^{\alpha - 1}), $$ the integral converging at $\infty$ by the exponential and being finite at $r=1$.

Inner loop. On $z=1+\frac{e^{i\theta }}{n}$, again $|f|\le K{n}^{\alpha }$ on the loop of radius $1/n$, $|z^{-n-1}|$ is bounded, and the arc length is $\frac{1}{n}\cdot 2\varphi$, so the loop contributes $O(n^{\alpha }\cdot \frac{1}{n})=O(n^{\alpha -1})$. Summing the four pieces, $[z^n]f=O(n^{\alpha -1})$. Replacing the hypothesis $|f|\le K|1-z{|}^{-\alpha }$ by $|f|=o(|1-z{|}^{-\alpha })$ makes $K=K(z)\to 0$ as $z\to 1$, and the same bounds give $o(n^{\alpha -1})$. For the $\sim$ statement, apply the $o$-transfer to $f(z)-c(1-z{)}^{-\alpha }$ and use the exact coefficient asymptotic $[z^n]c(1-z{)}^{-\alpha }\sim c{n}^{\alpha -1}/\Gamma (\alpha )$ from the standard scale. $\square$

Corollary (the basic scale via the Hankel integral). The constant $1/\Gamma (\alpha )$ in the $\sim$ transfer is the Hankel representation of the reciprocal Gamma function: setting $z=1+t/n$ in $[z^n](1-z{)}^{-\alpha }=\frac{1}{2\pi i}\oint (1-z{)}^{-\alpha }{z}^{-n-1}dz$ and letting $n\to \infty$ collapses the inner loop and rays onto the Hankel contour $\mathcal{H}$, giving $[z^n](1-z{)}^{-\alpha }\sim \frac{n^{\alpha -1}}{2\pi i}{\int }_{\mathcal{H}}(-t{)}^{-\alpha }{e}^{t}dt=\frac{n^{\alpha -1}}{\Gamma (\alpha )}$, by Hankel's loop integral $\frac{1}{\Gamma (\alpha )}=\frac{1}{2\pi i}{\int }_{\mathcal{H}}{e}^t{t}^{-\alpha }dt$ of 06.01.15.

Bridge. This theorem is the foundational reason coefficient asymptotics survive the loss of poles: where 40.08.03 used the residue theorem to convert a contour integral into a finite sum at infinities of $f$, singularity analysis keeps the contour integral but reshapes it into a Hankel loop hugging a finite singularity, and the loop's size $1/n$ is exactly what manufactures the factor $n^{\alpha -1}$ — this is exactly the analytic content of the Gamma function's loop integral 06.01.15 imported into combinatorics. The meromorphic case generalises into this one: a pole of order $m$ is the standard scale element $(1-z{)}^{-m}$ with integer $\alpha =m$, whose transfer $n^{m-1}/\Gamma (m)=n^{m-1}/(m-1)!$ recovers the order-$m$ pole asymptotic of 40.08.03 term for term, so the residue calculus is the integer-exponent special case of the transfer theorem and the central insight is that pole order and singular exponent are one parameter $\alpha$. This builds toward the smooth implicit-function schema of the Advanced results, where tree generating functions acquire the half-integer exponent $\alpha =-\frac{1}{2}$ and the universal $n^{-3/2}$ law, and it appears again in 40.08.05 as the engine behind the full tree-asymptotics catalogue. Putting these together, the first principle (location fixes ${\rho }^{-n}$) of 40.08.03 and the second principle (type fixes $n^{\alpha -1}$) of this unit are the two halves of one statement read off one Cauchy integral.

Exercises Intermediate+

Advanced results Master

Beyond the basic transfer theorem, the singularity-analysis machinery extends through the full asymptotic expansion of the standard scale, the complete transfer of singular expansions, the smooth implicit-function and inverse-function schemas that produce the universal tree law, the exp-log schema for set-of-cycles structures, and the algebraic and $\exp (\sqrt{})$ singularity classes.

Theorem 1 (full asymptotic expansion of the standard scale). For $\alpha \in \mathbb{C}\setminus {\mathbb{Z}}_{\le 0}$, the coefficients of $(1-z{)}^{-\alpha }$ admit the complete expansion $$ [z^n](1 - z)^{-\alpha} = \frac{n^{\alpha - 1}}{\Gamma(\alpha)}\Big(1 + \sum_{j \ge 1}\frac{e_j(\alpha)}{n^j}\Big), $$ where each $e_j(\alpha )$ is a polynomial in $\alpha$ of degree $2j$ with $e_1(\alpha )=\frac{\alpha (\alpha -1)}{2}$, derived by applying Stirling's expansion of $\Gamma$ from 06.01.15 to $\frac{\Gamma (n+\alpha )}{\Gamma (n+1)}$. The logarithmic functions $(1-z{)}^{-\alpha }(\log \frac{1}{1-z}{)}^k$ have coefficients obtained by differentiating $\frac{n^{\alpha -1}}{\Gamma (\alpha )}$ formally in $\alpha$: $[z^n](1-z{)}^{-\alpha }\log \frac{1}{1-z}\sim \frac{n^{\alpha -1}}{\Gamma (\alpha )}(\log n-\psi (\alpha )+\gamma )$, since ${\partial }_{\alpha }\frac{n^{\alpha -1}}{\Gamma (\alpha )}=\frac{n^{\alpha -1}}{\Gamma (\alpha )}(\log n-\psi (\alpha ))$ and $\log \frac{1}{1-z}={\partial }_{\alpha }(1-z{)}^{-\alpha }{|}_{\alpha =0}$ shifted appropriately ^{[Flajolet-Odlyzko 1990, Flajolet-Sedgewick Ch. VI.2]}.

Theorem 2 (transfer of a singular expansion). Let $f$ be $\Delta$-analytic with singular expansion $f(z)={\sum }_{j=1}^J{c}_j(1-z{)}^{-{\alpha }_j}+O((1-z{)}^{-\beta })$ as $z\to 1$ in $\Delta$, with ${\alpha }_1>{\alpha }_2>\cdots$ and $\beta <{\alpha }_J$, none of the ${\alpha }_j$ in ${\mathbb{Z}}_{\le 0}$. Then term-by-term transfer is valid: $$ [z^n]f = \sum_{j=1}^{J} c_j,\frac{n^{\alpha_j - 1}}{\Gamma(\alpha_j)}\big(1 + O(1/n)\big) + O(n^{\beta - 1}), $$ the error being the transfer of the $O((1-z{)}^{-\beta })$ remainder by the big-O theorem. This is the working form of singularity analysis: compute the local expansion to the depth wanted, transfer each standard element, and the error is controlled by the remainder's exponent ^{[Flajolet-Sedgewick Ch. VI.3-VI.4]}.

Theorem 3 (smooth implicit-function schema and the universal tree law). Let $y(z)$ be the branch with $y(0)=0$ of $y=z\varphi (y)$, where $\varphi$ is analytic at $0$ with nonnegative coefficients, $\varphi (0)\ne 0$, $\varphi$ not affine, and aperiodic. If the characteristic equation $\varphi (\tau )=\tau {\varphi }^{\prime }(\tau )$ has a positive root $\tau$ within the disc of convergence of $\varphi$, then $y$ has a square-root singularity at $\rho =\tau /\varphi (\tau )$: $$ y(z) = \tau - \gamma\sqrt{1 - z/\rho} + O(1 - z/\rho),\qquad \gamma = \sqrt{\frac{2\phi(\tau)}{\phi''(\tau)}}, $$ and consequently $$ [z^n]y \sim \frac{\gamma}{2\sqrt\pi},\rho^{-n},n^{-3/2} = \sqrt{\frac{\phi(\tau)}{2\pi\phi''(\tau)}},\rho^{-n}n^{-3/2}. $$ The exponent $-\frac{3}{2}$ is universal across simple varieties of trees — binary, plane, Cayley, unary-binary, Motzkin — because all arise from the same $y=z\varphi (y)$ inversion with a smooth $\varphi$; only $\rho$ and the constant vary. This is the analytic completion of the Lagrange-inversion algebra of 40.01.07, and the flagship application is developed in 40.08.05 ^{[Flajolet-Sedgewick Ch. VI.7, VII.3]}.

Theorem 4 (exp-log schema and the constant $e^{-z}/(1-z)$ family). Structures of the form $\exp (\beta \log \frac{1}{1-z}+g(z))$ with $g$ analytic at $1$ have OGF $\sim \frac{e^{g(1)}}{(1-z{)}^{\beta }}$ near $1$, hence $[z^n]\sim \frac{e^{g(1)}}{\Gamma (\beta )}{n}^{\beta -1}$. The derangement EGF $\frac{e^{-z}}{1-z}=\exp (\log \frac{1}{1-z}-z)$ has $\beta =1$, $g(z)=-z$, $g(1)=-1$, giving $D_n/n!\to e^{-1}$; the $2$-regular graph EGF $\frac{e^{-z/2-z^2/4}}{\sqrt{1-z}}=\exp (\frac{1}{2}\log \frac{1}{1-z}-\frac{z}{2}-\frac{z^2}{4})$ has $\beta =\frac{1}{2}$, $g(1)=-\frac{3}{4}$, giving the count $\sim n!\frac{e^{-3/4}}{\sqrt{\pi n}}$. The general exp-log schema $\frac{c(z)}{(1-z{)}^{\beta }}$ with $c$ analytic at $1$ produces the algebraic-power-times-analytic-constant family, the natural habitat of set-of-cycles labelled structures ^{[Flajolet-Sedgewick Ch. VI.10, V.4]}.

Theorem 5 (algebraic and $\exp (\sqrt{})$ singularities). A function algebraic over $\mathbb{C}(z)$ has, at each singularity $\rho$, a Puiseux expansion $f(z)={\sum }_{k\ge k_0}{c}_k(1-z/\rho {)}^{k/d}$ in fractional powers with a common denominator $d$ (the local branching order); singularity analysis transfers each fractional power, giving $[z^n]f\sim {\rho }^{-n}{\sum }_k{c}_k\frac{n^{-k/d-1}}{\Gamma (-k/d)}$ over the non-integer exponents, so coefficient asymptotics of algebraic functions are always of the form ${\rho }^{-n}{n}^{p/d}$ with rational $p/d$ — never, for instance, ${\rho }^{-n}{n}^{\log n}$. Functions with an $\exp (\sqrt{})$-type singularity, such as $\exp \left(\frac{z}{1-z}\right)$ at $z=1$ (an essential singularity), fall outside the $\Delta$-analytic standard scale and require the saddle-point method of 40.08.06; the boundary between singularity analysis and the saddle-point method is precisely the boundary between algebraic-logarithmic and essential singularities ^{[Flajolet-Sedgewick Ch. VI.5, VII-VIII]}.

Synthesis. Singularity analysis is the foundational reason the second principle of coefficient asymptotics is as clean as the first: just as the location of the dominant singularity fixes the exponential factor ${\rho }^{-n}$, the type of that singularity — encoded in a single exponent $\alpha$ on the standard scale $(1-z{)}^{-\alpha }$ — fixes the subexponential factor $n^{\alpha -1}/\Gamma (\alpha )$, and the central insight is that this transfer is realised by reshaping the Cauchy coefficient contour into a Hankel loop of radius $1/n$ whose integral reproduces the reciprocal-Gamma loop integral of 06.01.15. This is exactly the generalisation of the meromorphic calculus of 40.08.03: a pole of order $m$ is the integer point $\alpha =m$ of the scale, its transfer $n^{m-1}/(m-1)!$ recovering the residue asymptotic, so the residue theorem and the transfer theorem are one statement read at integer and non-integer exponents. The bridge to the rest of the chapter is the singular-expansion process — locate $\rho$, rescale, expand locally in $(1-z/\rho )$, transfer term by term — which is dual to the symbolic-method pipeline of 40.08.01: there a structural recipe became a generating-function equation, and here that equation's local behaviour at its dominant singularity becomes the asymptotic count, so the recipe-to-series and series-to-growth halves of analytic combinatorics meet at the singular expansion.

Putting these together, the universal $n^{-3/2}$ tree law of the smooth implicit-function schema, the constant-limit derangement law of the exp-log schema, and the ${\rho }^{-n}{n}^{p/d}$ rigidity of algebraic functions are three readings of one parameter, the singular exponent, and the boundary where the method stops — essential singularities and entire functions — is exactly where the saddle-point method of 40.08.06 takes over, so this unit is the load-bearing centre of the asymptotics chapter.

Full proof set Master

Proposition 1 (basic coefficient asymptotic via Gamma and Stirling). For $\alpha \in \mathbb{C}\setminus {\mathbb{Z}}_{\le 0}$, $[z^n](1-z{)}^{-\alpha }=\frac{\Gamma (n+\alpha )}{\Gamma (\alpha )\Gamma (n+1)}=\frac{n^{\alpha -1}}{\Gamma (\alpha )}(1+O(1/n))$.

Proof. The generalised binomial series gives $(1-z{)}^{-\alpha }={\sum }_{n\ge 0}(\genfrac{}{}{0ex}{}{-\alpha }{n})(-1{)}^n{z}^n={\sum }_{n\ge 0}\left(\genfrac{}{}{0ex}{}{n+\alpha -1}{n}\right)z^n$, and $\left(\genfrac{}{}{0ex}{}{n+\alpha -1}{n}\right)=\frac{(\alpha )(\alpha +1)\cdots (\alpha +n-1)}{n!}=\frac{\Gamma (n+\alpha )}{\Gamma (\alpha )\Gamma (n+1)}$ by the rising-factorial form of $\Gamma$ from 06.01.15. For the asymptotic, Stirling's expansion $\Gamma (n+a)=\Gamma (n+1)n^{a-1}(1+\frac{(a-1)a}{2n}+O(n^{-2}))$ (a consequence of $\log \Gamma$'s asymptotic, 06.01.15) applied with $a=\alpha$ gives $\frac{\Gamma (n+\alpha )}{\Gamma (n+1)}=n^{\alpha -1}(1+O(1/n))$, whence $[z^n](1-z{)}^{-\alpha }=\frac{n^{\alpha -1}}{\Gamma (\alpha )}(1+O(1/n))$. When $\alpha \in {\mathbb{Z}}_{\le 0}$, $1/\Gamma (\alpha )=0$ and $(1-z{)}^{-\alpha }$ is a polynomial with eventually-zero coefficients, consistent with the vanishing constant. $\square$

Proposition 2 (Hankel representation of $1/\Gamma$ and the inner-loop evaluation). $\frac{1}{\Gamma (\alpha )}=\frac{1}{2\pi i}{\int }_{\mathcal{H}}{e}^t{t}^{-\alpha }dt$, where $\mathcal{H}$ is the Hankel contour coming from $+\infty$ below the positive real axis, encircling $0$, and returning above; and this is the $n\to \infty$ limit, after $z=1+t/n$, of $n^{1-\alpha }[z^n](1-z{)}^{-\alpha }$.

Proof. Hankel's loop integral for the reciprocal Gamma function is established in 06.01.15: starting from $\Gamma (\alpha )\Gamma (1-\alpha )=\pi /\sin \pi \alpha$ and the loop integral ${\int }_{\mathcal{H}}{e}^t{t}^{-\alpha }dt=\frac{2\pi i}{\Gamma (\alpha )}$ (valid for all $\alpha$, the loop avoiding the branch cut of $t^{-\alpha }$ on the negative axis), gives the stated identity. For the coefficient connection, $[z^n](1-z{)}^{-\alpha }=\frac{1}{2\pi i}\oint (1-z{)}^{-\alpha }{z}^{-n-1}dz$ over a small circle about $0$; deform onto the Hankel-type contour at distance $1/n$ from $z=1$ and substitute $z=1+t/n$, so $1-z=-t/n$, $(1-z{)}^{-\alpha }=(-t/n{)}^{-\alpha }=n^{\alpha }(-t{)}^{-\alpha }$, $z^{-n-1}=(1+t/n{)}^{-n-1}\to e^{-t}$, and $dz=dt/n$. The integral becomes $\frac{n^{\alpha }}{2\pi i}{\int }_{{\mathcal{H}}^{\prime }}(-t{)}^{-\alpha }{e}^{-t}\frac{dt}{n}=\frac{n^{\alpha -1}}{2\pi i}{\int }_{{\mathcal{H}}^{\prime }}(-t{)}^{-\alpha }{e}^{-t}dt$; reflecting $t\mapsto -t$ to the standard Hankel contour gives $\frac{n^{\alpha -1}}{\Gamma (\alpha )}(1+o(1))$. The error from $(1+t/n{)}^{-n-1}=e^{-t}(1+O(t^2/n))$ and from truncating the rays is $o(1)$ uniformly on the contour. $\square$

Proposition 3 (big-O transfer, contour estimate). If $f$ is $\Delta$-analytic at $1$ and $|f(z)|\le K|1-z{|}^{-\alpha }$ in $\Delta$, then $[z^n]f=O(n^{\alpha -1})$.

Proof. As in the Key theorem, evaluate $[z^n]f=\frac{1}{2\pi i}{\oint }_{{\gamma }_n}f(z)z^{-n-1}dz$ on the four-part Hankel contour ${\gamma }_n$ (inner loop of radius $1/n$, two rays at angle $\pm \varphi$, outer arc on $|z|=R_0\in (1,R)$). The outer arc contributes $O(R_0^{-n})$ since $|z^{-n-1}|=R_0^{-n-1}$ and $|f|$ is bounded there (the arc stays a fixed distance from $1$). Each ray contributes $O(n^{\alpha -1})$ by Proposition-style bound: $|f|\le K{n}^{\alpha }{r}^{-\alpha }$ on $z=1+\frac{r}{n}{e}^{i\varphi }$, $|z^{-n-1}|\le e^{-cr}$ with $c=\frac{1}{2}\cos \varphi$, $|dz|=\frac{dr}{n}$, so $\frac{1}{2\pi }{\int }_1^{\infty }K{n}^{\alpha }{r}^{-\alpha }{e}^{-cr}\frac{dr}{n}=\frac{K{n}^{\alpha -1}}{2\pi }{\int }_1^{\infty }{r}^{-\alpha }{e}^{-cr}dr=O(n^{\alpha -1})$. The inner loop has $|f|\le K{n}^{\alpha }$, $|z^{-n-1}|$ bounded, length $\frac{2\varphi }{n}$, contributing $O(n^{\alpha }\cdot \frac{1}{n})=O(n^{\alpha -1})$. Summing, $[z^n]f=O(n^{\alpha -1})$. The contour deformation is justified because $f$ is analytic throughout $\Delta ({\varphi }^{\prime },R)\setminus \{1\}$ for some ${\varphi }^{\prime }<\varphi$ and the original small circle about $0$ is homotopic to ${\gamma }_n$ within the analyticity region. $\square$

Proposition 4 (square-root singularity of $y=z\varphi (y)$). Under the smooth implicit-function hypotheses of Theorem 3, $y(z)=\tau -\gamma \sqrt{1-z/\rho }(1+o(1))$ with $\rho =\tau /\varphi (\tau )$, $\gamma =\sqrt{2\varphi (\tau )/{\varphi }^{\prime \prime }(\tau )}$.

Proof. Let $F(z,y)=y-z\varphi (y)$, analytic with $F(\rho ,\tau )=0$. The implicit-function theorem produces a unique analytic branch $y(z)$ with $y(0)=0$ as long as $F_y=1-z{\varphi }^{\prime }(y)\ne 0$; the branch can be continued until $F_y=0$. At the characteristic point, $F_y(\rho ,\tau )=1-\rho {\varphi }^{\prime }(\tau )=0$, and combined with $\tau =\rho \varphi (\tau )$ this is the system $\varphi (\tau )=\tau {\varphi }^{\prime }(\tau )$, $\rho =\tau /\varphi (\tau )$. There $F_z(\rho ,\tau )=-\varphi (\tau )\ne 0$ and $F_{yy}(\rho ,\tau )=-\rho {\varphi }^{\prime \prime }(\tau )\ne 0$ (positivity of $\varphi$'s coefficients and non-affineness give ${\varphi }^{\prime \prime }(\tau )>0$). Taylor-expanding $F$ at $(\rho ,\tau )$ with $F=F_y=0$ there, $$ 0 = F(z, y) = F_z(z - \rho) + \tfrac12 F_{yy}(y - \tau)^2 + O\big((z-\rho)^2, (z-\rho)(y-\tau), (y-\tau)^3\big), $$ so $(y-\tau {)}^2=\frac{-2F_z}{F_{yy}}(z-\rho )(1+o(1))=\frac{2\varphi (\tau )}{\rho {\varphi }^{\prime \prime }(\tau )}(z-\rho )(1+o(1))$. Writing $z-\rho =-\rho (1-z/\rho )$ and taking the branch with $y\uparrow \tau$ as $z\uparrow \rho$ (so $y-\tau <0$ and the square root is real for $z<\rho$), $$ y(z) = \tau - \sqrt{\frac{2\phi(\tau)}{\phi''(\tau)}}\sqrt{1 - z/\rho},(1 + o(1)), $$ a square-root singularity. Transferring the $\sqrt{1-z/\rho }$ term with $\alpha =-\frac{1}{2}$ (Proposition 1, rescaled by ${\rho }^{-n}$) gives $[z^n]y\sim -\gamma {\rho }^{-n}\frac{n^{-3/2}}{\Gamma (-1/2)}=\frac{\gamma }{2\sqrt{\pi }}{\rho }^{-n}{n}^{-3/2}$, since $\Gamma (-\frac{1}{2})=-2\sqrt{\pi }$. $\square$

Connections Master

• This unit is the type-resolution half of the asymptotics begun in its prerequisite 40.08.03: there the location of the dominant singularity fixed the exponential factor ${\rho }^{-n}$ and poles were handled by residues; here the nature of the singularity fixes the subexponential factor $n^{\alpha -1}/\Gamma (\alpha )$, and the residue calculus is recovered as the integer-exponent special case ($\alpha =m$ a pole order, $1/\Gamma (m)=1/(m-1)!$). The two units are the first and second principles of coefficient asymptotics, and the meromorphic transfer is literally the integer points of the standard scale of this unit.

• The square-root-singularity machinery is the analytic destination of the tree algebra of 40.01.07: the Lagrange-inversion closed forms for $y=z\varphi (y)$ there become, under the smooth implicit-function schema, the universal $n^{-3/2}{\rho }^{-n}$ asymptotic, and the flagship development of tree asymptotics — Cayley trees, plane trees, simply generated families, the height and profile laws — is the co-produced unit 40.08.05, which uses this unit's transfer theorems as its engine. The Catalan square-root singularity at $\frac{1}{4}$ worked here is the prototype.

• The generating functions whose singularities this unit dissects are produced by the symbolic method of 40.08.01 (and its labelled mirror 40.08.02): the supercritical-sequence schema, the tree specifications $\mathcal{Y}=\mathcal{Z}\times \varphi (\mathcal{Y})$, the set-of-cycles exp-log structures, and the derangement / $2$-regular-graph EGFs all arise from the dictionaries there, and singularity analysis is the standard route from their defining equations to their counts. The first/second-principle split is what turns the symbolic method from a bookkeeping device into a complete asymptotic theory.

• The Hankel-contour proof and the standard scale rest entirely on the Gamma function of 06.01.15: the constant $1/\Gamma (\alpha )$ is its reciprocal-loop integral, the full $1/n$ expansion comes from Stirling's asymptotic of $\log \Gamma$, and the logarithmic-scale corrections involve the digamma $\psi ={\Gamma }^{\prime }/\Gamma$. The complex-analytic substrate — Cauchy's coefficient formula 06.01.02 for the contour integral and contour deformation in the cut plane — is imported from the same Riemann-surfaces chapter. The limit-law unit 40.08.07 extends this unit's transfer of a single singular expansion to the transfer of a family of expansions depending on a secondary variable, yielding the quasi-powers / Gaussian limit theorems for combinatorial parameters.

Historical & philosophical context Master

The extraction of coefficient asymptotics from non-polar singularities begins with Darboux's method (1878), which reads the asymptotics of $[z^n]f$ off the behaviour of $f$ on its circle of convergence by subtracting a comparison function with known coefficients and bounding the remainder through integration by parts — a method requiring a smoothness hypothesis on the boundary. The square-root-singularity asymptotics of tree counts, and the $n^{-3/2}$ universal law, trace to Pólya's 1937 enumeration of trees and to the tree-counting work of Otter (1948), with the implicit-function singularity analysis sharpened by Meir and Moon (1978) for simply generated families ^{[Flajolet-Sedgewick Ch. VII]}.

The replacement of Darboux's boundary-smoothness hypothesis by analytic continuation into a slit disc and a Hankel-contour estimate is due to Philippe Flajolet and Andrew Odlyzko, whose 1990 paper Singularity analysis of generating functions ^{[Flajolet-Odlyzko 1990]} introduced the $\Delta$-domain (the "camembert" region) and proved the $O$, $o$, and $\sim$ transfer theorems for the full standard scale $(1-z{)}^{-\alpha }(\log \frac{1}{1-z}{)}^k$, giving complete asymptotic expansions where Darboux gave only leading terms. The method was systematised as the central tool of Part B of Flajolet and Sedgewick's Analytic Combinatorics (2009) ^{[Flajolet-Sedgewick Ch. VI]}, where it is positioned as the engine connecting the symbolic method to limit laws. Odlyzko's 1995 Handbook of Combinatorics survey ^{[Odlyzko 1995]} gives the comparative account of singularity analysis against Darboux's method and the saddle-point method, locating each by the type of dominant singularity it addresses.

Bibliography Master

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

@article{flajoletodlyzko1990,
  author  = {Flajolet, Philippe and Odlyzko, Andrew},
  title   = {Singularity analysis of generating functions},
  journal = {SIAM Journal on Discrete Mathematics},
  volume  = {3},
  number  = {2},
  year    = {1990},
  pages   = {216--240}
}

@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}
}

@article{darboux1878,
  author  = {Darboux, Gaston},
  title   = {M\'{e}moire sur l'approximation des fonctions de tr\`{e}s-grands nombres},
  journal = {Journal de Math\'{e}matiques Pures et Appliqu\'{e}es},
  volume  = {4},
  year    = {1878},
  pages   = {5--56, 377--416}
}

@article{meirmoon1978,
  author  = {Meir, A. and Moon, J. W.},
  title   = {On the altitude of nodes in random trees},
  journal = {Canadian Journal of Mathematics},
  volume  = {30},
  year    = {1978},
  pages   = {997--1015}
}

@article{otter1948,
  author  = {Otter, Richard},
  title   = {The number of trees},
  journal = {Annals of Mathematics},
  volume  = {49},
  year    = {1948},
  pages   = {583--599}
}