Asymptotics of Tree Families and Simple Varieties of Trees

Intuition Beginner

A tree family is a single recipe for building trees: a root carries some number of smaller trees of the same kind, and a fixed rule says how many children a node may have. Plain branching trees allow any number of children; binary trees allow zero or two; Motzkin trees allow zero, one, or two. Each rule produces its own family, and each family has its own count of trees of a given size. This unit asks one question about every such family at once: as the trees grow large, how does the count grow?

The headline is a surprise. The growth rate — the base raised to the power $n$ — changes from family to family. But a second, finer factor in the count does not change: every one of these families carries the same correction $1$ over $n$ times the square root of $n$, written $n^{-3/2}$. Plain trees, binary trees, labelled trees, Motzkin trees: different bases, the same $n^{-3/2}$ tail. This shared factor is the universal tree-counting law, and it is the main character of the unit.

Why should families this different agree on anything? The reason is a kind of self-similarity. Because each tree is a root carrying smaller copies of the same object, the recipe folds back on itself, and that folding has the same shape no matter what the child rule is. Almost all large trees in a family look alike at scale — they share one typical silhouette — and that common silhouette is what forces the common $n^{-3/2}$ law.

Visual Beginner

Picture the count of size-$n$ trees plotted against $n$ for three families on the same chart. Each curve climbs roughly like its own base to the power $n$ — a steep exponential — so on a plain chart the three curves race off at different rates and you learn nothing more. The shared structure is hidden underneath the exponential.

Now strip each curve of its own exponential by dividing the count by that family's base raised to $n$. The three rescaled curves stop racing and settle onto one common shape, a slow decay that behaves like $n^{-3/2}$. That collapse is the picture of universality: once you remove the family-specific growth base, what remains is the same for everybody.

tree family	child rule	growth base	shared tail
plain (general) trees	any number of children	$4$	$n^{-3/2}$
binary trees	$0$ or $2$ children	$4$	$n^{-3/2}$
Motzkin trees	$0$, $1$, or $2$ children	$3$	$n^{-3/2}$
labelled (Cayley) trees	any, children unordered	$e$	$n^{-3/2}$

The base depends on the rule; the tail does not. A reader who remembers only one thing should remember that last column.

Worked example Beginner

Let us watch the universal tail appear in the most familiar family: plain branching trees, counted by the Catalan numbers. The number of plain trees with $n$ edges is $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. We will check that for large $n$ this behaves like a constant times $4^n$ times $n^{-3/2}$.

Step 1. Write out a few Catalan numbers: $C_1=1$, $C_2=2$, $C_3=5$, $C_4=14$, $C_5=42$, $C_6=132$, $C_7=429$, $C_8=1430$.

Step 2. Pull out the growth base. Divide each $C_n$ by $4^n$: for $n=6$, $C_6/4^6=132/4096\approx 0.03223$; for $n=7$, $429/16384\approx 0.02619$; for $n=8$, $1430/65536\approx 0.02182$. The numbers shrink, so the base $4$ slightly overshoots — there is a decaying correction left over.

Step 3. Identify the correction. Multiply what is left by $n$ times the square root of $n$, that is by $n^{3/2}$: for $n=6$, $0.03223\times 6^{1.5}\approx 0.03223\times 14.70\approx 0.474$; for $n=8$, $0.02182\times 8^{1.5}\approx 0.02182\times 22.63\approx 0.494$. These level off near a constant, about $0.5$.

Step 4. Compare with the predicted constant. The clean prediction is $C_n\approx \frac{1}{\sqrt{\pi }}{4}^n{n}^{-3/2}$, and $1/\sqrt{\pi }\approx 0.564$; the slow drift of our numbers toward roughly $0.5$ and on up is consistent with that limit (the approach is gradual). The base $4$ and the tail $n^{-3/2}$ are exactly what the universal law predicts.

What this tells us: a family-specific base ($4$ for plain trees) sets the exponential, and once you remove it the leftover is the universal $n^{-3/2}$ shape — the same tail every simple tree family carries.

Check your understanding Beginner

Formal definition Intermediate+

A simple variety of trees (equivalently a simply generated family) is fixed by a degree-generating function $\varphi (y)={\sum }_{k\ge 0}{\varphi }_k{y}^k$ with ${\varphi }_0>0$ and nonnegative coefficients, not reducing to ${\varphi }_0+{\varphi }_{1}y$. Its counting generating function $y(z)={\sum }_n{y}_n{z}^n$ is the unique formal power series with $y(0)=0$ solving the implicit equation $$ y(z) = z,\phi\big(y(z)\big). $$ Combinatorially ${\varphi }_k$ weights a node with $k$ subtrees, and the equation reads "a tree is a root carrying a $\varphi$-weighted sequence (or set) of subtrees," the catalytic recursion of 40.01.07. Plane trees take $\varphi (y)=\frac{1}{1-y}$ (any number of ordered children); binary trees $\varphi (y)=(1+y{)}^2$; unary-binary (Motzkin) trees $\varphi (y)=1+y+y^2$; labelled (Cayley) trees $\varphi (y)=e^y$, giving the tree function $T=z{e}^T$ of 40.01.07.

