Chapter 26: Analytic Combinatorics

How does a singularity predict the number of large combinatorial objects?

A full plane binary tree is either one leaf or a root with an ordered left subtree and right subtree. Count its internal vertices, each of which has two children. If $c_n$ counts trees with $n$ internal vertices, its ordinary generating function, or OGF, satisfies

$$ C(z)=\sum_{n\geq0}c_nz^n=1+zC(z)^2, \qquad C(z)=\frac{1-\sqrt{1-4z}}{2z}. $$

The apparent singularity at $z=0$ is removable: the selected solution has $C(0)=1$. The square root becomes singular at $\rho=1/4$. That location predicts an exponential factor $\rho^{-n}=4^n$; the square-root shape predicts a further factor $n^{-3/2}$. Together they suggest

$$ c_n\sim L_n:=\frac{4^n}{\sqrt{\pi}\,n^{3/2}}. $$

The constant and exponent require justification. We will obtain them from both an exact coefficient formula and a local analytic expansion, distinguish a relative approximation from an absolute error bound, and check what changes for entire functions and several dominant singularities.

The chapter foundation is this concrete problem and the final investigation, which restates the formulas needed for its calculations. Sections 26.1–26.10 are optional graduate extensions. The published prerequisites Generating functions and recurrence relations, Special counting sequences and lattice paths, and Combinatorial species and structured enumeration supply the combinatorial grammars. Complex analysis is needed for contour arguments; advanced theorems used without full proof are identified explicitly.

26.1 Complex-analytic foundations for generating functions

Optional advanced elective extension; not required to complete the chapter foundation. A formal generating function supports coefficient manipulations without referring to convergence. Analytic combinatorics adds a second interpretation: the same power series is a holomorphic function in a neighborhood of zero. This interpretation is available only when its radius of convergence is positive.

Write $F(z)=\sum_{n\geq0}f_nz^n$, where $[z^n]F(z)=f_n$. The Cauchy–Hadamard formula states

$$ \frac1\rho=\limsup_{n\to\infty}|f_n|^{1/n}, $$

with $1/\infty=0$ and $1/0=\infty$. It follows from the root test: for $|z|\lt\rho$ the terms are eventually dominated by a geometric sequence, while for $|z|\gt\rho$ they fail to tend to zero along a subsequence. The limsup permits oscillation and zero coefficients.

For $0\lt r\lt\rho$, Cauchy's coefficient formula and its angular version give

$$ f_n=\frac1{2\pi i}\int_{|z|=r}\frac{F(z)}{z^{n+1}}\,dz =\frac1{2\pi r^n}\int_{-\pi}^{\pi}F(re^{i\theta})e^{-in\theta}\,d\theta. $$

The circle is traversed counterclockwise. One proof substitutes the uniformly convergent series on that circle; integrating $e^{i(k-n)\theta}$ keeps only $k=n$. The triangle inequality then yields $|f_n|\leq M(r)/r^n$, where $M(r)=\max_{|z|=r}|F(z)|$. For nonnegative real coefficients, $M(r)=F(r)$.

Solved example. For $F(z)=1/(1-2z)$, the radius is $1/2$ and $f_n=2^n$. For $F(z)=e^z$, the radius is infinite and $f_n=1/n!$. The second example has no finite dominant singularity; its useful contour radius will grow with $n$ instead of approaching a fixed boundary.

For an exponential generating function, or EGF, $A(z)=\sum a_nz^n/n!$, the analytic coefficient is $f_n=a_n/n!$. Any estimate for $[z^n]A$ must be multiplied by $n!$ to estimate labeled counts. For permutations the OGF $\sum n!z^n$ has radius zero, while their EGF is $1/(1-z)$ and has radius one. Choosing the appropriate generating function is part of the analysis.

Exercise. Bound $[z^n]e^z$ using Cauchy's inequality and choose the best positive radius for that bound. Hint: minimize $e^r/r^n$ for $n\geq1$. Solution: differentiating its logarithm gives $1-n/r=0$, so $r=n$ and $1/n!\leq e^n/n^n$. This bound has the correct main exponential factor but misses the eventual factor $1/\sqrt{2\pi n}$.

26.2 Asymptotic notation and coefficient growth

Optional advanced elective extension; not required to complete the chapter foundation. Let $g_n\gt0$ eventually. The statement $f_n=O(g_n)$ means $|f_n|\leq Mg_n$ for some constant $M$ and all sufficiently large $n$. The statement $f_n=o(g_n)$ means $f_n/g_n\to0$. The statement $f_n\sim g_n$ means $f_n/g_n\to1$. For positive sequences, $f_n=\Theta(g_n)$ means that both upper and positive lower constant multiples hold eventually.

If $f_n=K\rho^{-n}n^\beta(1+O(1/n))$ with $K\gt0$, then $f_n\sim K\rho^{-n}n^\beta$ and its relative error is $O(1/n)$. Its absolute error is $O(\rho^{-n}n^{\beta-1})$, which may grow very rapidly. Neither the asymptotic symbol nor an unspecified big-O constant gives a numerical accuracy guarantee at a particular small $n$.

