40.08.07 · combinatorics / analytic-combinatorics-asymptotics

Limit Laws and the Quasi-Powers Theorem

shipped3 tiersLean: none

Anchor (Master): Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. IX in full — the bivariate-GF framework, the perturbed meromorphic schema (movable simple pole $\rho(u)$, §IX.6) and the perturbed singularity-analysis / algebraic-singularity schema (movable singularity, §IX.7), Hwang's quasi-powers theorem (§IX.5) and its Berry-Esseen and local-limit refinements, and the canonical worked laws: cycles in permutations (Goncharov, Erdős-Turán), components, descents (Eulerian), patterns and the Poisson regime; Hwang 1994 *Théorèmes limites pour les structures combinatoires et les fonctions arithmétiques* (Thèse, École Polytechnique); Bender 1973 *Central and local limit theorems applied to asymptotic enumeration* (J. Combin. Theory A 15)

Intuition Beginner

The chapter so far has counted objects and measured how fast the counts grow. This unit asks a finer question about a single random object. Pick a permutation of $n$ items at random; how many cycles does it have? Pick a set partition at random; how many blocks does it have? These numbers are not fixed — they change from one object to the next. So each one is a quantity that fluctuates, and the question is what its spread looks like across all objects of a given size.

You already know one shape that fluctuating quantities love to take. Add up many small, roughly independent contributions — many coin flips, many dice — and the total piles up into a bell curve, high in the middle and thin at the edges. That is the bell-shaped law that governs averages everywhere. The surprise of this unit is that a counted feature of a random combinatorial object very often follows the same bell-shaped law, even though the object was built by a counting recipe and not by tossing coins.

Why should counting and bell curves meet? Because many combinatorial parameters secretly are sums of many small almost-independent pieces. The number of cycles of a permutation is built up cycle by cycle; the number of blocks of a partition, block by block. Each small piece nudges the total a little, the pieces barely interfere, and the pile-up rule takes over. The bell curve appears for the same underlying reason it appears for coin flips.

The everyday picture is a gumball machine. Each gumball is one object; the number printed on it is the parameter. Most printed numbers cluster near a central value, fewer stray far, and a histogram of the numbers is a smooth hump. This unit explains when that hump is guaranteed to be the bell curve, how wide it is, and how fast it settles into shape.

Visual Beginner

Picture three histograms, one for each size $n$ , of the number of cycles across all permutations of that size. As $n$ grows the histogram slides right (more cycles on average) and widens a little, but its outline keeps converging to the same smooth bell hump once you re-centre and re-scale it.

The table records what the picture promises and what the machinery of this unit delivers. Each row is a fact you can use before seeing why it holds.

idea in words	what it gives you
a parameter of a random object is a fluctuating quantity	a spread to describe, not a single number
a marking variable bookkeeps the parameter inside the generating function	one function $F (z, u)$ holding every spread at once
dividing two coefficients gives the spread of the size- $n$ object	the probabilities of each parameter value
many small almost-independent pieces pile into a bell curve	a guaranteed bell-shaped limit with a known width

Read top to bottom: a parameter fluctuates, a marking variable tracks it, a ratio of coefficients reads off its spread, and the pile-up rule makes the spread a bell curve. The worked example carries this through for the simplest case and shows the bell curve emerging by hand.

Worked example Beginner

Let us watch the bell curve appear for a quantity you can compute by hand: the number of heads in repeated tosses, which is the model every combinatorial bell-curve law imitates. Take $n = 4$ tosses of a fair coin and let the parameter be the number of heads.

Step 1. List the spread. Across all $16$ equally likely outcomes, the number of heads is $0$ once, $1$ four times, $2$ six times, $3$ four times, $4$ once. So the counts are $1, 4, 6, 4, 1$ .

Step 2. Centre it. The average number of heads is $2$ (half of $4$ ). The counts are symmetric around $2$ : the same on each side. The middle value is the tallest, and the bars fall away evenly.

Step 3. Read the width. The spread is measured by a width that for $n$ fair tosses is the square root of $n /4$ , here the square root of $1$ , which is $1$ . So the bulk of the outcomes sits within about one step of the centre $2$ , that is between $1$ and $3$ .

Step 4. Match the hump. Plot the bars $1, 4, 6, 4, 1$ : a clean hump, tallest in the middle, symmetric, thinning at both ends. This is the bell shape in miniature.

Step 5. Grow $n$ . For $n = 100$ tosses the centre moves to $50$ and the width to the square root of $25$ , which is $5$ ; the bars from $40$ to $60$ trace a far smoother bell. The shape sharpens into the ideal curve as $n$ grows.

Step 6. Transfer the lesson. A combinatorial parameter that is a pile-up of many small almost-independent contributions copies this behaviour: a centre that grows with size, a width that grows more slowly, and a re-scaled histogram converging to the same bell. The number of cycles of a random permutation does exactly this, with centre and width both growing like the logarithm of $n$ .

What this tells us: the bell curve is the universal shape of a pile-up of many small contributions, and a counted feature of a random object inherits it whenever the feature is built that way — centre and width are all you need to locate and size the hump.

Check your understanding Beginner

Formal definition Intermediate+

Let $F$ be a combinatorial class with size function $∣ \cdot ∣$ and a parameter $χ : F \to Z_{\geq 0}$ (a marker such as the number of cycles, blocks, descents, or parts). The bivariate generating function marking $χ$ is $$ F(z, u) = \sum_{\omega \in \mathcal{F}} z^{|\omega|}, u^{\chi(\omega)} = \sum_{n, k} f_{n,k}, z^n u^k, $$ where $f_{n, k} = # {ω : ∣ ω ∣ = n, χ (ω) = k}$ (for labelled classes the OGF in $z$ is replaced by the EGF $\sum f_{n, k} \frac{z ^{n}}{n !} u^{k}$ , with $f_{n} = n! [z^{n}] F (z, 1)$ ). Setting $u = 1$ recovers the univariate counting series $F (z, 1) = \sum_{n} f_{n} z^{n}$ , whose asymptotics are read by the methods of 40.08.03 and 40.08.06.

Definition (parameter as a random variable). Under the uniform distribution on the $f_{n}$ objects of size $n$ , the parameter $χ$ becomes a random variable $X_{n}$ with $$ \mathbb{P}(X_n = k) = \frac{f_{n,k}}{f_n} = \frac{[z^n u^k]F(z,u)}{[z^n]F(z,1)}. $$ Its probability generating function (PGF) is the ratio of coefficient extractions in $z$ , $$ p_n(u) = \mathbb{E}\big[u^{X_n}\big] = \sum_k \mathbb{P}(X_n = k), u^k = \frac{[z^n]F(z,u)}{[z^n]F(z,1)}, $$ a polynomial in $u$ with $p_{n} (1) = 1$ . The mean and variance are read from $p_{n}$ by differentiation at $u = 1$ : $$ \mathbb{E}[X_n] = p_n'(1), \qquad \mathrm{Var}(X_n) = p_n''(1) + p_n'(1) - p_n'(1)^2. $$ The notation $F (z, u)$ , $[z^{n} u^{k}]$ , $p_{n} (u)$ , $X_{n}$ , and the variability functional below are recorded in _meta/NOTATION.md.

