Asymptotic growth rate of coefficients of generating function

Question

how to calculate the asymptotic growth rate of coefficients generating function $T(z)$ satisfied this identity

$T(z)=z+\frac{T(z)^3}{6}+\frac{T(z^2)T(z)}{2}+\frac{T(z^3)}{3}$

Answer 1

In order to analyze these type of equations one can use the methodology of Flajolet and Sedgewick (Analytic Combinatorics Book). More precisely, from the previous specification one gets that the first coefficients of $T(z)$ are

$$T(z)=z+z^3+z^5+2z^7+4z^9+8z^{11}+17z^{13}+39z^{15}+89z^{17}+211z^{19}$$

Observe now that if $T(z)$ has a finite singularity at $z=\rho<1$ (it cannot be $>1$ as this comes from a combinatorial problem: the sequence of numbers in the expansion is increasing), then both $T(z^2)$ and $T(z^3)$ are analytic functions at $z=\rho$, and hence we can approximate them by its Taylor expansion (which can be deduced from the previous expansion).

Hence, making this approximation gives an equation of the form $T(z)=F(z,T(z))$, where $F$ has positive Taylor coefficients. Under this circumstances, the singular expansion of $T(z)$ around its singularity will be of square-root type, and the position of the singularity will be at the solution of the system of equations

$$u=F(z,u),\, 1=F_u(z,u),$$

If you compute the solution you get $\rho=0.59597132592884902260$. Then $T(z)$ has a square-root type expansion around this value. You can get then the singular expansion (see Flajolet and Sedgewick), and apply the transference theorem to get that the coefficients grow like $ C n^{-3/2} \rho^{-n}$, with $\rho^{-1}$ roughly $1.6779330757926205637$. To compute the constant $C$ you need the singular expansion + application of the Transference Theorem.

Answer 2

Some remarks about bounding the coefficients of $T(z)$ from above and from below. I assume $T_0=0$ in $T(z)=\sum_{k=0}^\infty T_k z^k$, to which it corresponds a unique formal series solution of the functional equation for $T(z)$, e.g. obtained by iteration of the composition operator on the RHS. Let's first prove that even order coefficients vanish, and odd order coefficients increase.

The Ansatz $T(z):=zS(z^2)$ produces this equation for $S(z):=\sum_{k=0}^\infty S_k z^k$:

$$S(z)=1+\frac{1}{6}zS(z)^3 +\frac{1}{2}zS(z^2)S(z)+ \frac{1}{3}zS(z^3)\ .$$

The latter equation also have a unique formal series solution, which proves that $T$ has indeed the above form $zS(z^2)$, that is, all even order coefficients of $T$ vanish. Since $S$ can be obtained by iteration of the composition operator on the RHS, starting e.g. by $1$, it is clear that $S_k\ge0$ for all $k$, and since $S_0=1$ we also have $[z]^k S(z)^3\ge 3 [z^k]S(z)$ and $ [z^k]S(z^2) S(z)\ge [z^k]S(z)$. Thus $$S(z)\ge 1 + z S(z) \ ,$$
(coefficient-wise), proving that $S$ has increasing coefficients. Having $S(z)$ positive, increasing coefficients also implies, again from the equation, $$6S(z)\le 6 + z S(z)^3 + 3zS(z)^2+2zS(z) \ ,$$ (coefficient-wise). This implies that $S$ is dominated coefficient-wise by the power series solution $y(z)$ of $6y=6+z(y^3+3y^2+y)$. By uniqueness, $y$ is the expansion at $z=0$ of the local inverse of $$h(y)=\frac{6(y-1)}{y(y+1)(y+2)}$$ at $y=1$. This proves that $S$ has a positive radius of convergence $\rho$.

A bound from above for the coefficients of $S$ can be deduced from $$6S(z)\ge 6 + z S(z)^3 + 3zS(z) +2z \ ,$$ (coefficient-wise), which implies that the coefficients of $S(z)$ are larger than the coefficients of the local inverse at $y=1$ of $$g(y)=\frac{6(y-1)}{y^3+3y+2}\ .$$ Putting $y=x+1$, by the Lagrange inversion applied to $h(x+1)$ and $g(x+1)$ one gets, for $k\ge1$

$$\frac{1}{k}[x^{k-1}](1+x+ x^2/2 +x^3/6)^k \le S_k \le \frac{1}{k}[x^{k-1}](1+ 11x/6 +x^2 + x^3/6)^k$$

etc.