For Catalan numbers, the exact expression is

$$ c_n=\frac1{n+1}\binom{2n}{n}. $$

It follows by expanding the square root in the opening formula, or by Lagrange inversion applied to $C-1=z(1+(C-1))^2$. The first values are $1,1,2,5,14,42$. These exact values provide a reference against which to assess an approximation.

Exercise. If $f_n=3^nn^{-2}(1+2/n+O(n^{-2}))$, determine the relative and absolute errors of the estimate $3^nn^{-2}$. Hint: invert $1+2/n+O(n^{-2})$. Solution: the estimate divided by $f_n$, minus one, is $-2/n+O(n^{-2})$. The estimate minus $f_n$ is $-2\cdot3^nn^{-3}+O(3^nn^{-4})$. Relative accuracy improves while absolute error grows.

26.3 Singularities of generating functions

Optional advanced elective extension; not required to complete the chapter foundation. A singular point is a point where the chosen analytic germ cannot extend holomorphically to a neighborhood. A dominant singularity lies on its circle of convergence. A pole of order $m$ has a local principal part proportional to $(1-z/\rho)^{-m}$; a square-root branch point has a fractional-power expansion. A removable apparent singularity contributes no boundary obstruction.

Solved contrast. The functions $1/(1-z)$ and $1/(1-z)^2$ share radius one, but their coefficients are $1$ and $n+1$ respectively. Location alone does not determine the polynomial factor. The function $C(z)$ is finite at $z=1/4$, where $C(1/4)=2$, but its square-root branch is still singular; divergence of the function is not necessary for singularity.

Several dominant points can cause oscillation. The partial fractions

$$ \frac1{1-z^2}=\frac12\left(\frac1{1-z}+\frac1{1+z}\right) $$

give coefficients $(1+(-1)^n)/2$, equal to one for even $n$ and zero for odd $n$. Both $1$ and $-1$ are dominant poles. Keeping only the positive pole would give the incorrect answer $1/2$ at every size.

The diagram compares normalized complex planes. In the left panel $w=z/\rho=4z$, so the Catalan branch point is at $w=1$. In the right panel $w=z$, and both poles are at $w=\pm1$. Solid circles are convergence boundaries; dashed circles of radius $0.65$ are permissible coefficient contours, not singular sets. The left red ray marks the chosen square-root branch cut beginning at $1$.

For nonnegative coefficients and finite positive radius, Pringsheim's theorem guarantees a singularity on the positive real axis at the radius. It does not guarantee uniqueness. This theorem is used as background, without its complex-analytic proof; the periodic example satisfies its conclusion while also having a negative dominant point.

Exercise. Find all dominant singularities and coefficients of $1/(1-8z^3)$. Hint: its geometric expansion has powers divisible by three. Solution: the singularities are $\tfrac12\omega^j$ for $j=0,1,2$, where $\omega=e^{2\pi i/3}$. The coefficient is $8^m$ when $n=3m$, and zero otherwise. Their common modulus is $1/2$, so the limsup coefficient root is $2$ even though an ordinary limit does not exist.

26.4 Singularity analysis and transfer theorems

Optional advanced elective extension; not required to complete the chapter foundation. Transfer theorems make the passage from local singular powers to coefficient estimates precise. The local expansion must hold in a complex neighborhood large enough for a contour deformation, rather than merely along the real axis.

Normalize $w=z/\rho$. For $R\gt1$ and $0\lt\phi\lt\pi/2$, use a dented domain

$$ \Delta(R,\phi)=\{w:|w|\lt R,\ w\neq1,\ |\arg(w-1)|\gt\phi\}. $$

It excludes a wedge pointing outwards from $1$. Assume that $F(\rho w)$ is holomorphic there, with its chosen branch, and that its expansion holds as $w\to1$ inside this domain. These hypotheses control other points of modulus one as well as continuation past the circle away from the dent.

The basic singular model, for $\alpha\notin\{0,-1,-2,\ldots\}$, has

$$ [z^n]\,(1-z/\rho)^{-\alpha} =\rho^{-n}\frac{\Gamma(n+\alpha)}{\Gamma(\alpha)\Gamma(n+1)} \sim\rho^{-n}\frac{n^{\alpha-1}}{\Gamma(\alpha)}. $$

Here $\Gamma$ extends factorials and satisfies $\Gamma(s+1)=s\Gamma(s)$ and $\Gamma(1/2)=\sqrt\pi$. The exact coefficient follows from the generalized binomial series; the gamma ratio follows from Stirling's expansion. For the excluded values, the model is a polynomial and its coefficients eventually vanish.

A useful sufficient transfer statement is: if, in this dented domain,