The structural object is the inverse function. Since ${\varphi }_0\ne 0$, the relation $y=z\varphi (y)$ inverts near the origin to $$ z = \psi(y) := \frac{y}{\phi(y)}, \qquad \psi(0) = 0,\ \psi'(0) = \frac{1}{\phi(0)} \ne 0, $$ so $y(z)$ is the compositional inverse of $\psi$, analytic where ${\psi }^{\prime }$ stays nonzero. The characteristic value $\tau$ is the smallest positive solution, inside the disc of convergence of $\varphi$, of $$ \psi'(\tau) = 0 \iff \phi(\tau) - \tau,\phi'(\tau) = 0 \iff \frac{\tau,\phi'(\tau)}{\phi(\tau)} = 1, $$ and the dominant singularity of $y$ sits at $\rho =\psi (\tau )=\tau /\varphi (\tau )=\varphi (\tau )/{\varphi }^{\prime }(\tau )$. The notation $[z^n]$, $\sqrt{\cdot }$ for the principal branch, $\rho$ (dominant-singularity modulus), and $\tau$ (characteristic value) is recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "Any $\varphi$ gives a square-root singularity." The characteristic equation $\tau {\varphi }^{\prime }(\tau )=\varphi (\tau )$ must have a positive root inside the disc of convergence of $\varphi$, with ${\psi }^{\prime \prime }(\tau )\ne 0$ (the smooth, or "irreducible-quadratic", case). For $\varphi (y)=e^y$ the root is $\tau =1<\infty$; for $\varphi$ a polynomial of degree $\ge 2$ a root exists. Linear $\varphi ={\varphi }_0+{\varphi }_{1}y$ (paths) has no such root — there is no branching, hence no square root.

• "The singularity is a pole, as in the meromorphic case." It is an algebraic branch point of square-root type, not a pole: $y$ stays finite at $\rho$, equal to $\tau$, but its derivative blows up. The residue calculus of 40.08.03 does not apply; the square-root transfer of the companion singularity-analysis unit does.

• "$\rho$ is where $\varphi$ blows up." Generally $\rho <$ radius of $\varphi$. The singularity is created by the inversion failing (${\psi }^{\prime }=0$), not by $\varphi$ itself becoming singular. For $\varphi =e^y$ (entire), $\rho =1/e$ comes purely from ${\psi }^{\prime }(\tau )=0$.

• "Periodicity never intrudes." If $\varphi (y)=\eta (y^d)$ for some $d\ge 2$ (e.g. only even child-counts allowed), then $y(z)$ has $d$ singularities on $|z|=\rho$ and the coefficients vanish off a residue class; the $n^{-3/2}$ law then holds along the supported class. Aperiodicity ($\gcd$ of supported degrees $=1$) restores a unique dominant singularity.

Key theorem with proof Intermediate+

The signature theorem is the square-root singularity and universal $n^{-3/2}$ law for a simple variety of trees: the inverse-function schema forces an algebraic branch point of exponent $\frac{1}{2}$, and the singularity-analysis transfer reads off the universal subexponential factor ^{[Flajolet-Sedgewick Ch. VII.3]}.

Theorem (singular expansion and tree asymptotics). Let $\varphi$ have nonnegative coefficients, ${\varphi }_0>0$, be aperiodic, and admit a positive root $\tau$ of $\tau {\varphi }^{\prime }(\tau )=\varphi (\tau )$ inside its disc of convergence, with ${\varphi }^{\prime \prime }(\tau )>0$. Let $\rho =\tau /\varphi (\tau )$. Then $y(z)$ defined by $y=z\varphi (y)$ is analytic in $|z|<\rho$, has its unique dominant singularity at $\rho$, and admits the singular expansion $$ y(z) = \tau - c\sqrt{1 - z/\rho} + O!\big(1 - z/\rho\big), \qquad c = \sqrt{\frac{2,\phi(\tau)}{\phi''(\tau)}}. $$ Consequently, by the square-root transfer $[z^n](1-z/\rho {)}^{1/2}\sim -\frac{1}{2\sqrt{\pi }}{\rho }^{-n}{n}^{-3/2}$, $$ [z^n],y(z) ;\sim; \frac{c}{2\sqrt\pi};\rho^{-n},n^{-3/2} ;=; \sqrt{\frac{\phi(\tau)}{2\pi,\phi''(\tau)}};\rho^{-n},n^{-3/2}. $$

