Sequence of interest
I feel like I've got most of the way, I just need some help at the last step. I am considering an integer sequence which encodes information pertaining to certain weighted ordered rooted trees. I won't bore you with the details suffice to say I found a recurrence relation for the sequence and consequently a generating function. Given the arbitrary variables $(c_0, c_1, c_2, c_3)$, the recurrence relation is:
\begin{align}
a_0 &= c_0 \\
a_n &= c_1 a_{n-1} + c_2 \sum_{i=0}^{n-2}a_ia_{n-2-i} + c_3\sum_{i=0}^{n-3}\sum_{j=0}^{n-3-i}a_ia_ja_{n-3-i-j} \hspace{2em} \text{for $n \geq 1$}
\end{align}
and the generating function $A(x)$ satisfies:
$$A = c_0 + c_1 (Ax) + c_2 (Ax)^2 + c_3 (Ax)^3$$
I'd like to get an asymptotic formula for this sequence, based on the variables $(c_0,c_1,c_2,c_3)$.
Bonus points for an exact formula!
Simpler sequence
Given the case with no weightings where $c_0 = c_1 = c_2 = c_3 = 1$, we are just counting the number of ordered rooted trees with outdegree no greater than 3. I found this sequence on OEIS where it says
$$a_n = \frac{1}{n+1}\sum_{j=0}^{\left\lfloor n/2\right\rfloor} \binom{n+1}{n-2j}\binom{n+1}{j}$$
and $$a_n \sim \frac{cd^n}{n^{3/2}}$$
where
$$d = \frac{(6371+624\sqrt{78})^{2/3}+11(6371+624\sqrt{78})^{1/3}+217}{12(6371+624\sqrt{78})^{1/3}} \approx 3.610718613276\ldots$$
is the root of the equation $4d^3-11d^2-8d-16=0$ and
$$c = \sqrt{\frac{f}{\pi}} \approx 0.9102276936417\ldots$$
where
$$f = \frac{1}{9984}(9295 + (13(45085576939 – 795629568\sqrt{78}))^{1/3} + (13(45085576939 + 795629568\sqrt{78}))^{1/3})$$
is the root of the equation $3328f^3-9295f^2+1696f-128=0$.
I'm assuming these magical formulae were somehow derived from its generating function? But I'm afraid this is beyond my generatingfunctionology skills.
I didn't know if this was more suitable for math stackexchange or mathoverflow. Please feel free to redirect me.
Thanks for any help!
Best Answer
An asymptotic follows from Theorem VI.6 ("Singular Inversion") in Flajolet and Sedgewick's Analytic Combinatorics (freely legally available online at the link). The theorem concerns generating functions which solve equations of the form $Y(z) = z \phi(Y(z))$, where $\phi$ is a polynomial or more generally a power series; these count trees of various sorts. Setting $Y(z) = z A(z)$ lets us put your problem in this framework, with $\phi(u) = c_0 + c_1 u + c_2 u^2 + c_3 u^3$. We need $\phi(u)$ to satisfy three sets of conditions (equations (35) and (36) on pages 402 and 403, together with a third condition detailed on page 404):
Then the radius of convergence of $Y(z)$ is $\rho = \frac{\tau}{\phi(\tau)} = \frac{1}{\phi'(\tau)}$. For example, when $c_i = 1$ the characteristic equation is
$$(\tau^3 + \tau^2 + \tau + 1) - \tau (3 \tau^2 + 2 \tau + 1) = - 2 \tau^3 - \tau^2 + 1 = 0$$
which has a unique positive real root $\tau \approx 0.657$ (an exact value can be written down using the cubic formula) and which gives $\rho \approx 0.277$.
Again with $c_i = 1$ we have $\rho^{-1} \approx 3.61 \dots$ so this is the $d$ which appears in the result you cited from the OEIS, and the constant factor is
$$\sqrt{ \frac{\tau^3 + \tau^2 + \tau + 1}{(12 \tau + 4)\pi} } \approx 0.252$$
but since $Y(z) = z A(z)$ our indexing is off by $1$ and $y_n = a_{n-1}$. So to get $a_n = y_{n+1}$ we multiply by $\rho^{-1}$ and get a constant factor $\approx 0.910$ which matches up with the result you cited from the OEIS again. Using the cubic formula and a bunch of algebraic manipulations it would be possible to match the exact results using radicals but it doesn't sound fun.
All of these computations simplify substantially if $c_3 = 0$, since then all of the cubic equations become quadratic. In this case we can write down an explicit closed form for $Y(z)$ using the quadratic formula and analyze that closed form using the binomial theorem to get asymptotics. This case is an elaboration on that one; the asymptotics come from a square-root singularity although it's harder to tell that that's what's happening.
The first formula you give can be obtained from Lagrange inversion, which gives that if $\frac{Y(z)}{\phi(Y(z))} = z$ then $Y$ (which is the compositional inverse of $\frac{w}{\phi(w)}$) has coefficients given by
$$[z^n] Y(z) = \frac{1}{n} [w^{n-1}] \phi(w)^n.$$
When $c_i = 1$ this gives
$$\begin{eqnarray*} a_n &=& \frac{1}{n+1} [w^n] (1 + w + w^2 + w^3)^{n+1} \\ &=& \frac{1}{n+1} [w^n] (1 + w)^{n+1} (1 + w^2)^{n+1} \\ &=& \frac{1}{n+1} [w^n] \left( \sum_{i=0}^{n+1} {n+1 \choose i} w^i \right) \left( \sum_{j=0}^{n+1} {n+1 \choose j} w^{2j} \right) \\ &=& \frac{1}{n+1} \left( \sum_{i+2j = n} {n+1 \choose i} {n+1 \choose j} \right) \end{eqnarray*}$$
which is equivalent to the desired result. A nicer special case is $c_0 = c_2 = 1, c_1 = c_3 = 0$, or $\phi(w) = 1 + w^2$, which corresponds to binary trees and gives $a_{2n+1} = 0$ and
$$a_{2n} = \frac{1}{2n+1} [w^{2n}] (1 + w^2)^{2n+1} = \frac{1}{2n+1} {2n+1 \choose n} = \frac{1}{n+1} {2n \choose n}$$
which is the Catalan numbers. These have a similar asymptotic expansion because their generating function also has a square-root singularity, but the base of the exponent is $4$. It would be good to understand this case as a warmup exercise if you haven't already done so.