$$ F(z)=P(1-z/\rho)+K(1-z/\rho)^{-\alpha} +O\left((1-z/\rho)^{-\alpha+\varepsilon}\right), $$

where $P$ is a polynomial, $K\neq0$, $\alpha$ is real and not excluded above, and $\varepsilon\gt0$, then

$$ [z^n]F(z)=K\rho^{-n}\frac{n^{\alpha-1}}{\Gamma(\alpha)} \left(1+O\left(n^{-\min(1,\varepsilon)}\right)\right). $$

The polynomial contributes nothing for sufficiently large $n$. The estimate is about coefficients of the analytic remainder, not a rule that permits arbitrary pointwise errors to be transferred.

Proof mechanism sketch. Deform Cauchy's contour into the dented domain, using a small loop and two paths near the singularity. On the scale $1-z/\rho=t/n$, the factor $z^{-n-1}$ becomes $\rho^{-n-1}e^t$ to leading order, and the singular power supplies $n^\alpha$. The contour integral produces $1/\Gamma(\alpha)$; the remainder and distant paths require uniform bounds. The full contour estimates are omitted. This established method is developed in Flajolet and Odlyzko, Singularity Analysis of Generating Functions (1990).

Solved Catalan application. Put $w=1-4z$. Near $w=0$,

$$ C(z)=\frac{2(1-\sqrt w)}{1-w} =2-2w^{1/2}+2w+O(w^{3/2}). $$

The selected square root is analytic on a slit plane, and the apparent singularity at zero is removed, so an appropriate dented domain exists. Take $P(w)=2+2w$, $K=-2$, $\alpha=-1/2$, and $\varepsilon=1$. Since $\Gamma(-1/2)=-2\sqrt\pi$, transfer gives $c_n=L_n(1+O(1/n))$. The positive sign comes from the two negative factors, not from ignoring the singular coefficient.

Exercise. Estimate $[z^n]\,(1-3z)^{-3/2}$. Hint: $\Gamma(3/2)=\sqrt\pi/2$. Solution: the estimate is $(2/\sqrt\pi)3^nn^{1/2}$. A slit domain beyond the unique branch point $1/3$ satisfies the analytic hypothesis. The basic gamma-ratio expansion also gives a relative error $O(1/n)$.

26.5 Saddle-point method

Optional advanced elective extension; not required to complete the chapter foundation. For an entire function, there is no finite singularity to approach. Cauchy's circle can instead move with $n$ so that the integrand concentrates near a stationary point. The same strategy also applies to some finite-radius functions with more rapid singular growth.

Assume $F(r)\gt0$ on the positive radii under consideration. Define