Proof. Set $\psi (y)=y/\varphi (y)$, so $z=\psi (y)$ and $y(z)={\psi }^{-1}(z)$. Compute $$ \psi'(y) = \frac{\phi(y) - y\phi'(y)}{\phi(y)^2}, $$ which vanishes exactly when $\varphi (y)=y{\varphi }^{\prime }(y)$; by hypothesis the least positive such $y$ in the disc of convergence of $\varphi$ is $\tau$, and $\psi (\tau )=\rho$. Because $\varphi$ has nonnegative coefficients, $\psi$ is increasing on $(0,\tau )$ (there ${\psi }^{\prime }>0$), so $y(z)$ is real-analytic and increasing for $z\in (0,\rho )$, rising to $y({\rho }^{-})=\tau$; the inverse exists and is analytic wherever ${\psi }^{\prime }\ne 0$, hence on $|z|<\rho$. The point $\rho$ is the dominant singularity: ${\psi }^{\prime }(\tau )=0$ obstructs analytic inversion there, and aperiodicity (with Pringsheim's theorem of 40.08.03 forcing a positive-axis singularity for the nonnegative-coefficient series $y$) makes it the unique singularity of modulus $\rho$.

Near $\tau$ expand $\psi$ to second order. Since ${\psi }^{\prime }(\tau )=0$, $$ z = \psi(y) = \psi(\tau) + \tfrac12\psi''(\tau)(y - \tau)^2 + O!\big((y-\tau)^3\big) = \rho + \tfrac12\psi''(\tau)(y-\tau)^2 + \cdots . $$ A direct computation from $\psi =y/\varphi$ gives ${\psi }^{\prime \prime }(\tau )=\frac{\tau {\varphi }^{\prime \prime }(\tau )}{\varphi (\tau {)}^2}$ at the characteristic value (the first-derivative terms cancel because $\varphi (\tau )=\tau {\varphi }^{\prime }(\tau )$). Solving the quadratic relation for $y-\tau$, $$ (y - \tau)^2 = \frac{2(z - \rho)}{\psi''(\tau)} = \frac{-2\rho,(1 - z/\rho)}{\psi''(\tau)}, \qquad y - \tau = -\sqrt{\frac{2\rho}{\psi''(\tau)}};\sqrt{1 - z/\rho}, $$ the negative branch chosen because $y$ increases to $\tau$ from below as $z\uparrow \rho$. Substituting ${\psi }^{\prime \prime }(\tau )=\tau {\varphi }^{\prime \prime }(\tau )/\varphi (\tau {)}^2$ and $\rho =\tau /\varphi (\tau )$ gives $\frac{2\rho }{{\psi }^{\prime \prime }(\tau )}=\frac{2(\tau /\varphi (\tau ))\varphi (\tau {)}^2}{\tau {\varphi }^{\prime \prime }(\tau )}=\frac{2\varphi (\tau )}{{\varphi }^{\prime \prime }(\tau )}$, so $c=\sqrt{2\varphi (\tau )/{\varphi }^{\prime \prime }(\tau )}$, establishing the singular expansion. Higher-order terms in the Taylor expansion of $\psi$ produce the $O(1-z/\rho )$ remainder. The transfer $[z^n](1-z/\rho {)}^{\alpha }\sim \frac{{\rho }^{-n}{n}^{-\alpha -1}}{\Gamma (-\alpha )}$ with $\alpha =\frac{1}{2}$ and $\Gamma (-\frac{1}{2})=-2\sqrt{\pi }$ gives $[z^n]\sqrt{1-z/\rho }\sim -\frac{1}{2\sqrt{\pi }}{\rho }^{-n}{n}^{-3/2}$; the constant $\tau$ contributes nothing past $n=0$ and the remainder contributes $O({\rho }^{-n}{n}^{-2})$, so $[z^n]y\sim \frac{c}{2\sqrt{\pi }}{\rho }^{-n}{n}^{-3/2}$. $\square$

Corollary (general plane / Catalan case). For $\varphi (y)=(1-y{)}^{-1}$, the equation $\tau {\varphi }^{\prime }(\tau )=\varphi (\tau )$ is $\frac{\tau }{(1-\tau {)}^2}=\frac{1}{1-\tau }$, giving $\tau =\frac{1}{2}$, $\varphi (\tau )=2$, $\rho =\tau /\varphi (\tau )=\frac{1}{4}$, and ${\varphi }^{\prime \prime }(\tau )=2(1-\tau {)}^{-3}=16$, so $c=\sqrt{2\cdot 2/16}=\frac{1}{2}$ and $[z^n]y\sim \frac{1/2}{2\sqrt{\pi }}{4}^n{n}^{-3/2}=\frac{1}{4\sqrt{\pi }}{4}^n{n}^{-3/2}$, matching the Catalan asymptotic $C_n\sim \frac{1}{\sqrt{\pi }}{4}^n{n}^{-3/2}$ after the edge/node index shift.

Bridge. This theorem is the foundational reason every simple variety of trees obeys one universal law: the family-specific data $\varphi$ enters only through the two numbers $\rho$ (the growth base) and $c$ (the amplitude), while the exponent $-\frac{3}{2}$ is fixed by the square-root type of the singularity, which the inverse-function schema produces for every branching family. This is exactly the second principle of 40.08.03 — singularity type fixes the subexponential factor — instantiated with an algebraic branch point in place of a pole; the meromorphic $n^{m-1}$ of 40.08.03 is replaced by $n^{-3/2}$ because $\sqrt{1-z/\rho }$ replaces $(1-z/\rho {)}^{-m}$. The construction builds toward the height and profile theory of the Advanced results, where the same $\tau ,\varphi (\tau ),{\varphi }^{\prime \prime }(\tau )$ that fix $\rho$ and $c$ reappear as the variance scaling the $\sqrt{\pi n}$ height law, and it appears again in the Drmota-Lalley-Woods theorem, where a whole positive system shares one square-root singularity. The central insight is that the singularity of $y$ comes from the inversion ${\psi }^{\prime }=0$, not from $\varphi$, so it generalises the Lagrange-inversion residue form of 40.01.07: Lagrange inversion gives the exact coefficient $[z^n]y=\frac{1}{n}[{\lambda }^{n-1}]\varphi (\lambda {)}^n$, and differentiating the singularity of the inverse is what turns that exact form into the $n^{-3/2}$ asymptotic. Putting these together, the exact enumeration of 40.01.07 and the asymptotic law here are the algebraic and analytic faces of the same fixed-point equation $y=z\varphi (y)$.

Exercises Intermediate+

Advanced results Master

Beyond the singular expansion, the theory of simple varieties extends to the height and width laws governed by the Airy / Brownian-excursion limit, to the additive-functional transfer, and to the universality of the square-root singularity across positive polynomial systems.

Theorem 1 (universal singular expansion, restated with error terms). Under the hypotheses of the Key theorem, $y(z)$ admits a full singular expansion in powers of $(1-z/\rho {)}^{1/2}$: $$ y(z) = \tau - c_1(1 - z/\rho)^{1/2} + c_2(1 - z/\rho) - c_3(1 - z/\rho)^{3/2} + \cdots, \quad c_1 = \sqrt{\tfrac{2\phi(\tau)}{\phi''(\tau)}}, $$ convergent in a $\Delta$-domain (a slit disc) about $\rho$, so that singularity-analysis transfer yields a complete asymptotic expansion $[z^n]y={\rho }^{-n}(\frac{c_1}{2\sqrt{\pi }}{n}^{-3/2}+d{n}^{-5/2}+\cdots )$, the odd half-integer powers of $(1-z/\rho )$ supplying the visible $n^{-3/2},n^{-5/2},\dots$ scale and the integer powers contributing nothing past constants ^{[Flajolet-Sedgewick Ch. VII.3]}.

Theorem 2 (height of random trees, $\sqrt{\pi n}$ law). Let $H_n$ be the height of a uniformly random tree of size $n$ in a simple variety with offspring variance ${\sigma }^2={\tau }^2{\varphi }^{\prime \prime }(\tau )/\varphi (\tau )$ (the variance of the size-biased offspring law attached to $\varphi$). Then $$ \mathbb{E}[H_n] \sim \sqrt{\frac{\pi}{\sigma^2}};\sqrt{n} = \sqrt{\pi n}\cdot\sigma^{-1}, \qquad \frac{H_n}{\sqrt{n}} \xrightarrow{d} \sigma^{-1}\max_{0\le t\le 1} \mathbf{e}(t), $$ where $\mathbf{e}$ is the standard Brownian excursion; the limit law of $\sigma H_n/\sqrt{n}$ is the theta distribution $\mathbb{P}(\max \mathbf{e}\le x)={\sum }_k(1-2k^2{x}^2)e^{-k^2{x}^2}$-type expansion, with all moments expressible through the Airy function. The plane-tree (${\sigma }^2=2$) value is $\mathbb{E}[H_n]\sim \sqrt{\pi n/2}$ ^{[Meir-Moon 1978, Flajolet-Sedgewick Ch. VII.10]}.

Theorem 3 (width and the profile process). Let $W_n(\xi )$ count nodes at depth $\lfloor \xi \sqrt{n}\rfloor$ in a random size-$n$ tree of the variety. The rescaled profile $n^{-1/2}{W}_n(\xi \sqrt{n})$ converges, as a process in $\xi$, to $\sigma {\ell }_{\sigma \xi }(\mathbf{e})$, the local time at level $\sigma \xi$ of the normalised Brownian excursion; consequently the width ${\max }_d{W}_n(d)\sim \kappa \sqrt{n}$ with a constant $\kappa$ expressible through the Airy distribution, and the total path length (sum of depths) is of order $n^{3/2}$ with an Airy-distributed limit law. These are the continuum-random-tree (Aldous CRT) readings of the same square-root singularity ^{[Drmota 2009 Ch. 4]}.

Theorem 4 (additive functionals and the transfer). For an additive functional $F(t)={\sum }_{v}f(\text{subtree at }v)$ with toll $f$ of subtree-generating function $\hat{f}(z)$, the expected value over random size-$n$ trees transfers through the same square-root singularity: if $\hat{f}$ has a singular contribution $\sim a(1-z/\rho {)}^{\beta }$, then $\mathbb{E}[F]/n$ acquires growth governed by $\beta$ relative to the $\frac{1}{2}$ of $y$. Tolls with $\hat{f}$ analytic at $\rho$ give $\mathbb{E}[F]\sim \mu n$ (linear, additive over a typical fringe), while critical tolls (e.g. subtree-size sums) push the order to $n^{3/2}$, matching the path-length scale of Theorem 3 ^{[Flajolet-Sedgewick Ch. VII.4]}.

Theorem 5 (Drmota-Lalley-Woods, positive systems). Let $\mathbf{y}=(y_1,\dots ,y_m)$ solve a polynomial system $\mathbf{y}=\mathbf{\Phi }(z,\mathbf{y})$ with $\mathbf{\Phi }$ having nonnegative coefficients, that is proper (${\Phi }_j(0,0)=0$, no $\frac{\partial {\Phi }_j}{\partial y_i}(0,0)$ summing to identity), strongly connected (the dependency digraph among the $y_i$ is strongly connected), and aperiodic. Then all components $y_j$ share a common dominant singularity $\rho$, each has a square-root singular expansion $y_j(z)={\tau }_j-c_j\sqrt{1-z/\rho }+\cdots$, and consequently $$ [z^n],y_j(z) ;\sim; \frac{c_j}{2\sqrt\pi},\rho^{-n},n^{-3/2} $$ for every $j$, with $\rho$ determined by the vanishing of the Jacobian determinant $\det (I-{\partial }_{\mathbf{y}}\mathbf{\Phi })$ at the characteristic point. The single-equation tree theorem is the case $m=1$; the systems theorem extends the universal $n^{-3/2}$ law to context-free specifications, families of mutually recursive trees, and many maps and lattice-path classes ^{[Flajolet-Sedgewick Ch. VII.6, Drmota 2009 Ch. 8]}.

Synthesis. The universal $n^{-3/2}$ law is the foundational reason "simple variety of trees" is a single asymptotic phenomenon rather than a list of cases: every branching family is an inverse-function schema $y=z\varphi (y)$, the inversion fails at the characteristic point ${\psi }^{\prime }(\tau )=0$, and a smooth stationary point is generically quadratic, so the inverse is a square root and the transfer reads off $n^{-3/2}$ regardless of $\varphi$. The central insight is that the family enters only through $\rho =\tau /\varphi (\tau )$ and the amplitude $c=\sqrt{2\varphi (\tau )/{\varphi }^{\prime \prime }(\tau )}$, while the exponent is locked by the singularity type — this is exactly the second principle of 40.08.03, now with an algebraic branch point in place of a pole, and it is dual to the meromorphic case where the type is a pole and the factor is the integer-power $n^{m-1}$.

Putting these together, the same $\tau ,\varphi (\tau ),{\varphi }^{\prime \prime }(\tau )$ that fix the count's amplitude fix the offspring variance ${\sigma }^2={\tau }^2{\varphi }^{\prime \prime }(\tau )/\varphi (\tau )$, so the $\sqrt{\pi n}$ height law, the Brownian-excursion profile, and the Airy path-length distribution all read off the same local data as the coefficient asymptotic; the bridge is that the singular expansion's coefficient $c$ and the limit-process's scaling $\sigma$ are two extractions from one second-order Taylor expansion of $\psi$. This generalises the Lagrange-inversion exact form of 40.01.07 — which gives $[z^n]y=\frac{1}{n}[{\lambda }^{n-1}]\varphi (\lambda {)}^n$ exactly — into its asymptotic shadow, and the Drmota-Lalley-Woods theorem generalises the single $\varphi$ to an entire strongly connected positive system sharing one square-root singularity, so the universality is not an accident of one equation but the structural fact of positive algebraic systems: a strongly connected branching mechanism has exactly one critical point, and its smoothness forces the square root.

Full proof set Master

Proposition 1 (existence and location of the characteristic value). Let $\varphi$ have nonnegative coefficients, ${\varphi }_0>0$, ${\varphi }_k>0$ for some $k\ge 2$, and radius of convergence $R\in (0,\infty ]$. Then $h(y):=y{\varphi }^{\prime }(y)/\varphi (y)$ is continuous and strictly increasing on $(0,R)$ with $h(0^{+})=0$; if $h(y)\to L>1$ as $y\uparrow R$ (or $L=\infty$), there is a unique $\tau \in (0,R)$ with $h(\tau )=1$, equivalently ${\psi }^{\prime }(\tau )=0$.

Proof. On $(0,R)$, $\varphi (y)>0$ and ${\varphi }^{\prime }(y)>0$ (positive coefficients, $\varphi$ nonconstant), so $h$ is well-defined and positive. Write $h(y)=\frac{{\sum }_{k}k{\varphi }_k{y}^k}{{\sum }_k{\varphi }_k{y}^k}$, the mean of the random variable $K$ with $\mathbb{P}(K=k)\propto {\varphi }_k{y}^k$. Its derivative is $h^{\prime }(y)=\frac{1}{y}\mathrm{Var}(K)>0$ (a standard exponential-family computation: $h$ is the mean of a tilted law and its $y$-derivative is the variance over $y$), so $h$ strictly increases. As $y\to 0^{+}$ the law concentrates on $k=0$, so $h(0^{+})=0$. By the intermediate value theorem, $h(\tau )=1$ has a unique solution $\tau \in (0,R)$ precisely when the limit $L={\lim }_{y\uparrow R}h(y)>1$. Then ${\psi }^{\prime }(\tau )=\frac{\varphi (\tau )-\tau {\varphi }^{\prime }(\tau )}{\varphi (\tau {)}^2}=\frac{\varphi (\tau )}{\varphi (\tau {)}^2}(1-h(\tau ))=0$. $\square$

Proposition 2 (square-root singular expansion). At $\tau$ from Proposition 1 with ${\psi }^{\prime \prime }(\tau )\ne 0$, the inverse $y={\psi }^{-1}$ satisfies $y(z)=\tau -\sqrt{2\rho /|{\psi }^{\prime \prime }(\tau )|}\sqrt{1-z/\rho }(1+o(1))$ as $z\to {\rho }^{-}$, with $\rho =\psi (\tau )$ and $\sqrt{2\rho /|{\psi }^{\prime \prime }(\tau )|}=\sqrt{2\varphi (\tau )/{\varphi }^{\prime \prime }(\tau )}$.

Proof. Since $\psi$ is analytic at $\tau$ with ${\psi }^{\prime }(\tau )=0$, ${\psi }^{\prime \prime }(\tau )\ne 0$, the Weierstrass/Morse normal form gives an analytic change of variable: there is $u(y)=(y-\tau )\sqrt{{\psi }^{\prime \prime }(\tau )/2}(1+O(y-\tau ))$, analytic and invertible near $\tau$, with $\psi (y)-\rho =u(y{)}^2$. Hence $z-\rho =u^2$ and $u=\pm \sqrt{z-\rho }$; inverting $u(y)$ gives $y-\tau =u\sqrt{2/{\psi }^{\prime \prime }(\tau )}(1+O(u))$. For real $z\uparrow \rho$ with $y\uparrow \tau$ from below, $y-\tau <0$, and $z-\rho =-\rho (1-z/\rho )<0$, so $u=\sqrt{z-\rho }$ is imaginary; choosing the branch that keeps $y$ real and increasing yields $y-\tau =-\sqrt{2/|{\psi }^{\prime \prime }(\tau )|}\sqrt{\rho }\sqrt{1-z/\rho }(1+o(1))$. The constant is $\sqrt{2\rho /|{\psi }^{\prime \prime }(\tau )|}$; by Proposition 3 below $|{\psi }^{\prime \prime }(\tau )|=\tau {\varphi }^{\prime \prime }(\tau )/\varphi (\tau {)}^2$, and $2\rho /|{\psi }^{\prime \prime }(\tau )|=2(\tau /\varphi (\tau ))\varphi (\tau {)}^2/(\tau {\varphi }^{\prime \prime }(\tau ))=2\varphi (\tau )/{\varphi }^{\prime \prime }(\tau )$. $\square$

Proposition 3 (${\psi }^{\prime \prime }$ at the characteristic value). ${\psi }^{\prime \prime }(\tau )=-\tau {\varphi }^{\prime \prime }(\tau )/\varphi (\tau {)}^2$, so $|{\psi }^{\prime \prime }(\tau )|=\tau {\varphi }^{\prime \prime }(\tau )/\varphi (\tau {)}^2$.

Proof. From ${\psi }^{\prime }=(\varphi -y{\varphi }^{\prime }){\varphi }^{-2}$, differentiate: ${\psi }^{\prime \prime }=({\varphi }^{\prime }-{\varphi }^{\prime }-y{\varphi }^{\prime \prime }){\varphi }^{-2}+(\varphi -y{\varphi }^{\prime })(-2){\varphi }^{-3}{\varphi }^{\prime }=-y{\varphi }^{\prime \prime }{\varphi }^{-2}-2{\varphi }^{\prime }(\varphi -y{\varphi }^{\prime }){\varphi }^{-3}$. At $\tau$, $\varphi (\tau )-\tau {\varphi }^{\prime }(\tau )=0$ annihilates the second term, leaving ${\psi }^{\prime \prime }(\tau )=-\tau {\varphi }^{\prime \prime }(\tau )/\varphi (\tau {)}^2$. Since ${\varphi }^{\prime \prime }(\tau )>0$ for a branching family, ${\psi }^{\prime \prime }(\tau )<0$ and its magnitude is as stated. $\square$

Proposition 4 (coefficient asymptotic via transfer). With $y(z)=\tau -c\sqrt{1-z/\rho }+O(1-z/\rho )$, $c=\sqrt{2\varphi (\tau )/{\varphi }^{\prime \prime }(\tau )}$, analytic in a $\Delta$-domain at $\rho$, $[z^n]y\sim \frac{c}{2\sqrt{\pi }}{\rho }^{-n}{n}^{-3/2}$.

Proof. The singularity-analysis transfer theorem (companion unit) states that a function analytic in a $\Delta$-domain at $\rho$ with $g(z)\sim (1-z/\rho {)}^{\alpha }$, $\alpha \notin {\mathbb{Z}}_{\ge 0}$, has $[z^n]g\sim \frac{{\rho }^{-n}{n}^{-\alpha -1}}{\Gamma (-\alpha )}$. Apply with $g=\sqrt{1-z/\rho }$, $\alpha =\frac{1}{2}$: $\Gamma (-\frac{1}{2})=-2\sqrt{\pi }$ and $n^{-\alpha -1}=n^{-3/2}$ give $[z^n]\sqrt{1-z/\rho }\sim -\frac{1}{2\sqrt{\pi }}{\rho }^{-n}{n}^{-3/2}$. The constant term $\tau$ contributes only to $[z^0]$, and the $O(1-z/\rho )$ remainder has $\alpha =1\in \mathbb{Z}$, contributing $O({\rho }^{-n}{n}^{-2})$, subleading. Linearity gives $[z^n]y\sim -c\cdot (-\frac{1}{2\sqrt{\pi }}){\rho }^{-n}{n}^{-3/2}=\frac{c}{2\sqrt{\pi }}{\rho }^{-n}{n}^{-3/2}$. The $\Delta$-domain analyticity required by the transfer holds because $y$, the inverse of $\psi$ analytic with an isolated ${\psi }^{\prime }=0$ at $\tau$, continues analytically to a slit neighbourhood of $\rho$ (the only obstruction is the branch point at $\rho$ itself), and aperiodicity rules out other singularities of modulus $\rho$. $\square$

Proposition 5 (height first moment, sketch within the schema). For the simple variety with $y=z\varphi (y)$ and offspring variance ${\sigma }^2={\tau }^2{\varphi }^{\prime \prime }(\tau )/\varphi (\tau )$, $\mathbb{E}[H_n]\sim {\sigma }^{-1}\sqrt{\pi n}$.

Proof sketch. The bivariate generating function $y^{[h]}(z)$ of trees of height $\le h$ satisfies the truncated recursion $y^{[h]}=z\varphi (y^{[h-1]})$, $y^{[0]}=0$, a sequence of approximants converging to $y$ from below. The tail probability $\mathbb{P}(H_n>h)=1-[z^n]y^{[h]}/[z^n]y$ is controlled by the difference $y-y^{[h]}$, whose dominant singularity analysis near $\rho$ shows $[z^n](y-y^{[h]})/[z^n]y\to \Theta (h/\sqrt{n})$-profile. Summing the tail, $\mathbb{E}[H_n]={\sum }_{h\ge 0}\mathbb{P}(H_n>h)\sim {\int }_0^{\infty }\mathbb{P}(\sigma H_n/\sqrt{n}>x)dx\cdot \sqrt{n}/\sigma$, and the limit integrand is the tail of $\max \mathbf{e}$, whose mean is $\sqrt{\pi /2}$; combined with the excursion normalisation this yields $\mathbb{E}[H_n]\sim {\sigma }^{-1}\sqrt{\pi n}$. The rigorous limit law $\sigma H_n/\sqrt{n}\stackrel{d}{\to }\max \mathbf{e}$ is the theta/Airy distribution of Theorem 2 ^{[Meir-Moon 1978, Flajolet-Sedgewick Ch. VII.10]}. $\square$

Connections Master

• This unit is the asymptotic completion of the exact tree enumeration of 40.01.07: there the tree function $T=z{e}^T$ and the general fixed-point $y=z\varphi (y)$ were solved by Lagrange-Bürmann inversion to give $[z^n]y=\frac{1}{n}[{\lambda }^{n-1}]\varphi (\lambda {)}^n$, and here the same equation is read analytically — the inverse $\psi (y)=y/\varphi (y)$ has ${\psi }^{\prime }(\tau )=0$, producing the square-root singularity that turns the exact coefficient into the $n^{-3/2}{\rho }^{-n}$ law. The Catalan and Cayley instances computed there ($C_n$, $n^{n-1}/n!$) reappear here as the $\rho =\frac{1}{4}$, $c=\frac{1}{2}$ and the $\rho =\frac{1}{e}$, $c=\sqrt{2}$ specialisations.

• The transfer engine is supplied by the companion singularity-analysis unit 40.08.04, co-produced this wave: it proves the Hankel-contour theorem $[z^n](1-z/\rho {)}^{\alpha }\sim {\rho }^{-n}{n}^{-\alpha -1}/\Gamma (-\alpha )$ and the $\Delta$-domain transfer that this unit invokes at $\alpha =\frac{1}{2}$. Where 40.08.04 owns the general algebraic-logarithmic transfer machinery, this unit is its flagship application: the inverse-function schema is the canonical source of the square-root singularity $\alpha =\frac{1}{2}$, and the universal $n^{-3/2}$ tree law is the headline consequence of 40.08.04's transfer.

• The unit sits in the analytic-combinatorics pipeline alongside the meromorphic theory of 40.08.03: there the dominant singularity is a pole and the subexponential factor is the integer power $n^{m-1}$; here it is an algebraic branch point and the factor is $n^{-3/2}$. The two are the two halves of the second principle (singularity type fixes the subexponential factor), and the remaining case — entire generating functions with no finite singularity, where growth is read from a saddle point — is handled by 40.08.06, so the three units partition the asymptotic regimes of combinatorial generating functions.

• The square-root universality generalises beyond single trees to positive algebraic systems via the Drmota-Lalley-Woods theorem of the Advanced results, connecting forward to context-free specifications and to map enumeration: planar maps, dissections, and pattern-avoiding lattice-path families all satisfy strongly connected positive systems and inherit the $n^{-3/2}$ (or, at non-smooth critical points, other algebraic) exponents. The Brownian-excursion / continuum-random-tree limit links this unit to probability theory, where Aldous's CRT is the scaling limit common to every simple variety, and the offspring-variance constant ${\sigma }^2={\tau }^2{\varphi }^{\prime \prime }(\tau )/\varphi (\tau )$ ties the analytic amplitude to the probabilistic Galton-Watson conditioning.

Historical & philosophical context Master

The recognition that diverse tree families share one asymptotic shape emerged from George Pólya's 1937 enumeration of chemical isomers and rooted trees, which produced the functional equations and the first asymptotic estimates, and from the singularity-based coefficient asymptotics that Edward Bender (1974), Asymptotic methods in enumeration (SIAM Review 16, 485–515), systematised for implicitly defined generating functions. The explicit "simple families of trees" framework and the $\sqrt{\pi n}$ height law are due to Amram Meir and John Moon (1978) ^{[Meir-Moon 1978]}, who computed node-altitude moments through the inverse-function singularity and named the class.

The square-root singularity of the inverse function and the universal $n^{-3/2}$ coefficient law were placed inside the singularity-analysis transfer framework by Philippe Flajolet and Andrew Odlyzko (1990), Singularity analysis of generating functions (SIAM J. Discrete Math. 3, 216–240), and organised as the smooth implicit-function schema in Flajolet and Sedgewick's Analytic Combinatorics (2009) ^{[Flajolet-Sedgewick Ch. VII]}, whose Chapter VII makes the inverse-function singularity, the height/profile Airy laws, and the Drmota-Lalley-Woods systems theorem a single development. The probabilistic counterpart — that a Galton-Watson tree conditioned on size converges after $\sqrt{n}$ scaling to the continuum random tree — is David Aldous's (1991–1993) CRT, and the systems universality is the Drmota (1997), Lalley (1993), Woods (1997) theorem, consolidated in Michael Drmota's Random Trees (2009) ^{[Drmota 2009]}. The Brownian-excursion height law traces to Daniel Renyi and George Szekeres (1967) for plane trees and Flajolet-Odlyzko (1982) for the general height distribution.

Bibliography Master

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

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

@article{meirmoon1978altitude,
  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{flajoletodlyzko1990singularity,
  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}
}

@article{bender1974asymptotic,
  author  = {Bender, Edward A.},
  title   = {Asymptotic methods in enumeration},
  journal = {SIAM Review},
  volume  = {16},
  number  = {4},
  year    = {1974},
  pages   = {485--515}
}

@article{aldous1991crt,
  author  = {Aldous, David},
  title   = {The continuum random tree. I},
  journal = {The Annals of Probability},
  volume  = {19},
  number  = {1},
  year    = {1991},
  pages   = {1--28}
}

@article{drmota1997systems,
  author  = {Drmota, Michael},
  title   = {Systems of functional equations},
  journal = {Random Structures \& Algorithms},
  volume  = {10},
  number  = {1-2},
  year    = {1997},
  pages   = {103--124}
}