Definition (quasi-powers form). A sequence of PGFs $p_{n} (u)$ has a quasi-powers expansion if there are functions $A, B$ analytic at $u = 1$ with $A (1) = B (1) = 1$ , a sequence $λ_{n} \to \infty$ , and a sequence $κ_{n} \to \infty$ such that $$ p_n(u) = A(u), B(u)^{\lambda_n}\big(1 + O(\kappa_n^{-1})\big) $$ holds uniformly for $u$ in a fixed complex neighbourhood of $1$ . The name records that, to leading order, $p_{n} (u)$ is a large power $B (u)^{λ_{n}}$ — a "quasi-power" — modulated by the fixed factor $A (u)$ . The variability constant of $B$ is $$ \mathfrak{v}(B) = \frac{B''(1)}{B(1)} + \frac{B'(1)}{B(1)} - \left(\frac{B'(1)}{B(1)}\right)^2, $$ the second derivative of $lo g B (e^{t})$ at $t = 0$ ; the mean constant is $m (B) = B^{'} (1) / B (1) = \frac{d}{d t} lo g B (e^{t})_{t = 0}$ .

A pure power $p_{n} (u) = B (u)^{λ_{n}}$ is the PGF of a sum of $λ_{n}$ independent identically distributed variables each with PGF $B (u)$ (when $λ_{n}$ is an integer); the quasi-powers hypothesis says that $X_{n}$ behaves, in the bulk, like such a sum of $λ_{n}$ small pieces, which is exactly the pile-up that produces a Gaussian.

Counterexamples to common slips Intermediate+

"Knowing the mean and variance is the limit law." The mean $p_{n}^{'} (1) \sim λ_{n} m (B)$ and variance $p_{n}^{''} (1) + p_{n}^{'} (1) - p_{n}^{'} (1)^{2} \sim λ_{n} v (B)$ fix the centre and width of the hump but not its shape; a sequence can have linear-in- $n$ mean and variance and still converge to a non-Gaussian law. The Gaussian conclusion needs the full quasi-power form uniformly on a complex neighbourhood of $u = 1$ , not just the first two moments at $u = 1$ .
" $λ_{n} = n$ always." The growth rate $λ_{n}$ is the number of small pieces, and it depends on the schema. For a movable pole (meromorphic schema) $λ_{n} = n$ , giving mean and variance linear in $n$ ; for the number of cycles of a permutation the relevant rate is $λ_{n} = H_{n} \sim ln n$ , giving mean and variance of order $ln n$ . A bounded $λ_{n}$ does not give a Gaussian at all but a discrete (Poisson) limit.
"The bivariate singularity is just the univariate one with $u$ along for the ride." The whole mechanism is that the dominant singularity $ρ (u)$ in $z$ moves with $u$ . If $ρ (u) \equiv ρ (1)$ were constant in $u$ , then $B (u) = ρ (1) / ρ (u) \equiv 1$ , the variability would vanish, and there would be no spreading; the Gaussian comes precisely from the curvature of $lo g ρ (u)$ at $u = 1$ .
"A central limit theorem gives the individual probabilities." The quasi-powers theorem in its basic form is a central limit theorem: it controls the distribution function $P (X_{n} \leq x)$ . The local limit theorem — convergence of the single probabilities $P (X_{n} = k)$ to the Gaussian density — needs an extra condition ruling out oscillation of $∣ p_{n} (u) ∣$ on $∣ u ∣ = 1$ away from $u = 1$ ; a parameter supported on an arithmetic progression (e.g. always even) satisfies the central but not the local theorem without rescaling.

Key theorem with proof Intermediate+

The signature theorem is Hwang's quasi-powers theorem: a uniform quasi-power expansion of the PGFs forces a Gaussian limit with explicit mean, variance, and convergence speed. Every Gaussian law in this unit — cycles, descents, components — is one instance, obtained by exhibiting the quasi-power form for that parameter's bivariate generating function ^{[Flajolet-Sedgewick §IX.5]}. The proof runs the parameter's PGF through the characteristic-function machinery of the central limit theorem of 37.03.01, so this is the point where enumeration borrows the probabilist's continuity theorem.

Theorem (quasi-powers; Hwang). Suppose the PGFs $p_{n} (u) = E [u^{X_{n}}]$ admit a quasi-power expansion $$ p_n(u) = A(u), B(u)^{\lambda_n}\big(1 + O(\kappa_n^{-1})\big), \qquad \kappa_n \to \infty, $$ uniformly for $u$ in a fixed complex neighbourhood of $u = 1$ , with $A, B$ analytic there, $A (1) = B (1) = 1$ , $λ_{n} \to \infty$ , and variability $v (B) \neq = 0$ . Then $E [X_{n}] = λ_{n} m (B) + O (1)$ , $Var (X_{n}) = λ_{n} v (B) + O (1)$ , and the standardised variable converges to the standard normal: $$ \frac{X_n - \lambda_n\mathfrak{m}(B)}{\sqrt{\lambda_n,\mathfrak{v}(B)}} \xrightarrow{d} \mathcal{N}(0,1), $$ with Berry-Esseen speed $sup_{x} P (X_{n} \leq E [X_{n}] + x Var (X_{n})) - Φ (x) = O (κ_{n}^{- 1} + λ_{n}^{- 1/2})$ , where $Φ$ is the standard normal distribution function.

Proof. Write $μ_{n} = λ_{n} m (B)$ and $σ_{n}^{2} = λ_{n} v (B)$ ; the moment claims follow by differentiating $lo g p_{n} (u) = lo g A (u) + λ_{n} lo g B (u) + O (κ_{n}^{- 1})$ at $u = 1$ and using $E [X_{n}] = (lo g p_{n})^{'} (1) + (lower)$ , $Var (X_{n}) = (lo g p_{n})^{''} (1) + (lo g p_{n})^{'} (1)$ , the cumulant reading of the PGF.

For the limit law, evaluate the PGF on the unit circle at $u = e^{i t / σ_{n}}$ , which produces the characteristic function of the standardised variable: with $Y_{n} = (X_{n} - μ_{n}) / σ_{n}$ ,

E [e^{i t Y_{n}}] = e^{- i t μ_{n} / σ_{n}} p_{n} (e^{i t / σ_{n}}) .

Fix $t$ . As $n \to \infty$ , $e^{i t / σ_{n}} \to 1$ , so $u = e^{i t / σ_{n}}$ lies in the neighbourhood where the expansion holds for all large $n$ , and

lo g p_{n} (e^{i t / σ_{n}}) = lo g A (e^{i t / σ_{n}}) + λ_{n} lo g B (e^{i t / σ_{n}}) + O (κ_{n}^{- 1}) .

The first term is $O (1/ σ_{n}) \to 0$ since $A (1) = 1$ and $A$ is analytic. Expand $lo g B (e^{s})$ at $s = 0$ : with $g (s) := lo g B (e^{s})$ one has $g (0) = 0$ , $g^{'} (0) = m (B)$ , $g^{''} (0) = v (B)$ , so $g (s) = m (B) s + \frac{1}{2} v (B) s^{2} + O (s^{3})$ . Substituting $s = i t / σ_{n}$ ,

λ_{n} lo g B (e^{i t / σ_{n}}) = λ_{n} (m (B) \frac{i t}{σ _{n}} - \frac{1}{2} v (B) \frac{t ^{2}}{σ _{n}^{2}} + O (σ_{n}^{- 3})) = \frac{i t μ _{n}}{σ _{n}} - \frac{t ^{2}}{2} + O (λ_{n}^{- 1/2}),

using $λ_{n} m (B) = μ_{n}$ and $λ_{n} v (B) = σ_{n}^{2}$ , and $λ_{n} / σ_{n}^{3} = O (λ_{n}^{- 1/2})$ . Hence

lo g E [e^{i t Y_{n}}] = - \frac{i t μ _{n}}{σ _{n}} + \frac{i t μ _{n}}{σ _{n}} - \frac{t ^{2}}{2} + O (κ_{n}^{- 1} + λ_{n}^{- 1/2}) ⟶ - \frac{t ^{2}}{2},

the linear terms cancelling by the choice of centring. Thus $E [e^{i t Y_{n}}] \to e^{- t^{2} /2}$ pointwise in $t$ , the characteristic function of $N (0, 1)$ ; by Lévy's continuity theorem 37.03.01, $Y_{n} d N (0, 1)$ . The rate follows from the Berry-Esseen inequality: the explicit error $O (κ_{n}^{- 1} + λ_{n}^{- 1/2})$ in $lo g E [e^{i t Y_{n}}]$ , uniform for $∣ t ∣ \leq c σ_{n}$ , bounds the characteristic-function difference $∣ E [e^{i t Y_{n}}] - e^{- t^{2} /2} ∣$ , and Esseen's smoothing inequality converts this integrated difference into the stated sup-norm bound on the distribution functions. $□$

Corollary (mean and variance schema). When $B (u) = ρ (1) / ρ (u)$ comes from a movable singularity $ρ (u)$ and $λ_{n} = n$ , the mean is $- n ρ^{'} (1) / ρ (1) + O (1)$ and the variance is $n (- ρ^{''} (1) / ρ (1) - ρ^{'} (1) / ρ (1) + (ρ^{'} (1) / ρ (1))^{2}) + O (1)$ , both linear in $n$ , recovering Bender's central limit theorem ^{[Bender 1973]}.

Bridge. This theorem builds toward every named limit law in the chapter and appears again in 40.08.04, where the perturbed singularity analysis supplies the uniform expansion of $[z^{n}] F (z, u)$ that the hypothesis demands. The foundational reason a counting problem produces a probabilist's bell curve is that the quasi-power $B (u)^{λ_{n}}$ is exactly the probability generating function of a sum of $λ_{n}$ independent small pieces, so this is exactly the central limit theorem of 37.03.02 read through a generating function: the marking variable $u = e^{i t / σ_{n}}$ turns the PGF into a characteristic function, and Lévy continuity does the rest. The mechanism generalises the saddle-point Gaussian of 40.08.06 — there the integrand collapsed to a Gaussian in the angle $θ$ ; here a second Gaussian, in the marking direction $u$ , rides on top — and putting these together, the central insight is that the same quadratic expansion of a logarithm that gave Stirling's $2 π b_{n}$ now gives the limiting $e^{- t^{2} /2}$ , one collapse counting size and the other measuring a parameter.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

The number of cycles of a random permutation has bivariate EGF $F (z, u) = (1 - z)^{- u} = exp (u lo g \frac{1}{1 - z})$ (each cycle marked by $u$ ). Show $[z^{n}] F (z, u) = (n n + u - 1)$ and hence $p_{n} (u) = \frac{( n n + u - 1 )}{1} = \frac{Γ ( n + u )}{Γ ( u ) n !}$ , the PGF of the cycle count.

Hint

$(1 - z)^{- u} = \sum_{n} (n n + u - 1) z^{n}$ (generalised binomial series). At $u = 1$ , $F (z, 1) = (1 - z)^{- 1}$ , so $[z^{n}] F (z, 1) = 1$ and $f_{n} = n!$ .

Answer

The generalised binomial series gives $(1 - z)^{- u} = \sum_{n} (n n + u - 1) z^{n}$ , so $[z^{n}] F (z, u) = (n n + u - 1) = \frac{u ( u + 1 ) \dots ( u + n - 1 )}{n !} = \frac{Γ ( n + u )}{Γ ( u ) n !}$ . At $u = 1$ this is $(n n) = 1$ , so $f_{n} = n! \cdot 1 = n!$ permutations, as expected. Hence $p_{n} (u) = [z^{n}] F (z, u) / [z^{n}] F (z, 1) = (n n + u - 1) = \frac{u ( u + 1 ) \dots ( u + n - 1 )}{n !}$ . Expanding, $p_{n} (u) = \frac{1}{n !} \sum_{k} [k n] u^{k}$ where $[k n]$ are the unsigned Stirling numbers of the first kind, so $P (X_{n} = k) = \frac{1}{n !} [k n]$ , the probability that a random permutation has $k$ cycles. Rubric: full credit for the binomial coefficient, the value $1$ at $u = 1$ , and the rising-factorial PGF.

Exercise 5 (medium, symbolic).

Still for the cycle count, compute the variance. Show $Var (X_{n}) = \sum_{j = 0}^{n - 1} \frac{j}{( 1 + j ) ^{2}} = H_{n} - H_{n}^{(2)}$ where $H_{n}^{(2)} = \sum_{m = 1}^{n} 1/ m^{2}$ , and conclude $Var (X_{n}) \sim ln n$ .

Hint

$(lo g p_{n})^{''} (u) = - \sum_{j} \frac{1}{( u + j ) ^{2}}$ , and $Var (X_{n}) = (lo g p_{n})^{''} (1) + (lo g p_{n})^{'} (1)$ .

Answer

The cumulant identity gives $Var (X_{n}) = (lo g p_{n})^{''} (1) + (lo g p_{n})^{'} (1)$ . Here $(lo g p_{n})^{'} (u) = \sum_{j} \frac{1}{u + j}$ and $(lo g p_{n})^{''} (u) = - \sum_{j} \frac{1}{( u + j ) ^{2}}$ , so at $u = 1$ : $Var (X_{n}) = - \sum_{j = 0}^{n - 1} \frac{1}{( 1 + j ) ^{2}} + \sum_{j = 0}^{n - 1} \frac{1}{1 + j} = \sum_{m = 1}^{n} \frac{1}{m} - \sum_{m = 1}^{n} \frac{1}{m ^{2}} = H_{n} - H_{n}^{(2)}$ . Since $H_{n} \sim ln n$ and $H_{n}^{(2)} \to π^{2} /6$ (bounded), $Var (X_{n}) = ln n + γ - π^{2} /6 + o (1) \sim ln n$ . Mean and variance both $\sim ln n$ : the signature of the Erdős-Turán / Goncharov Gaussian law for cycles. Rubric: full credit for the variance sum, the closed form $H_{n} - H_{n}^{(2)}$ , and the $ln n$ asymptotic.

Exercise 6 (medium, symbolic).

Verify the quasi-power form for the cycle count. Using $p_{n} (u) = \frac{Γ ( n + u )}{Γ ( u ) n !}$ and Stirling for the Gamma function, show $p_{n} (u) \sim \frac{1}{Γ ( u )} n^{u - 1}$ , identify $A (u)$ , $B (u)$ , and $λ_{n}$ , and confirm $m (B)$ and $v (B)$ match the mean and variance rates $\sim ln n$ .

Hint

$\frac{Γ ( n + u )}{Γ ( n + 1 )} \sim n^{u - 1}$ as $n \to \infty$ (ratio of Gammas). Write $n^{u - 1} = e^{(u - 1) l n n}$ to read off $B (u)^{λ_{n}}$ with $λ_{n} = ln n$ .

Answer

The Gamma ratio asymptotic $\frac{Γ ( n + u )}{Γ ( n + 1 )} \sim n^{u - 1}$ gives $p_{n} (u) = \frac{Γ ( n + u )}{Γ ( u ) Γ ( n + 1 )} \sim \frac{1}{Γ ( u )} n^{u - 1}$ . Write $n^{u - 1} = e^{(u - 1) l n n} = (e^{u - 1})^{l n n}$ . So $p_{n} (u) \sim A (u) B (u)^{λ_{n}}$ with $A (u) = \frac{1}{Γ ( u )}$ (note $A (1) = 1/Γ (1) = 1$ ), $B (u) = e^{u - 1}$ (so $B (1) = 1$ ), and $λ_{n} = ln n \to \infty$ . Then $lo g B (e^{t}) = e^{t} - 1$ , so $m (B) = \frac{d}{d t} (e^{t} - 1) ∣_{0} = 1$ and $v (B) = \frac{d ^{2}}{d t ^{2}} (e^{t} - 1) ∣_{0} = 1$ . Mean $\sim λ_{n} m (B) = ln n$ and variance $\sim λ_{n} v (B) = ln n$ , matching Exercises 4-5. By the quasi-powers theorem with $κ_{n} = ln n$ , $(X_{n} - ln n) / ln n \to N (0, 1)$ . Rubric: full credit for $A = 1/Γ (u)$ , $B = e^{u - 1}$ , $λ_{n} = ln n$ , and $m = v = 1$ .

Exercise 7 (hard, symbolic).

The number of descents of a random permutation is marked by the Eulerian generating function (cross-ref 40.01.05): $\sum_{n} A_{n} (u) \frac{z ^{n}}{n !} = \frac{u - 1}{u - e ^{(u - 1) z}}$ , where $A_{n} (u) = \sum_{k} ⟨ k n ⟩ u^{k}$ is the Eulerian polynomial. Using the known mean $E [X_{n}] = \frac{n - 1}{2}$ and variance $Var (X_{n}) = \frac{n + 1}{12}$ , identify the quasi-power rate $λ_{n}$ and the implied Gaussian law.

Hint

Mean and variance are both linear in $n$ , so $λ_{n} = n$ . The descent count is a sum of $n - 1$ indicator variables $1 [π (i) > π (i + 1)]$ , almost independent.

Answer

The descent count $X_{n} = \sum_{i = 1}^{n - 1} 1 [π (i) > π (i + 1)]$ is a sum of $n - 1$ indicators, each with mean $\frac{1}{2}$ (by symmetry $π (i) > π (i + 1)$ with probability $\frac{1}{2}$ ), giving $E [X_{n}] = \frac{n - 1}{2}$ . The variance is $\frac{n + 1}{12}$ (the adjacent indicators are weakly negatively correlated, reducing the naive $\frac{n - 1}{4}$ ). Both are linear in $n$ , so $λ_{n} = n$ and $m (B) = \frac{1}{2}$ , $v (B) = \frac{1}{12}$ . The Eulerian polynomials are real-rooted (Frobenius), so $A_{n} (u) / A_{n} (1) = \prod_{i} \frac{u + r _{i}}{1 + r _{i}}$ is a product of PGFs of independent bits, and Hwang's theorem (or the real-rootedness route via Harper's theorem) gives $\frac{X _{n} - ( n - 1 ) /2}{( n + 1 ) /12} \to N (0, 1)$ , the Gaussian descent law. The real-rootedness is the cleanest certificate of the quasi-power form here. Rubric: full credit for $λ_{n} = n$ , $m = \frac{1}{2}$ , $v = \frac{1}{12}$ , and the Gaussian conclusion with the real-rootedness remark.

Exercise 8 (hard, symbolic).

Establish the meromorphic-schema quasi-power. Let $F (z, u) = \frac{1}{1 - u C ( z )}$ mark by $u$ the number of components in a sequence of $C$ -structures with $C (z)$ having radius $r_{C}$ and $C (r_{C}) > 1$ . For $u$ near $1$ let $ρ (u)$ solve $u C (ρ (u)) = 1$ (the movable simple pole). Show $p_{n} (u) \sim (ρ (1) / ρ (u))^{n} \cdot \frac{const ( u )}{const ( 1 )}$ and identify $B (u) = ρ (1) / ρ (u)$ , $λ_{n} = n$ .

Hint

By the simple-pole coefficient asymptotic of 40.08.03, $[z^{n}] \frac{1}{1 - u C ( z )} \sim \frac{1}{u ρ ( u ) C ^{'} ( ρ ( u ))} ρ (u)^{- n}$ . Take the ratio over $u = 1$ .

Answer

For each $u$ near $1$ , $F (z, u) = \frac{1}{1 - u C ( z )}$ has a dominant simple pole at $z = ρ (u)$ solving $u C (ρ (u)) = 1$ , with $ρ (u)$ analytic in $u$ by the implicit function theorem since $\partial_{z} [u C (z)] = u C^{'} (z) \neq = 0$ there. By the simple-pole asymptotic of 40.08.03, $[z^{n}] F (z, u) \sim \frac{- 1}{\partial _{z} [ 1 - u C ( z )] ∣ _{ρ (u)}} ρ (u)^{- n - 1} = \frac{1}{u C ^{'} ( ρ ( u ))} ρ (u)^{- n - 1} =: g (u) ρ (u)^{- n}$ with $g (u) = \frac{1}{u ρ ( u ) C ^{'} ( ρ ( u ))}$ analytic. Therefore $$ p_n(u) = \frac{[z^n]F(z,u)}{[z^n]F(z,1)} \sim \frac{g(u)}{g(1)}\Big(\frac{\rho(1)}{\rho(u)}\Big)^{n}. $$ This is the quasi-power $A (u) B (u)^{λ_{n}}$ with $A (u) = g (u) / g (1)$ (so $A (1) = 1$ ), $B (u) = ρ (1) / ρ (u)$ (so $B (1) = 1$ ), $λ_{n} = n$ , and $κ_{n} = n$ from the $O (R^{- n} / ρ (u)^{- n})$ relative error of the singularity expansion. Differentiating $u C (ρ (u)) = 1$ gives $C (ρ) + u C^{'} (ρ) ρ^{'} = 0$ , so $ρ^{'} (1) / ρ (1) = - C (ρ (1)) / (ρ (1) C^{'} (ρ (1)) \cdot ρ (1)) \cdot ρ (1)$ is finite and the variability $v (B) = - ρ^{''} (1) / ρ (1) - ρ^{'} (1) / ρ (1) + (ρ^{'} (1) / ρ (1))^{2} > 0$ (generically nonzero), so the component count is Gaussian with mean and variance linear in $n$ — the supercritical-composition law. Rubric: full credit for the movable pole $ρ (u)$ , the simple-pole asymptotic, $B (u) = ρ (1) / ρ (u)$ , $λ_{n} = n$ , and the linear-in- $n$ Gaussian conclusion.

Advanced results Master

The quasi-powers theorem is the analytic kernel; its deployment rests on the two structural mechanisms that generate the quasi-power form from a bivariate generating function — the perturbed meromorphic schema and the perturbed singularity-analysis schema — together with the local-limit refinement, the discrete (Poisson) regime where the hypothesis fails, and the canonical permutation-cycle law as the worked frontier case.

Theorem 1 (meromorphic schema: movable pole gives a Gaussian). Let $F (z, u)$ be analytic in a bidisc around $(0, 1)$ such that, for each $u$ in a neighbourhood of $1$ , the section $z \mapsto F (z, u)$ is meromorphic with a unique dominant simple pole at $z = ρ (u)$ , with $ρ$ analytic, $ρ (1)$ the dominant pole of $F (z, 1)$ , and the residue analytic and nonzero. Then $$ p_n(u) \sim A(u),\Big(\frac{\rho(1)}{\rho(u)}\Big)^{n}, \qquad A(u) = \frac{\operatorname{Res}{z=\rho(u)}F(z,u)/\rho(u)}{\operatorname{Res}{z=\rho(1)}F(z,1)/\rho(1)}, $$ a quasi-power with $B (u) = ρ (1) / ρ (u)$ , $λ_{n} = n$ , $κ_{n} = n$ . Hence $X_{n}$ is asymptotically Gaussian with mean $\sim - n ρ^{'} (1) / ρ (1)$ and variance $\sim n v (ρ (1) / ρ (\cdot))$ , both linear in $n$ , whenever the variability is nonzero ^{[Flajolet-Sedgewick §IX.6]}. This is the law of the number of components in a supercritical sequence, the number of parts in a composition, and the number of $H$ -patterns in random words; the movable pole of 40.08.03 perturbed by the marking variable is the whole content.

Theorem 2 (singularity-analysis schema: movable algebraic singularity gives a Gaussian). Let $F (z, u) \sim c (u) (1 - z / ρ (u))^{- α (u)}$ near a movable algebraic singularity $z = ρ (u)$ , with $c, ρ, α$ analytic near $u = 1$ and $ρ$ non-constant. By the singularity-analysis transfer theorems (co-produced 40.08.04), $[z^{n}] F (z, u) \sim \frac{c ( u )}{Γ ( α ( u ))} n^{α (u) - 1} ρ (u)^{- n}$ uniformly for $u$ near $1$ , so $$ p_n(u) \sim \frac{c(u),\Gamma(\alpha(1))}{c(1),\Gamma(\alpha(u))},n^{\alpha(u)-\alpha(1)}\Big(\frac{\rho(1)}{\rho(u)}\Big)^{n}. $$ When $ρ$ is non-constant the dominant quasi-power has $B (u) = ρ (1) / ρ (u)$ , $λ_{n} = n$ ; when $ρ \equiv ρ (1)$ but $α$ varies, $p_{n} (u) \sim \frac{c ( u ) Γ ( α ( 1 ))}{c ( 1 ) Γ ( α ( u ))} (e^{α (u)})^{l n n}$ is a quasi-power with $λ_{n} = ln n$ , $B (u) = e^{α (u) - α (1)}$ . Either way $X_{n}$ is asymptotically Gaussian ^{[Flajolet-Sedgewick §IX.7]}. The non-constant- $ρ$ case governs the number of leaves and the number of nodes of given degree in simple varieties of random trees and the number of components of random mappings; the constant- $ρ$ , varying- $α$ case governs the number of cycles of a permutation ( $α (u) = u$ , $ρ \equiv 1$ , $λ_{n} = ln n$ ) and the number of distinct prime factors $ω (N)$ of a random integer (Erdős-Kac).

Theorem 3 (central versus local limit law). Under the quasi-powers hypothesis, $X_{n}$ satisfies the central limit theorem (convergence of the distribution function $P (X_{n} \leq x)$ to $Φ$ ). If in addition $∣ p_{n} (u) ∣$ is uniformly small on the arc ${∣ u ∣ = 1, ∣ ar g u ∣ \geq δ}$ for some $δ > 0$ — equivalently $X_{n}$ is not concentrated on a proper arithmetic progression — then the local limit law holds: $$ \sup_k\left|\sqrt{\mathrm{Var}(X_n)};\mathbb{P}(X_n = k) - \frac{1}{\sqrt{2\pi}}\exp!\left(-\frac{(k - \mathbb{E}[X_n])^2}{2,\mathrm{Var}(X_n)}\right)\right| \to 0. $$ The local theorem is strictly stronger: it gives the individual probabilities, not merely the cumulative ones, and fails for a parameter supported on, say, the even integers until rescaled by the period ^{[Bender 1973]}. The arc condition is the marking-variable analogue of the tail-negligibility hypothesis of the saddle-point method of 40.08.06.

Theorem 4 (discrete/Poisson regime: when the hypothesis fails). If $λ_{n} \to λ < \infty$ stays bounded — the parameter is a count of rare events, each occurring with vanishing probability — the quasi-powers hypothesis $λ_{n} \to \infty$ fails and there is no Gaussian. Instead, when $p_{n} (u) \to e^{λ (u - 1)}$ pointwise, $X_{n}$ converges to a Poisson law of mean $λ$ : $P (X_{n} = k) \to e^{- λ} λ^{k} / k!$ . The number of fixed points of a random permutation (mean $1$ , Poisson $(1)$ in the limit), the number of singleton blocks of a random set partition, and the number of occurrences of a fixed pattern that appears $O (1)$ times are governed by this regime; the boundary between Poisson and Gaussian is exactly $λ_{n}$ bounded versus $λ_{n} \to \infty$ ^{[Flajolet-Sedgewick §IX.11]}. The Poisson convergence is the method-of-moments / Janson-inequality regime of the probabilistic combinatorics chapter 40.07.07, reached here analytically through the bivariate generating function.

Theorem 5 (permutation cycles: the Goncharov / Erdős-Turán law). Let $X_{n}$ be the number of cycles of a uniformly random permutation of $[n]$ , with PGF $p_{n} (u) = (n n + u - 1) = \frac{Γ ( n + u )}{Γ ( u ) n !}$ . Then $E [X_{n}] = H_{n}$ , $Var (X_{n}) = H_{n} - H_{n}^{(2)}$ , and $$ \frac{X_n - \ln n}{\sqrt{\ln n}} \xrightarrow{d} \mathcal{N}(0,1), $$ with the local limit law $P (X_{n} = k) \sim \frac{1}{2 π l n n} exp (- \frac{( k - l n n ) ^{2}}{2 l n n})$ for $k = ln n + O (ln n)$ ^{[Flajolet-Sedgewick §IX.9]}. The quasi-power is $p_{n} (u) \sim \frac{1}{Γ ( u )} n^{u - 1} = \frac{1}{Γ ( u )} (e^{u - 1})^{l n n}$ , with $A (u) = 1/Γ (u)$ , $B (u) = e^{u - 1}$ , $λ_{n} = ln n$ , $κ_{n} = ln n$ ; the rate $λ_{n} = ln n$ rather than $n$ is the signature of the logarithmic-structure (constant $ρ$ , varying singular exponent) schema, and the same analysis with $ω (N) =$ number of distinct primes of $N$ ( $λ_{n} = ln ln N$ ) is the Erdős-Kac theorem.

Synthesis. The quasi-powers theorem is the foundational reason enumeration meets probability: a counted parameter of a random combinatorial object becomes a probabilist's Gaussian precisely when its probability generating function $p_{n} (u) = [z^{n}] F (z, u) / [z^{n}] F (z, 1)$ is, to leading order, a large power $B (u)^{λ_{n}}$ of a fixed analytic function — the generating-function avatar of a sum of $λ_{n}$ independent small pieces. The central insight is that the marking substitution $u = e^{i t / σ_{n}}$ turns this PGF into the characteristic function of the standardised variable, the quadratic expansion of $lo g B (e^{s})$ produces $e^{- t^{2} /2}$ , and Lévy continuity 37.03.01 delivers the normal law with a Berry-Esseen rate; this is exactly the central limit theorem of 37.03.02 read through the bivariate generating function, and it is dual to the univariate saddle-point Gaussian of 40.08.06 — there a Gaussian in the contour angle counts size, here a second Gaussian in the marking direction measures a parameter, and the same logarithm-and-quadratic collapse drives both.

The two mechanisms producing the quasi-power are the two singularity readings of the chapter perturbed by $u$ : the movable simple pole $ρ (u)$ of the meromorphic schema 40.08.03, giving $λ_{n} = n$ and laws linear in $n$ (components, descents), and the movable algebraic singularity $ρ (u)$ or movable exponent $α (u)$ of the singularity-analysis schema 40.08.04, giving $λ_{n} = n$ or $λ_{n} = ln n$ (trees, mappings, cycles). Putting these together, the whole asymptotic landscape of the chapter — meromorphic 40.08.03, singularity analysis 40.08.04, saddle point 40.08.06 — reappears here perturbed by a marking variable, and the same local analysis that read the size asymptotics now reads the distribution of every parameter the symbolic method can mark; this generalises the chapter's univariate growth analysis into a parametric limit-law machine, and the boundary where $λ_{n}$ stays bounded crosses out of the Gaussian world into the Poisson regime of 40.07.07, so the quasi-powers theorem is the capstone that classifies, by the growth of $λ_{n}$ , when a combinatorial parameter is Gaussian, when it is Poisson, and how fast it converges.

Full proof set Master

Proposition 1 (PGF extraction and moments). For a parameter $χ$ with bivariate GF $F (z, u)$ and $f_{n} = [z^{n}] F (z, 1) > 0$ , the PGF of $X_{n}$ is $p_{n} (u) = [z^{n}] F (z, u) / f_{n}$ , a polynomial with $p_{n} (1) = 1$ , $p_{n}^{'} (1) = E [X_{n}]$ , and $p_{n}^{''} (1) + p_{n}^{'} (1) - p_{n}^{'} (1)^{2} = Var (X_{n})$ .

Proof. By definition $[z^{n}] F (z, u) = \sum_{k} f_{n, k} u^{k}$ , so $p_{n} (u) = \sum_{k} \frac{f _{n, k}}{f _{n}} u^{k} = \sum_{k} P (X_{n} = k) u^{k} = E [u^{X_{n}}]$ . At $u = 1$ , $\sum_{k} P (X_{n} = k) = 1$ . Differentiating, $p_{n}^{'} (u) = \sum_{k} k P (X_{n} = k) u^{k - 1}$ , so $p_{n}^{'} (1) = \sum_{k} k P (X_{n} = k) = E [X_{n}]$ . Next $p_{n}^{''} (1) = \sum_{k} k (k - 1) P (X_{n} = k) = E [X_{n} (X_{n} - 1)] = E [X_{n}^{2}] - E [X_{n}]$ , so $p_{n}^{''} (1) + p_{n}^{'} (1) - p_{n}^{'} (1)^{2} = E [X_{n}^{2}] - E [X_{n}] + E [X_{n}] - E [X_{n}]^{2} = Var (X_{n})$ . $□$

Proposition 2 (cumulants of a quasi-power). If $p_{n} (u) = A (u) B (u)^{λ_{n}} (1 + O (κ_{n}^{- 1}))$ uniformly near $u = 1$ with $A (1) = B (1) = 1$ , then $E [X_{n}] = λ_{n} m (B) + m (A) + O (κ_{n}^{- 1})$ and $Var (X_{n}) = λ_{n} v (B) + v (A) + O (κ_{n}^{- 1})$ .

Proof. Let $L_{n} (t) = lo g p_{n} (e^{t}) = lo g A (e^{t}) + λ_{n} lo g B (e^{t}) + O (κ_{n}^{- 1})$ , the cumulant generating function of $X_{n}$ (the $O$ -term analytic in $t$ near $0$ , so differentiable term by term by uniform convergence on a complex neighbourhood and Cauchy's estimates). The first cumulant is $L_{n}^{'} (0) = E [X_{n}]$ and the second is $L_{n}^{''} (0) = Var (X_{n})$ . With $g_{A} (t) = lo g A (e^{t})$ , $g_{B} (t) = lo g B (e^{t})$ : $g_{A} (0) = g_{B} (0) = 0$ , $g_{B}^{'} (0) = m (B)$ , $g_{B}^{''} (0) = v (B)$ by the definitions, and likewise for $A$ . Differentiating $L_{n}$ at $0$ gives $E [X_{n}] = m (A) + λ_{n} m (B) + O (κ_{n}^{- 1})$ and $Var (X_{n}) = v (A) + λ_{n} v (B) + O (κ_{n}^{- 1})$ . Since $A$ is fixed, $m (A), v (A) = O (1)$ . $□$

Proposition 3 (quasi-powers central limit theorem). Under the hypotheses of Proposition 2 with $λ_{n} \to \infty$ and $v (B) \neq = 0$ , $Y_{n} := (X_{n} - E [X_{n}]) / Var (X_{n}) d N (0, 1)$ .

Proof. Set $σ_{n} = Var (X_{n}) \sim λ_{n} v (B) \to \infty$ . The characteristic function is $ϕ_{n} (t) = E [e^{i t Y_{n}}] = e^{- i t E [X_{n}] / σ_{n}} p_{n} (e^{i t / σ_{n}})$ . Fix $t \in R$ . For $n$ large, $i t / σ_{n}$ lies in the complex neighbourhood of $0$ where $L_{n}$ is analytic, so $$ \log p_n(e^{it/\sigma_n}) = g_A(it/\sigma_n) + \lambda_n g_B(it/\sigma_n) + O(\kappa_n^{-1}). $$ Taylor-expanding $g_{B} (s) = m (B) s + \frac{1}{2} v (B) s^{2} + O (s^{3})$ at $s = i t / σ_{n}$ : $$ \lambda_n g_B(it/\sigma_n) = \lambda_n\mathfrak{m}(B)\frac{it}{\sigma_n} - \lambda_n\mathfrak{v}(B)\frac{t^2}{2\sigma_n^2} + O!\Big(\frac{\lambda_n}{\sigma_n^3}\Big). $$ Now $λ_{n} v (B) / σ_{n}^{2} \to 1$ , $λ_{n} / σ_{n}^{3} = O (λ_{n}^{- 1/2}) \to 0$ , and $g_{A} (i t / σ_{n}) = O (1/ σ_{n}) \to 0$ . The term $λ_{n} m (B) (i t / σ_{n})$ combines with $- i t E [X_{n}] / σ_{n} = - i t (λ_{n} m (B) + O (1)) / σ_{n}$ to leave $O (t / σ_{n}) \to 0$ . Hence $lo g ϕ_{n} (t) \to - t^{2} /2$ , so $ϕ_{n} (t) \to e^{- t^{2} /2}$ for every $t$ . By Lévy's continuity theorem 37.03.01, pointwise convergence of characteristic functions to the continuous limit $e^{- t^{2} /2}$ implies $Y_{n} d N (0, 1)$ . $□$

Proposition 4 (Berry-Esseen rate). Under the hypotheses of Proposition 3, $sup_{x} ∣ P (Y_{n} \leq x) - Φ (x) ∣ = O (κ_{n}^{- 1} + λ_{n}^{- 1/2})$ .

Proof. By Esseen's smoothing inequality, for any $T > 0$ , $$ \sup_x|\mathbb{P}(Y_n\le x) - \Phi(x)| \le \frac{1}{\pi}\int_{-T}^{T}\frac{|\phi_n(t) - e^{-t^2/2}|}{|t|},dt + \frac{C}{T}, $$ with $C$ absolute. From Proposition 3, on $∣ t ∣ \leq T = c σ_{n}$ the expansion gives $lo g ϕ_{n} (t) = - \frac{t ^{2}}{2} + R_{n} (t)$ with $∣ R_{n} (t) ∣ \leq C^{'} (κ_{n}^{- 1} + ∣ t ∣^{3} λ_{n} / σ_{n}^{3} + ∣ t ∣/ σ_{n}) = O ((κ_{n}^{- 1} + λ_{n}^{- 1/2}) (1 + ∣ t ∣^{3}))$ , so $∣ ϕ_{n} (t) - e^{- t^{2} /2} ∣ \leq e^{- t^{2} /2} ∣ e^{R_{n} (t)} - 1∣ \leq C^{''} e^{- t^{2} /4} (κ_{n}^{- 1} + λ_{n}^{- 1/2}) (1 + ∣ t ∣^{3})$ for $∣ t ∣$ up to a fixed multiple of $σ_{n}$ . Integrating against $1/∣ t ∣$ over $R$ converges and is $O (κ_{n}^{- 1} + λ_{n}^{- 1/2})$ ; choosing $T ≍ σ_{n} ≍ λ_{n}$ makes the $C / T = O (λ_{n}^{- 1/2})$ tail subdominant. Summing the two contributions gives the stated rate. $□$

Proposition 5 (permutation-cycle Gaussian law). The number of cycles $X_{n}$ of a uniform random permutation satisfies $(X_{n} - ln n) / ln n d N (0, 1)$ .

Proof. The cycle-marked EGF is $F (z, u) = (1 - z)^{- u}$ (a permutation is a set of cycles, each cycle marked by $u$ , and the EGF of cycles is $lo g \frac{1}{1 - z}$ , so the SET gives $exp (u lo g \frac{1}{1 - z}) = (1 - z)^{- u}$ ). Thus $[z^{n}] F (z, u) = (n n + u - 1)$ and, since $[z^{n}] F (z, 1) = 1$ , $p_{n} (u) = (n n + u - 1) = \frac{Γ ( n + u )}{Γ ( u ) Γ ( n + 1 )}$ . The Gamma ratio asymptotic $Γ (n + u) /Γ (n + 1) \sim n^{u - 1}$ (uniform for $u$ in a neighbourhood of $1$ , by Stirling for $Γ$ ) gives $p_{n} (u) \sim \frac{1}{Γ ( u )} n^{u - 1} = \frac{1}{Γ ( u )} (e^{u - 1})^{l n n}$ , a quasi-power with $A (u) = 1/Γ (u)$ ( $A (1) = 1$ ), $B (u) = e^{u - 1}$ ( $B (1) = 1$ ), $λ_{n} = ln n \to \infty$ , $κ_{n} = ln n$ (the relative error in the Gamma ratio is $O (1/ n) = O (e^{- λ_{n}})$ , hence $O (κ_{n}^{- 1})$ ). Then $g_{B} (t) = lo g B (e^{t}) = e^{t} - 1$ , so $m (B) = 1$ , $v (B) = 1 \neq = 0$ . By Proposition 3, $(X_{n} - λ_{n}) / λ_{n} = (X_{n} - ln n) / ln n d N (0, 1)$ , with the exact mean $H_{n}$ and variance $H_{n} - H_{n}^{(2)}$ from Proposition 1 differing from $ln n$ by $O (1)$ , absorbed in the standardisation. $□$

Connections Master

This unit is the bivariate completion of the meromorphic coefficient asymptotics of 40.08.03: there a single dominant pole $ρ$ fixed the growth $ρ^{- n}$ of the counts; here the pole moves with the marking variable, $ρ = ρ (u)$ , and the curvature of $lo g ρ (u)$ at $u = 1$ is exactly the variance of the Gaussian limit law. The simple-pole coefficient asymptotic of that unit, applied uniformly in $u$ , is the engine of the meromorphic schema (Theorem 1 and Exercise 8), so the supercritical-sequence component count promised at the end of 40.08.03 is delivered here as a central limit theorem.
The companion unit 40.08.04 on singularity analysis supplies the other mechanism: when the dominant singularity is algebraic, $F (z, u) \sim c (u) (1 - z / ρ (u))^{- α (u)}$ , the transfer theorems of 40.08.04 give the uniform-in- $u$ coefficient asymptotic that the singularity-analysis schema (Theorem 2) feeds to the quasi-powers theorem; the movable exponent $α (u) = u$ with constant $ρ$ produces the logarithmic rate $λ_{n} = ln n$ of the permutation-cycle law, and the movable $ρ (u)$ produces the linear-in- $n$ laws of random trees and mappings. This unit and 40.08.04 are co-produced; 40.08.04 is the univariate transfer theory and this unit is its parametric distribution-valued reading.
The Gaussian conclusion is imported wholesale from the probability chapter: Lévy's continuity theorem 37.03.01 converts pointwise convergence of the PGF-derived characteristic functions into convergence in distribution, and the Lindeberg-Feller central limit theorem 37.03.02 is the prototype that the quasi-power $B (u)^{λ_{n}}$ imitates — a sum of $λ_{n}$ small almost-independent pieces. The Berry-Esseen rate of Proposition 4 is the combinatorial instance of the classical Berry-Esseen bound. The discrete regime of Theorem 4 connects forward to the Poisson-approximation and Janson-inequality methods of the probabilistic combinatorics chapter 40.07.07, reached here analytically through the bivariate generating function.
The Eulerian-polynomial descent law (Exercise 7) ties this unit to the permutation-statistics unit 40.01.05, whose real-rooted Eulerian polynomials $A_{n} (u)$ furnish the cleanest quasi-power certificate (a product of independent-bit PGFs); the saddle-point Gaussian of the co-prerequisite 40.08.06 is the univariate shadow of the quasi-powers Gaussian, the angle-direction collapse there mirrored by the marking-direction collapse here, and the Stirling/Laplace quadratic of 06.01.15 underlies both. The chapter's whole asymptotic toolkit — meromorphic, singularity-analysis, saddle-point — reappears here perturbed by a marking variable to yield the limit law of every markable parameter.

Historical & philosophical context Master

The recognition that combinatorial parameters obey limit laws begins with Goncharov's 1944 determination that the number of cycles of a random permutation is asymptotically normal with mean and variance $\sim ln n$ , and with the parallel number-theoretic discovery by Erdős and Kac (1940) that the number of distinct prime factors $ω (N)$ of a random integer below $x$ is asymptotically normal with mean and variance $\sim ln ln x$ — the Erdős-Kac theorem, the founding instance of "probabilistic number theory" and a structural twin of the cycle law (both are sums of nearly independent indicators with logarithmic rate). Erdős and Turán's 1965-67 papers on the statistical theory of the symmetric group consolidated the cycle and order statistics of random permutations ^{[Flajolet-Sedgewick §IX.9]}.

The analytic derivation of such laws directly from generating functions, rather than by the method of moments, was inaugurated by Edward Bender's 1973 paper Central and local limit theorems applied to asymptotic enumeration ^{[Bender 1973]}, which showed that a bivariate generating function with a smoothly moving dominant singularity forces a Gaussian limit, and gave the local-limit refinement. Bender and Richmond, and later Michael Drmota and Hsien-Kuei Hwang, extended and quantified the framework. Hwang's 1994 thesis and his 1998 paper ^{[Hwang 1998]} abstracted the common hypothesis into the quasi-powers theorem: a uniform expansion $p_{n} (u) = A (u) B (u)^{λ_{n}} (1 + O (κ_{n}^{- 1}))$ on a complex neighbourhood of $u = 1$ yields the Gaussian law together with a Berry-Esseen convergence rate $O (κ_{n}^{- 1} + λ_{n}^{- 1/2})$ , unifying the meromorphic and singularity-analysis schemata under one analytic criterion. The codification within analytic combinatorics, organising the limit laws by the two singularity mechanisms and the growth of $λ_{n}$ , is due to Philippe Flajolet and Robert Sedgewick, whose Analytic Combinatorics (2009) Chapter IX is the reference treatment ^{[Flajolet-Sedgewick Ch. IX]}.

Bibliography Master

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

@article{bender1973central,
  author  = {Bender, Edward A.},
  title   = {Central and local limit theorems applied to asymptotic enumeration},
  journal = {Journal of Combinatorial Theory, Series A},
  volume  = {15},
  year    = {1973},
  pages   = {91--111}
}

@article{hwang1998convergence,
  author  = {Hwang, Hsien-Kuei},
  title   = {On convergence rates in the central limit theorems for combinatorial structures},
  journal = {European Journal of Combinatorics},
  volume  = {19},
  year    = {1998},
  pages   = {329--343}
}

@phdthesis{hwang1994thesis,
  author  = {Hwang, Hsien-Kuei},
  title   = {Th\'{e}or\`{e}mes limites pour les structures combinatoires et les fonctions arithm\'{e}tiques},
  school  = {\'{E}cole Polytechnique},
  year    = {1994}
}

@article{erdoskac1940,
  author  = {Erd\H{o}s, Paul and Kac, Mark},
  title   = {The Gaussian law of errors in the theory of additive number theoretic functions},
  journal = {American Journal of Mathematics},
  volume  = {62},
  year    = {1940},
  pages   = {738--742}
}

@book{drmota2009random,
  author    = {Drmota, Michael},
  title     = {Random Trees: An Interplay between Combinatorics and Probability},
  publisher = {Springer},
  year      = {2009}
}

Prerequisites

40.08.06
40.08.03

Tier anchors

beginner: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. IX read for the picture-first story — a parameter of a random object (the number of cycles of a permutation, the number of blocks of a set partition) as a quantity that fluctuates from object to object, and the empirical observation that, once it is a sum of many small almost-independent contributions, its histogram is bell-shaped; Sedgewick-Flajolet 2013 *An Introduction to the Analysis of Algorithms* 2e (Addison-Wesley) Ch. 8 for the bivariate-generating-function bookkeeping with a marking variable
intermediate: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) §IX.1-IX.5: bivariate generating functions $F(z,u)$ marking a parameter, the extraction $\mathbb{E}[u^{X_n}] = [z^n]F(z,u)/[z^n]F(z,1)$ of the probability generating function of $X_n$, the moment-by-differentiation calculus, and Hwang's quasi-powers theorem with its Gaussian conclusion and Berry-Esseen speed; Hwang 1998 *On convergence rates in the central limit theorems for combinatorial structures* (European J. Combin. 19) for the quantitative statement
master: Flajolet-Sedgewick 2009 *Analytic Combinatorics* (Cambridge) Ch. IX in full — the bivariate-GF framework, the perturbed meromorphic schema (movable simple pole $\rho(u)$, §IX.6) and the perturbed singularity-analysis / algebraic-singularity schema (movable singularity, §IX.7), Hwang's quasi-powers theorem (§IX.5) and its Berry-Esseen and local-limit refinements, and the canonical worked laws: cycles in permutations (Goncharov, Erdős-Turán), components, descents (Eulerian), patterns and the Poisson regime; Hwang 1994 *Théorèmes limites pour les structures combinatoires et les fonctions arithmétiques* (Thèse, École Polytechnique); Bender 1973 *Central and local limit theorems applied to asymptotic enumeration* (J. Combin. Theory A 15)

References

Flajolet, P. & Sedgewick, R. — Analytic Combinatorics · Cambridge University Press (2009), Chapter IX 'Multivariate Asymptotics and Limit Laws' is the source for this unit. §IX.1 introduces a combinatorial parameter $\chi$ on a class $\mathcal{F}$ and the bivariate generating function $F(z,u) = \sum_{\omega\in\mathcal{F}} z^{|\omega|}u^{\chi(\omega)}$, with the marking variable $u$ recording the parameter; the parameter restricted to size-$n$ objects becomes a sequence of random variables $X_n$ under the uniform distribution, whose probability generating function is $p_n(u) = \mathbb{E}[u^{X_n}] = \frac{[z^n]F(z,u)}{[z^n]F(z,1)}$. §IX.2 develops the moment calculus: $\mathbb{E}[X_n] = p_n'(1)$, $\mathrm{Var}(X_n) = p_n''(1) + p_n'(1) - p_n'(1)^2$, computed by differentiating $F(z,u)$ in $u$ at $u=1$ and extracting coefficients, often via the singularity in $z$ of $\partial_u F(z,1)$. §IX.3-IX.4 treat the mean and variance asymptotics from the singular structure of $F(z,u)$. §IX.5 is the quasi-powers theorem (Hwang's theorem): if the PGFs satisfy $p_n(u) = A(u)\,B(u)^{\lambda_n}\big(1 + O(\kappa_n^{-1})\big)$ uniformly for $u$ in a complex neighbourhood of $1$, with $A,B$ analytic, $A(1)=B(1)=1$, $\lambda_n\to\infty$, $\kappa_n\to\infty$, and the variability condition that $\mathfrak{v}(B) = B''(1)/B(1) + B'(1)/B(1) - (B'(1)/B(1))^2 \neq 0$, then $X_n$ is asymptotically Gaussian with mean $\sim \lambda_n\, B'(1)/B(1)$ and variance $\sim \lambda_n\,\mathfrak{v}(B)$, and the speed of convergence to the normal law is $O(\kappa_n^{-1} + \lambda_n^{-1/2})$ in the Kolmogorov (sup-norm) distance — a Berry-Esseen bound. §IX.6 is the meromorphic schema: when $F(z,u) = \frac{N(z,u)}{D(z,u)}$ has a movable simple pole $z = \rho(u)$ depending analytically on $u$ with $\rho(1)$ the dominant pole at $u=1$, then $p_n(u) \sim C(u)\,(\rho(1)/\rho(u))^n$, a quasi-power with $\lambda_n = n$ and $B(u) = \rho(1)/\rho(u)$, so $X_n$ is Gaussian with mean and variance LINEAR in $n$ (supercritical sequences/compositions, the number of components). §IX.7 is the singularity-analysis schema: when $F(z,u)$ has a movable algebraic singularity $z = \rho(u)$ with $F(z,u) \sim c(u)(1 - z/\rho(u))^{-\alpha}$ (or a logarithmic one), the same quasi-power structure with $\lambda_n = n$ or $\lambda_n = \ln n$ gives a Gaussian law (mappings, the number of cycles, the number of parts of a partition into distinct parts). §IX.8-IX.11 work the catalogue: the number of cycles of a random permutation, Gaussian with mean $\sim \ln n$ and variance $\sim \ln n$ (Goncharov; the Erdős-Turán law); the number of summands/components; the number of descents (Eulerian numbers, cross-ref 40.01.05), Gaussian with mean $(n-1)/2$ and variance $(n+1)/12$; the number of nodes of given degree and the profile of random trees; and the discrete (Poisson) limit laws for rare patterns where $\lambda_n$ stays bounded. The chapter distinguishes the central limit theorem (convergence of the distribution function) from the local limit theorem (convergence of the individual probabilities $\mathbb{P}(X_n = k)$ to the Gaussian density), the latter requiring a stronger 'no-oscillation' condition on $p_n(u)$ on $|u|=1$.
Hwang, H.-K. — On convergence rates in the central limit theorems for combinatorial structures · European Journal of Combinatorics 19 (1998), pp. 329-343. States and proves the quasi-powers theorem in quantitative form: under $p_n(u) = e^{\lambda_n U(u) + V(u)}\big(1 + O(\kappa_n^{-1})\big)$ uniform on a fixed complex neighbourhood of $u=1$ with $\lambda_n\to\infty$, $U,V$ analytic and $U''(0)+U'(0)\neq 0$ in the standardised parametrisation, the normalised variable $(X_n - \lambda_n U'(0))/\sqrt{\lambda_n(U''(0)+U'(0))}$ converges to the standard normal with Kolmogorov-distance error $O(\kappa_n^{-1} + \lambda_n^{-1/2})$. The proof goes through the characteristic function: setting $u = e^{it/\sigma_n}$ turns the PGF into the characteristic function of the standardised variable, the quasi-power form gives $\mathbb{E}[e^{it(X_n-\mu_n)/\sigma_n}] \to e^{-t^2/2}$ pointwise, Lévy's continuity theorem (cross-ref 37.03.01) yields convergence in distribution, and the Berry-Esseen inequality applied to the explicit characteristic-function approximation supplies the rate. Includes the local-limit refinement under an added condition controlling $|p_n(u)|$ away from $u=1$ on the unit circle, and applications to the number of distinct prime factors $\omega(n)$ (Erdős-Kac), the number of cycles and the number of components of combinatorial structures.
Bender, E. A. — Central and local limit theorems applied to asymptotic enumeration · Journal of Combinatorial Theory, Series A 15 (1973), pp. 91-111. The originating paper for the analytic derivation of combinatorial limit laws. Bender shows that if a bivariate generating function $F(z,u) = \sum_{n,k} a_{n,k} z^n u^k$ has, for each $u$ near $1$, a dominant singularity $z = \rho(u)$ depending smoothly on $u$, and $[z^n]F(z,u) \sim c(u)\,\rho(u)^{-n} n^{s}$ uniformly, then the coefficients $a_{n,k}/\sum_k a_{n,k}$ obey a central limit theorem: the parameter $X_n$ with $\mathbb{P}(X_n=k) = a_{n,k}/a_n$ is asymptotically normal with mean $\sim -n\,\rho'(1)/\rho(1)$ and variance $\sim n\big(-\rho''(1)/\rho(1) - \rho'(1)/\rho(1) + (\rho'(1)/\rho(1))^2\big)$, derived by expanding $\ln\rho(u)$ at $u=1$ and recognising $\rho(1)^n/\rho(e^{it/\sigma\sqrt n})^n \to e^{-t^2/2}$. The paper also gives the local-limit version under a ratio condition on the $a_{n,k}$ in $k$, and the worked cases of Stirling numbers, the number of parts in partitions, and runs/descents in permutations — the analytic blueprint that Hwang's quasi-powers theorem later abstracted and quantified.

Estimated time

beginner: 23m
intermediate: 55m
master: 96m