$$ a(r)=r\frac{F'(r)}{F(r)},\qquad b(r)=r\,a'(r). $$

The derivative of $\log F(r)-n\log r$ vanishes when $a(r)=n$. On the circle of that radius, a local Taylor expansion gives

$$ \log\frac{F(re^{i\theta})}{F(r)} =ia(r)\theta-\frac12b(r)\theta^2+\text{higher terms}. $$

The factor $e^{-in\theta}$ in Cauchy's formula cancels the linear term. If the higher terms are small on a sufficiently wide central arc and the remaining arcs are negligible, a Gaussian integral predicts

$$ [z^n]F(z)\sim\frac{F(r)}{r^n\sqrt{2\pi b(r)}},\qquad a(r)=n. $$

The saddle equation alone is insufficient; localization and tail bounds are part of the proof. Section 26.6 gives explicit sufficient hypotheses.

Solved example with bounds. For $F(z)=e^z$, $a(r)=b(r)=r$, so take $r=n$. Its angular integrand, after removing the factor $e^n$, is $\exp(n(e^{i\theta}-1-i\theta))$. On $|\theta|\leq\delta=n^{-2/5}$, Taylor's formula gives exponent $-n\theta^2/2+O(n|\theta|^3)$, with uniform remainder $O(n^{-1/5})=o(1)$. The central arc has Gaussian width $n^{-1/2}$ and $\delta\sqrt n=n^{1/10}\to\infty$.

For the rest of the circle, the modulus is $e^{-n(1-\cos\theta)}$. The inequality $1-\cos\theta\geq2\theta^2/\pi^2$ for $|\theta|\leq\pi$ bounds it by $e^{-cn^{1/5}}$ outside the central arc, for a fixed $c\gt0$. This is negligible compared with the central integral of order $n^{-1/2}$. Consequently

$$ \frac1{n!}\sim\frac{e^n}{n^n\sqrt{2\pi n}}, $$

recovering the leading Stirling formula from the coefficient integral. These estimates justify the leading equivalence; they do not by themselves establish the sharper correction in Section 26.2.

There is also a probabilistic interpretation. For nonnegative coefficients and finite $F(r)$, define $\Pr_r(N=k)=f_kr^k/F(r)$. Differentiating its normalization gives $\mathbb E_rN=a(r)$ and $\operatorname{Var}_rN=b(r)$. The saddle tunes the mean to $n$. A Gaussian local probability at that mean, when justified, is another way to understand the denominator $\sqrt{2\pi b(r)}$.

Exercise. For $F(z)=e^{2z}$, find the saddle estimate and compare with the exact coefficient. Hint: $a(r)=b(r)=2r$. Solution: $r=n/2$, giving $2^ne^n/(n^n\sqrt{2\pi n})$. The exact coefficient is $2^n/n!$, consistent with Stirling. Rescaling $z$ reduces its localization proof to the preceding one.

26.6 Hayman's admissibility method

Optional advanced elective extension; not required to complete the chapter foundation. Hayman's method packages the local and global estimates required by a saddle into verifiable conditions. Its classical origin is Hayman, A Generalisation of Stirling's Formula (1956). We state a sufficient version with an explicit growing central Gaussian window and prove its consequence directly.

Let $F$ be holomorphic for $|z|\lt R$, where $R$ may be infinite, and positive on real radii sufficiently near $R$. Define $a,b$ as before. As $r\to R$ from below, or $r\to\infty$ when $R=\infty$, require:

1. Capture: $a(r)\to\infty$ and $b(r)\to\infty$.
2. Locality: for some $\delta(r)\to0$ with $\delta(r)\sqrt{b(r)}\to\infty$, uniformly on $|\theta|\leq\delta(r)$,

$$ F(re^{i\theta})=F(r)\exp\left(ia(r)\theta-\frac12b(r)\theta^2\right)(1+o(1)). $$

1. Decay: uniformly on $\delta(r)\leq|\theta|\leq\pi$,

$$ |F(re^{i\theta})|=o\left(\frac{F(r)}{\sqrt{b(r)}}\right). $$

If radii $r_n$ satisfy $a(r_n)=n$ and tend to $R$, these conditions imply the saddle estimate from Section 26.5. Proof: split the angular integral at $\delta(r_n)$. Locality, followed by $t=\sqrt b\,\theta$, turns the central part into $F(r_n)\sqrt{2\pi/b(r_n)}(1+o(1))$. Its normalized interval tends to the whole real line. Decay bounds the outer integral by $o(F(r_n)/\sqrt b)$. Including the factor $1/(2\pi r_n^n)$ proves the claim.

Solved involution example. Chapter 25 gives the EGF $I(z)=e^{z+z^2/2}$ and labeled counts $a_n=n![z^n]I(z)$. To avoid confusing those counts with the saddle function $a(r)$, write the counts as $\iota_n$ in this section. Here

$$ a(r)=r+r^2,\qquad b(r)=r+2r^2,\qquad r_n=\frac{\sqrt{1+4n}-1}{2}. $$

Capture is immediate. Choose $\delta=r^{-4/5}$. Expanding the logarithm on the central arc gives remainder $O((r+r^2)\delta^3)=O(r^{-2/5})$, while $\delta\sqrt b$ is of order $r^{1/5}$ and tends to infinity. This proves locality.

For decay, the exact modulus ratio is

$$ \frac{|I(re^{i\theta})|}{I(r)} =\exp\bigl(-r(1-\cos\theta)-r^2\sin^2\theta\bigr). $$

On $\delta\leq|\theta|\leq\pi/2$, $|\sin\theta|\geq2|\theta|/\pi$, so this is at most $e^{-cr^{2/5}}$. On $\pi/2\leq|\theta|\leq\pi$, it is at most $e^{-r}$. Both are $o(1/r)=o(1/\sqrt b)$. All three conditions are now checked, so

$$ \iota_n\sim H_n:=n!\frac{\exp(r_n+r_n^2/2)} {r_n^n\sqrt{2\pi(r_n+2r_n^2)}}. $$

At $n=10$, the exact count is $9496$ and $H_{10}/9496-1\approx0.0141181$. This finite comparison is a check, whereas the admissibility estimates prove the limit.

Exercise. Explain why applying the single-saddle formula to $e^{z^2}$ is invalid. Hint: compare its modulus at angles $0$ and $\pi$. Solution: the modulus at $\pi$ equals its value at zero, so decay fails. Its odd coefficients are zero. For even $n$, both saddle neighborhoods contribute equally; ignoring the second loses a factor of two. Thus nonnegative coefficients and a solvable saddle equation do not establish admissibility.

26.7 Darboux's method

Optional advanced elective extension; not required to complete the chapter foundation. Darboux's method separates explicit singular terms from a remainder that is sufficiently smooth on the convergence circle. It uses decay of Fourier coefficients of that remainder, rather than continuation through a dented complex neighborhood.

Normalize the radius to one. Suppose $R$ is holomorphic in the unit disk, extends continuously to the closed disk, and has a periodic $C^k$ boundary function $\theta\mapsto R(e^{i\theta})$. Uniform radial convergence and the boundary coefficient integral give

$$ [z^n]R(z)=\frac1{2\pi}\int_{-\pi}^{\pi}R(e^{i\theta})e^{-in\theta}\,d\theta =o(n^{-k})\quad(n\to\infty). $$

To prove the estimate, integrate by parts $k$ times; periodic boundary terms cancel. The remaining integral is a Fourier coefficient of the continuous $k$th derivative, which tends to zero by the Riemann–Lebesgue lemma. That elementary Fourier-analysis result is used without proof. At radius $\rho$, rescaling introduces a factor $\rho^{-n}$.

After subtracting explicit singular models, this lemma controls their remainder. It is not enough to say that the original function is smooth away from a few points: the remainder after subtraction must meet the boundary differentiability requirement at those points too. Flajolet and Odlyzko, Section 5 contrasts this boundary method with singularity analysis.

Solved example. Let

$$ F(z)=\frac{1+z}{\sqrt{1-z}}+R(z),\qquad R(z)=\sum_{m\geq1}\frac{z^m}{m^4}. $$

The series for the boundary value of $R$ and its first two angular derivatives converge absolutely and uniformly, since $\sum m^2/m^4$ converges. Thus $R$ has a $C^2$ boundary value and contributes $o(n^{-2})$; its known exact coefficient $n^{-4}$ is even smaller.

Rewrite the singular part as $2(1-z)^{-1/2}-(1-z)^{1/2}$. The generalized binomial coefficients and their gamma-ratio estimates give leading coefficient $2/(\sqrt\pi\sqrt n)$; the second model has coefficients of order $n^{-3/2}$. The smooth-remainder lemma therefore proves

$$ [z^n]F(z)\sim\frac2{\sqrt{\pi n}}. $$

For an exact check at $n=2$, the singular part contributes $3/8+1/2=7/8$, while $R$ contributes $1/16$, giving $15/16$. This check does not replace the large-$n$ estimate.

Exercise. After subtracting a leading square-root singular model with coefficient scale $n^{-3/2}$, what integer differentiability order $k$ of the remainder suffices to make it negligible by this lemma? Hint: compare $n^{-k}$ with $n^{-3/2}$. Solution: $k=2$ suffices because $o(n^{-2})=o(n^{-3/2})$. The conclusion $o(n^{-1})$ from $k=1$ would not suffice on its own.

26.8 Multivariate analytic combinatorics

Optional advanced elective extension; not required to complete the chapter foundation. A multivariate generating function records several sizes or statistics. Write $F(x,y)=\sum_{r,s\geq0}f_{r,s}x^ry^s$. Cauchy's formula becomes an integral over two circles, and growth depends on the direction $(r,s)$ in which the coefficient indices tend to infinity.

For a rational function $F=G/H$, possible singularities form the variety $H(x,y)=0$, after cancellations are considered. At a smooth point, $\nabla H\neq0$. Positive critical points for a direction often satisfy

$$ H(x,y)=0,\qquad \frac rs=\frac{xH_x(x,y)}{yH_y(x,y)}. $$

These equations produce candidates. Minimality in the domain of convergence, numerator noncancellation, competing points, and a nondegenerate reduced saddle must also be checked before applying a smooth-point asymptotic theorem. The established general framework is Pemantle and Wilson, Asymptotics of Multivariate Sequences, Part I: Smooth Points of the Singular Variety. We prove the following example directly instead of invoking a general formula without its hypotheses.

Solved example. Let $F(x,y)=1/(1-x-y)$. Expanding $\sum_{N\geq0}(x+y)^N$ gives $f_{r,s}=\binom{r+s}{r}$. Put $N=r+s$, $p=r/N$, and $q=s/N$. Assume $p,q$ stay bounded away from zero as $N\to\infty$. The critical point is $(x,y)=(p,q)$, since $H_x=H_y=-1$ and $x+y=1$.

The positive point is smooth, the numerator is nonzero, and it lies on the boundary of absolute convergence $|x|+|y|\lt1$. On the torus $|x|=p,|y|=q$, equality $x+y=1$ forces both coordinates to be positive real by equality in the triangle inequality. Hence it is the only singular point on that torus. On the positive curve $y=1-x$, the second derivative of $-r\log x-s\log(1-x)$ is $r/x^2+s/(1-x)^2\gt0$, checking nondegeneracy.

Using Stirling directly now yields, uniformly when $p$ lies in a fixed compact subinterval of $(0,1)$,

$$ \binom Nr=\frac{p^{-r}q^{-s}}{\sqrt{2\pi Npq}} \left(1+O(N^{-1})\right). $$

For $r=s=n$, this becomes $\binom{2n}{n}\sim4^n/\sqrt{\pi n}$. Different directions select different critical points; there is no single nearest singularity that answers every direction. If one index remains fixed, the assumptions fail and a different approximation is needed.

Exercise. Estimate $[x^ny^{2n}]F(x,y)$. Hint: use $p=1/3,q=2/3,N=3n$. Solution: the estimate is

$$ \binom{3n}{n}\sim\frac{\sqrt3}{2\sqrt{\pi n}}\left(\frac{27}{4}\right)^n. $$

Both coordinates tend to infinity with their ratio fixed, so the interior-direction condition holds. Substituting only the diagonal point $(1/2,1/2)$ would give the wrong exponential factor.

26.9 Quasi-powers and limiting distributions

Optional advanced elective extension; not required to complete the chapter foundation. Mark a statistic $K$ by $u$ in a bivariate generating function $F(z,u)$. For a uniformly chosen object of size $n$, its probability generating function is

$$ P_n(u)=\frac{[z^n]F(z,u)}{[z^n]F(z,1)}. $$

Use a consistent OGF or EGF in numerator and denominator; the common factor $n!$ cancels for an EGF. The moment generating function is $M_n(s)=P_n(e^s)$. Its logarithm has derivatives at zero equal to the mean and variance.

A sufficient quasi-powers form is

$$ M_n(s)=\exp(nU(s)+V(s))(1+O(n^{-1})), $$

uniformly in a fixed complex neighborhood of zero, with analytic $U,V$, $U(0)=V(0)=0$, and $\sigma^2=U''(0)\gt0$. Then, with $\mu=U'(0)$,

$$ \mathbb E K_n=n\mu+V'(0)+O(n^{-1}),\qquad \operatorname{Var}(K_n)=n\sigma^2+V''(0)+O(n^{-1}), $$

and $(K_n-n\mu)/(\sigma\sqrt n)$ converges in distribution to a standard normal variable. This is a sufficient form of the quasi-powers principle associated with Hwang, On Convergence Rates in the Central Limit Theorems for Combinatorial Structures (1998). No convergence-rate claim is needed here.

Proof outline. Uniform analyticity of the relative error lets Cauchy's estimates control its derivatives on a smaller neighborhood, proving the two derivative formulas. For fixed real $t$, substitute $s=it/(\sigma\sqrt n)$ and subtract the centering term. Taylor expansion gives $nU(s)-itn\mu/(\sigma\sqrt n)=-t^2/2+O(n^{-1/2})$, while $V(s)=O(n^{-1/2})$. Thus the characteristic functions tend to $e^{-t^2/2}$. Lévy's continuity theorem, whose probability-theoretic proof is omitted, gives the normal limit. A real-axis approximation with no uniform complex control would not justify the derivative step.

Solved example. For binary words, mark the number of ones:

$$ F(z,u)=\frac1{1-z(1+u)},\qquad P_n(u)=\left(\frac{1+u}{2}\right)^n. $$

Thus $U(s)=\log((1+e^s)/2)$ and $V=0$, with the analytic logarithm chosen near zero. Differentiation gives $U'(0)=1/2$ and $U''(0)=1/4$. The statistic is exactly binomial, with mean $n/2$ and variance $n/4$, and $(K_n-n/2)/(\sqrt n/2)$ tends to the standard normal law.

A singularity perturbation often generates such a form: if coefficients uniformly behave like $B(u)\rho(u)^{-n}n^\beta(1+O(1/n))$, with analytic nonzero $B,\rho$ near $u=1$ and a fixed exponent $\beta$, division gives $U(s)=\log(\rho(1)/\rho(e^s))$ and $V(s)=\log(B(e^s)/B(1))$. The uniformity and branch choices are substantive hypotheses.

Exercise. Can the number of leaves in a full binary tree with $n$ internal vertices have this nondegenerate normal limit? Hint: count edges using children and using total vertices. Solution: if there are $\ell$ leaves, then $2n=n+\ell-1$, so $\ell=n+1$ deterministically. Its variance is zero, violating $U''(0)\gt0$. Having a marking variable does not by itself produce a Gaussian limit.

26.10 Asymptotics of trees, permutations, and partitions

Optional advanced elective extension; not required to complete the chapter foundation. The family, size convention, and use of labels determine which coefficient problem is being solved. Trees need not all have the same generating function; partitions of an integer differ from partitions of a labeled set.

For full plane binary trees with $n$ internal vertices, $c_n\sim4^n/(\sqrt\pi n^{3/2})$. For nonplane rooted trees with all $n$ vertices labeled, Chapter 25 gives $A(z)=ze^{A(z)}$ and the exact count $n^{n-1}$. Consequently Stirling gives the normalized EGF coefficient

$$ [z^n]A(z)=\frac{n^{n-1}}{n!} \sim\frac{e^n}{\sqrt{2\pi}\,n^{3/2}}. $$

Its radius is $1/e$, rather than $1/4$. The local square root can be checked from the equation: write $A=1-v$, so $\log(ez)=\log(1-v)+v=-v^2/2+O(v^3)$. On the real branch approaching $A=1$, this gives

$$ A(z)=1-\sqrt2\,(1-ez)^{1/2}+O(1-ez). $$

The exponent matches the binary-tree exponent despite a different exponential scale and labeling convention. A complete continuation-domain proof for this implicit function is omitted; its coefficient equivalence above is already independently proved by its exact formula and Stirling.

Permutations have labeled count $n!$ and EGF $1/(1-z)$; its coefficient is exactly $1$, so the pole causes no additional polynomial correction. If fixed points are forbidden, inclusion–exclusion gives derangements

$$ d_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!},\qquad D(z)=\frac{e^{-z}}{1-z},\qquad d_n\sim\frac{n!}{e}. $$

