For $r \ge 2$ let $\mathcal{C}_r$ denote the class of Cayley trees in which every vertex has at most $r$ children. We denote the EGF of $\mathcal{C}_r$ by $C_r(z)$. Show that the Singular Inversion Theorem (see below) is applicable to $C_r(z)$ and use it to determine an asymptotic formula for $[z^n]C_r(z)$ in the case $r = 2$.
When I use the symbolic method, analogously to the case of general Cayley trees, to determine $C_r(z)$ I get: $\mathcal{Z} \times \text{SET}_{\le r}(\mathcal{Z})$, and thus:
$$C_r(z) = z \sum_{k=1}^r \frac{1}{k!} z^k = \sum_{k=1}^r \frac{1}{k!} z^{k+1}.$$
However, I already get stuck here as the $C_r(z)$ I computed does not fulfill the condition $C_r(0) \ne 0$.
Could you please tell me what I am doing wrong?
Singular Inversion Theorem: Let $\phi(u)$ be analytic at $0$ and its series expansion $\phi(u) = \sum_{k} \phi_k u^k$ at $0$ satisfy the following conditions:
- $\phi(0) \ne 0$
- $[u^k]\phi(u) \ge 0 \quad (\forall k \ge 0)$
- $[u^k]\phi(u) > 0 \text{ for some } k \ge 0$, i.e $\phi(u)$ is non-linear
- The radius of convergence of $\sum_k \phi_k u^k$ is $R \in (0, \infty]$.
If there exists a unique solution $u_0 \in (0,R)$ of the equation $$\phi(u) - u\phi^\prime(u) = 0, $$ then the solution $u(z)$ of the equation $u(z) = z\phi(u(z))$ satisfies the following:
- $u(z)$ is analytic at $0$
- The dominant singularity of $u(z)$ is given by $\rho := \frac{u_0}{\phi(u_0)}$.
- The singular expansion of $u(z)$ for $z \rightarrow \rho$ is of the form $$u(z) = u_0 - \sqrt{ \frac{2 \phi(u_0)}{ \phi^{\prime\prime}(u_0) }} \biggl( 1- \frac{z}{\rho} \biggr)^{1/2} + \sum_{j \ge 2} C_j \biggl(1 + \frac{z}{\rho} \biggr)^{j/2}$$
- If additionally $\phi$ is aperiodic, then $$ [z^n]u(z) = \sqrt{ \frac{1}{2\pi} \frac{ \phi(u_0)}{ \phi^{\prime\prime} }} n^{-3/2} \rho^{-n} \cdot \bigg(1 + \mathcal{O}\bigg(\frac{1}{n}\bigg)\bigg).$$ Remark: Apparently this is a variant of the Singular Inversion Theorem described in Flajolet & Sedgewick p.404)