- Let $a(n)$ be A036765 i.e. number of ordered rooted trees with $n$ non-root nodes and all outdegrees $\leqslant 3$. Here $$ a(n) = \frac{1}{n+1}\sum\limits_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n+1}{n-2j}\binom{n+1}{j} $$ Also ordinary generating function $A(x)$ satisfies $$ A(x)=1+xA(x)+(xA(x))^2+(xA(x))^3 $$
- Let $$ R(n, q) = -R(n-1, q+1) + R(n-1, q+2) + \sum\limits_{j=0}^{q} (-1)^j R(n-1, j), \\ R(0, q) = 1. $$
I conjecture that $$R(n,0) = a(n).$$
Here is the PARI/GP program to check it numerically:
a(n) = sum(j=0, n\2, binomial(n+1, n-2*j) * binomial(n+1, j)) / (n+1)
R_upto(n) = my(v1, v2, v3); v1 = vector(2*n + 1, i, 1); v2 = v1; v3 = vector(n + 1, i, 0); v3[1] = 1; for(i = 1, n, for(q = 0, 2*(n - i), v2[q + 1] = - v1[q + 2] + v1[q + 3] + sum(j = 0, q, (-1) ^ j * v1[j + 1])); v1 = v2; v3[i + 1] = v1[1]); v3
test(n) = R_upto(n) == vector(n+1, i, a(i-1))
Is there a way to prove it?