Solved probability application. The alternating-series remainder proves $|d_n/n!-e^{-1}|\leq1/(n+1)!$. At $n=4$, $d_4=9$ and the probability of no fixed point is $9/24=0.375$, close to $e^{-1}\approx0.367879$. In this example an explicit finite error bound is available, unlike a bare asymptotic equivalence. Marking fixed points gives EGF $e^{(u-1)z}/(1-z)$, whose normalized coefficient tends to $e^{u-1}$ near $u=1$; this is the probability generating function of a Poisson variable of mean one. The limiting statistic has bounded variance, so the linear-variance Gaussian hypotheses do not apply.

Let $p(n)$ count integer partitions, where summands have no order. Choosing independently the multiplicity of each part size gives

$$ P(z)=\prod_{k\geq1}(1-z^k)^{-1},\qquad p(n)\sim\frac1{4\sqrt3\,n}\exp\left(\pi\sqrt{\frac{2n}{3}}\right). $$

The second formula is the established Hardy–Ramanujan asymptotic; their 1918 paper, Section 1.4 states it and develops the analytic argument. Its growth is faster than every fixed power of $n$ but slower than $b^n$ for every $b\gt1$. Taking $n$th roots shows that $P$ has radius one.

Proof mechanism sketch, not a complete proof. The modular transformation gives, for real $t\to0^+$,

