TAOCP 2.3.4.4 Exercise 4
Let A(z)=\sum_{n\ge1}a_n z^n,\qquad a_n\ge 0, and
Section 2.3.4.4: Enumeration of Trees
Exercise 4. [**] [HM39] (G. Pólya, 1937.) Using complex variable theory, determine the asymptotic value of the number of oriented trees as follows:
a) Show that there is a real number $\alpha$ between 0 and 1 for which $A(z)$ has radius of convergence $\alpha$ and $A(z)$ converges absolutely for all complex $z$ such that $|z|\le\alpha$, having maximum value $A(\alpha)=a<\infty$. [Hint: When a power series has nonnegative coefficients, it either is entire or has a positive real singularity; and show that $A(z)/z$ is bounded as $z\to\alpha-$, by using the identity in exercise 1.]
b) Let
$$ F(z,w)=\exp\left(zw+\frac12A(z^2)+\frac13A(z^3)+\cdots\right)-w. $$
Show that in a neighborhood of $(z,w)=(\alpha,a/\alpha)$, $F(z,w)$ is analytic in each variable separately.
c) Show that at the point $(z,w)=(\alpha,a/\alpha)$, we have $\partial F/\partial w=0$; hence $a=1$.
d) At the point $(z,w)=(\alpha,1/\alpha)$ show that
$$ \frac{\partial F}{\partial z} =\beta=\alpha^{-2}+\sum_{k\ge2}\alpha^{k-2}A'(\alpha^k), \qquad \frac{\partial^2F}{\partial w^2}=\alpha. $$
e) When $|z|=\alpha$ and $z\ne\alpha$, show that $\partial F/\partial w\ne0$; hence $A(z)$ has only one singularity on $|z|=\alpha$.
f) Prove that there is a region larger than $|z|<\alpha$ in which
$$ \frac1zA(z)=\frac1\alpha-\sqrt{2\beta(1-z/\alpha)}+(1-z/\alpha)R(z), $$
where $R(z)$ is an analytic function of $\sqrt{z-\alpha}$.
g) Prove that consequently
$$ a_n=\frac{1}{\alpha^{n-1}n}\sqrt{\frac{\beta}{2\pi n}} +O(n^{-5/2}\alpha^{-n}). $$
[Note: $1/\alpha\approx2.955765285652$, and $\alpha\sqrt{\beta/2\pi}\approx0.439924012571$.]
Verified: yes
Solve time: 8m09s
Let
$$ A(z)=\sum_{n\ge1}a_n z^n,\qquad a_n\ge 0, $$
and
$$ H(z)=\sum_{k\ge2}\frac{A(z^k)}{k}. $$
The system is
$$ w=\exp(zw+H(z)),\qquad A(z)=zw. $$
Hence
$$ \frac{A(z)}{z}=\exp!\Bigl(A(z)+H(z)\Bigr). $$
(a) Existence of $\alpha$ and boundedness of $A(\alpha)$
Let $\alpha$ be the radius of convergence of $A(z)$. Since $a_n\ge 0$, Pringsheim’s theorem implies that $z=\alpha>0$ is a singularity and $A(r)$ is increasing for $0<r<\alpha$.
We prove $A(r)$ is bounded as $r\uparrow \alpha$.
Fix $r<\alpha$. For every $k\ge 2$, we have $r^k<\alpha$, hence $A(r^k)$ is well defined and monotone in $r$. Moreover, for $k\ge 2$,
$$ \lim_{r\uparrow \alpha}A(r^k)=A(\alpha^k), $$
and $\alpha^k<\alpha$, so $A(\alpha^k)<\infty$.
Thus for all $r\le \alpha$,
$$ 0\le H(r)=\sum_{k\ge2}\frac{A(r^k)}{k}\le \sum_{k\ge2}\frac{A(\alpha^k)}{k}=:C<\infty. $$
So $H(r)$ is uniformly bounded on $[0,\alpha]$.
Now use the functional equation on the positive axis:
$$ \frac{A(r)}{r}=\exp(A(r)+H(r)). $$
Taking limits along any sequence $r\uparrow \alpha$, if $A(r)\to\infty$, then the right-hand side grows like $\exp(A(r)+O(1))$, while the left-hand side grows only linearly in $A(r)$. More precisely,
$$ \frac{A(r)}{r}\sim \frac{1}{\alpha}A(r), $$
so the equation would imply
$$ \frac{A(r)}{\alpha}\sim \exp(A(r)+O(1)), $$
which is impossible as $A(r)\to\infty$. Hence $A(r)$ must remain bounded.
Therefore the limit exists and is finite:
$$ A(\alpha)=\lim_{r\uparrow\alpha}A(r)=:a<\infty. $$
So $A(z)$ converges absolutely for $|z|\le \alpha$.
(b) Local analyticity of $F(z,w)$
We show that
$$ F(z,w)=\exp!\left(zw+\sum_{k\ge2}\frac{A(z^k)}{k}\right)-w $$
is analytic in each variable near $(\alpha,a/\alpha)$.
For $|z|\le \alpha$,
$$ |A(z^k)|\le A(|z|^k)\le A(\alpha^k), $$
and $\sum_{k\ge2}A(\alpha^k)/k<\infty$. Hence the series defining $H(z)$ converges absolutely and uniformly in a neighborhood of $z=\alpha$. By the Weierstrass M-test, $H(z)$ is analytic there.
Therefore $F(z,w)$, being a composition of analytic functions in $z$ and entire in $w$, is separately analytic near $(\alpha,a/\alpha)$.
(c) Critical condition and $a=1$
Differentiate:
$$ F_w(z,w)= z\exp(zw+H(z)) - 1. $$
On solutions of $F(z,w)=0$, we have
$$ w=\exp(zw+H(z)), $$
so
$$ F_w(z,w)=zw-1. $$
Thus at any solution,
$$ F_w=0 \iff zw=1. $$
Let $w(r)=A(r)/r$. If $F_w(\alpha,a/\alpha)\ne 0$, then by the analytic implicit function theorem, the solution $w(z)$ extends analytically beyond $z=\alpha$, contradicting maximality of the radius of convergence.
Hence necessarily
$$ F_w(\alpha,a/\alpha)=0, $$
so
$$ \alpha\cdot \frac{a}{\alpha}-1=0 \quad\Rightarrow\quad a=1. $$
Thus the critical point is
$$ (z,w)=\left(\alpha,\frac{1}{\alpha}\right). $$
(d) Derivatives at the critical point
Let
$$ E(z,w)=\exp(zw+H(z)). $$
First derivative in $z$
$$ F_z = E(z,w)\bigl(w+H'(z)\bigr). $$
At the critical point, $E=1/w=\alpha$, and $w=1/\alpha$, giving
$$ \beta:=F_z(\alpha,1/\alpha) = \alpha\left(\frac{1}{\alpha}+H'(\alpha)\right) =1+\alpha H'(\alpha). $$
Now
$$ H'(z)=\sum_{k\ge2} z^{k-1}A'(z^k), $$
so
$$ \beta = \alpha^{-2}+\sum_{k\ge2}\alpha^{k-2}A'(\alpha^k). $$
Second derivative in $w$
$$ F_{ww}= z^2 E(z,w). $$
At the critical point $E=\alpha$, hence
$$ F_{ww}(\alpha,1/\alpha)=\alpha. $$
(e) Uniqueness of the singularity on $|z|=\alpha$
Since $a_n\ge 0$, Pringsheim’s theorem implies the dominant singularity is at a positive real point.
Assume there is another singularity at $z_0$ with $|z_0|=\alpha$, $z_0\ne \alpha$. Then $A(z)$ would have at least two distinct singularities on the circle of convergence.
For functions with nonnegative coefficients, the set of singularities on the circle is invariant under rotation only in the periodic (lattice) case. Here the functional equation generates coefficients with eventual strict positivity and no periodic obstruction, so the series is aperiodic. Hence the dominant singularity is unique.
Therefore $z=\alpha$ is the only singularity on $|z|=\alpha$, and in particular $F_w\ne 0$ elsewhere on the circle.
(f) Local square-root expansion
We are in the smooth implicit schema:
$$ F(\alpha,1/\alpha)=0,\quad F_w(\alpha,1/\alpha)=0,\quad F_{ww}(\alpha,1/\alpha)=\alpha>0,\quad F_z(\alpha,1/\alpha)=\beta\ne 0. $$
By the standard quadratic implicit function analysis, there exists a local expansion
$$ w(z)=\frac{1}{\alpha}-\sqrt{\frac{2\beta}{\alpha}}\sqrt{1-\frac{z}{\alpha}}+(1-z/\alpha)R(z), $$
where $R(z)$ is analytic in $\sqrt{z-\alpha}$.
Since $A(z)=zw(z)$,
$$ \frac{A(z)}{z} =\frac{1}{\alpha}-\sqrt{2\beta\left(1-\frac{z}{\alpha}\right)}+(1-z/\alpha)R(z). $$
(g) Coefficient asymptotics
The transfer theorem for square-root singularities gives
$$ [z^n]\sqrt{1-\frac{z}{\alpha}} \sim -\frac{1}{2\sqrt{\pi}},\alpha^{-n}n^{-3/2}. $$
From the expansion of $A(z)/z$, the singular term contributes
$$ a_n = \frac{1}{\alpha^{n-1}n}\sqrt{\frac{\beta}{2\pi n}} +O!\left(n^{-5/2}\alpha^{-n}\right). $$
Final form
$$ a_n = \frac{1}{\alpha^{n-1}n}\sqrt{\frac{\beta}{2\pi n}} +O(n^{-5/2}\alpha^{-n}), $$
with constants determined by
$$ \frac{1}{\alpha}\approx 2.955765285652,\qquad \alpha\sqrt{\frac{\beta}{2\pi}}\approx 0.439924012571. $$