$$ P(e^{-t})\sim\sqrt{\frac{t}{2\pi}}\exp\left(\frac{\pi^2}{6t}-\frac{t}{24}\right). $$

In the coefficient integral, the main exponent is $nt+\pi^2/(6t)$; stationarity locates $t\approx\pi/\sqrt{6n}$ and predicts the exponential $e^{\pi\sqrt{2n/3}}$. Recovering the prefactor and bounding the other arcs require further analysis. Singularities at roots of unity prevent treating $1$ as a single isolated algebraic singularity with a dented continuation domain. The modular transformation and the required arc estimates are omitted prerequisites, so the real-axis estimate alone is not presented as a proof of the coefficient formula.

For comparison, partitions of a labeled set are counted by Bell numbers, whose EGF is $\exp(e^z-1)$. This is a different, entire generating function; the Hardy–Ramanujan estimate must not be applied to it.

Exercise. Compute $p(5)$ and explain why a good asymptotic estimate need not be close at this size. Hint: classify by largest part. Solution: the seven partitions are $5$, $4+1$, $3+2$, $3+1+1$, $2+2+1$, $2+1+1+1$, and $1+1+1+1+1$. The leading estimate is approximately $8.94$, about $27.7\%$ high. Equivalence as $n\to\infty$ supplies no small-size accuracy guarantee.

Compare exact coefficients with a justified asymptotic estimate

The investigation uses full plane binary trees, counted by internal vertices. Its exact coefficients are $c_n=\binom{2n}{n}/(n+1)$, and its two candidate estimates are

$$ L_n=\frac{4^n}{\sqrt\pi\,n^{3/2}},\qquad L_n^{(1)}=L_n\left(1-\frac9{8n}\right)\quad(n\geq1). $$

The corrected estimate is intended for large $n$; it is negative at $n=1$ and is not a probability or an exact count. The tasks below connect a structural grammar, a complex singularity, and a controlled expansion. They can be completed without the optional extensions using the exact formula and the stated Stirling expansion.

Part A: warm-up, 15 points. Use $c_n=\sum_{k=0}^{n-1}c_kc_{n-1-k}$ to compute coefficients through $n=5$, then obtain $c_{10}$ from the exact formula. Explain what is being counted and whether labels or factorial normalization are involved. Hint: an internal root has two ordered subtrees.

Worked solution. The values are $1,1,2,5,14,42$, and $c_{10}=16796$. These count unlabeled plane tree shapes with $n$ internal vertices and $n+1$ leaves. Their OGF coefficients are the actual counts, so no $n!$ factor is introduced. Ordering the two children is part of the structure, not an arbitrary presentation order.

Part B: analytic interpretation, 20 points. Solve the quadratic equation, select the solution with constant term one, and locate its singularity. Explain why a square root that stays finite can still be singular. Compare with $1/(1-z^2)$. Hint: distinguish a removable expression at zero from a branch obstruction at $1/4$.

Solution outline. The selected solution is $(1-\sqrt{1-4z})/(2z)$ with the square root equal to one at zero. Its series removes the apparent pole at zero. Near $1/4$, writing $w=1-4z$ gives $C=2-2w^{1/2}+2w+O(w^{3/2})$. The fractional-power term prevents a holomorphic Taylor expansion there. The location predicts $4^n$, and the singular exponent predicts $n^{-3/2}$ once transfer hypotheses are checked. In contrast, $1/(1-z^2)$ has two dominant poles and coefficients $(1+(-1)^n)/2$; its positive pole alone does not determine its coefficients.

Part C: proof, 25 points. Starting from the supplied logarithmic Stirling expansion, derive

$$ \frac{c_n}{L_n}=1-\frac9{8n}+\frac{145}{128n^2}+O(n^{-3}). $$

Deduce the two signed relative-error orders. Hints: first analyze $\binom{2n}{n}$; then multiply by $n/(n+1)$; finally invert the resulting ratio.

Worked solution. The logarithmic correction for the central binomial coefficient is $1/(24n)-2/(12n)=-1/(8n)$. Exponentiating gives the multiplicative correction $1-1/(8n)+1/(128n^2)+O(n^{-3})$. Multiplication by $1-1/n+1/n^2+O(n^{-3})$ gives the displayed coefficients. Inverting shows $L_n/c_n-1=9/(8n)+O(n^{-2})$. Subtracting the corrected estimate and dividing by $c_n$ gives $L_n^{(1)}/c_n-1=-145/(128n^2)+O(n^{-3})$. This proves both convergence and improvement in order. It does not identify an explicit finite threshold for a requested tolerance because the remaining big-O constant has not been bounded numerically.

Part D: computational comparison, 25 points. Compute the two errors with exact integer $c_n$. Report signed errors as ratios, rather than percentages, and compare $n(L_n/c_n-1)$ with $9/8$, and $n^2(L_n^{(1)}/c_n-1)$ with $-145/128$. Hint: evaluate $\log c_n=\log\Gamma(2n+1)-2\log\Gamma(n+1)-\log(n+1)$ only if your arithmetic cannot retain the exact integer; guard against cancellation when subtracting nearly equal ratios.

Verified numerical reference. The following values are rounded; use more precision internally. At $n=25$ the exact count is $4861946401452$, providing an integer cross-check.

Solution outline. The scaled errors approach $9/8=1.125$ and $-145/128=-1.1328125$, as proved in Part C. A reproducible computation can generate the exact coefficients by the integer recurrence $(n+2)c_{n+1}=2(2n+1)c_n$, beginning at $c_0=1$, then evaluate each estimate with at least 40 decimal digits. Increasing precision should leave the displayed rounded digits stable. These finite calculations validate implementation and illustrate the theorem; they are not an independent proof of the limits.

Part E: method selection and application, 15 points. Explain why Catalan singularity analysis cannot be applied unchanged to the involution EGF $e^{z+z^2/2}$. State its saddle and compare one exact count with its estimate. Describe one use for the Catalan estimate in computing.

Worked solution. The involution EGF is entire, so there is no finite dominant branch point. The appropriate saddle solves $r+r^2=n$ and yields

$$ H_n=n!\frac{e^{r+r^2/2}}{r^n\sqrt{2\pi(r+2r^2)}}, \qquad r=\frac{\sqrt{1+4n}-1}{2}. $$

The exact involution recurrence is $\iota_0=\iota_1=1$ and $\iota_n=\iota_{n-1}+(n-1)\iota_{n-2}$. It gives $\iota_{10}=9496$, with relative error $H_{10}/\iota_{10}-1\approx0.0141181$. The locality and decay checks in the optional Section 26.6 justify this method; the numerical match alone would not do so.

For an expression with $n$ binary operators and a fixed sequence of $n+1$ operands, its full parenthesizations are Catalan shapes. The logarithmic estimate

$$ \log c_n=n\log4-\frac32\log n-\frac12\log\pi+O(1/n) $$

quantifies the growth of a grammar's candidate parse shapes and helps explain why enumerating every candidate becomes expensive. A parser with precedence rules or a dynamic programming representation may handle this family without explicitly listing all trees; the counting estimate concerns the search space, not a universal lower bound on parsing time.

Optional open-ended extension, ungraded. Study full plane ternary trees counted by internal vertices. The grammar is $T=1+zT^3$ and the exact count is $t_n=\binom{3n}{n}/(2n+1)$. Derive

$$ t_n\sim\frac{\sqrt3}{4\sqrt\pi}\left(\frac{27}{4}\right)^n n^{-3/2}. $$

Solution route: Stirling gives the binomial estimate in Section 26.8; dividing by $2n+1$ gives the displayed constant. The simultaneous equations $T=1+zT^3$ and $1=3zT^2$ yield the positive critical pair $T=3/2,z=4/27$, agreeing with the exponential factor. Prove the selected branch has the required continuation domain before claiming a second proof by transfer, and compare exact and estimated coefficients. This is an extension of established methods, not an asserted unresolved research problem.