E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), Journal of Integer Sequences, Vol. 2 (1999) is only available in HTML, which makes it harder to read than a nice LaTeXified PDF but easy to quote the section which is confusing me:
Fix k, and let Th,n be the number of (k-1)-ary rooted trees with n nodes and height at most h. (The height of a node in a rooted tree is the number of edges joining the node to the root.) By convention the empty tree has height -1. Let Th(z) = SUM n >= 0 Th,n zn. Then T-1 (z ) = 1, T0 (z) = 1+ z, and for h>1,
Th+1 (z) = 1+ z Sk-1 (Th (z )), (4)
where Sm (f(z)) denotes the result of substituting f(z) into the cycle index for the symmetric group of order m!. For example,
S3 (f(z)) = ( f(z)3 +3 f(z) f(z2) + 2 f(z3)) / 3!.
Equation (4) holds because if we remove the root and adjacent edges from a rooted tree of height h+1 we are left with an unordered (k-1)-tuple of trees of height h.
Let C2h,n be the number of centered k-valent trees with n nodes and diameter 2h, and let C2h(z) = SUM n >= 0 C2h,n zn. By deleting the center node and adjacent edges, we see that any such tree corresponds to an unordered k-tuple of (k-1)-ary rooted trees of height at most h-1, at least two of which have height exactly h-1. Therefore
C2h = ( 1+ z Sk (Th-1 (z))) - (1+ z Sk (Th-2 (z))) - (Th-1 (z)-Th-2 (z))(Th-1 (z) - 1 ). (5)The three expressions in (5) account for the k-tuples of rooted trees of height at most h-1, k-tuples of rooted trees of height at most h-2, and rooted trees with exactly one subtree at the root with height h-1, respectively.
Finally, let Cn denote the number of centered k-valent trees with n nodes, and C(z) = SUM n >= 0 Cnzn. Then
C(z) = SUM h >= 0 C2h(z) .For k = 4 we obtain
C(z) = z + z3 + z4 + 2 z5 + 2 z6 + 6 z7 + 9 z8 + 20 z9 + 37 z10 + 86 z11 + 181 z12 + 422 z13 + ... ,which is the corrected version of Cayley's sequence (1), A000022.
However, it seems to me that in the sum $C_(z) = \sum_{h \ge 0} C_{2h}(z)$ the first two terms of $C_{2h}$ telescope, and likewise half of the third term, to give
$$C(z) = - (1+ z S_k (T_{-2} (z))) - T_{-2} (z) + \sum_{h \ge 0} (T_{h-2} (z)-T_{h-1} (z))T_{h-1} (z)$$
I presume, although it's not explicitly stated, that $T_{-2}(z) = 0$, so that simplifies to
$$C(z) = - 1 + \sum_{h \ge 0} (T_{h-2} (z)-T_{h-1} (z))T_{h-1} (z)$$
Now, the coefficients of $T_h$ are $T_{h,n}$ which must be non-negative, and since $T_{h,n}$ is defined as "the number of ($k$-1)-ary rooted trees with $n$ nodes and height at most $h$" (my emphasis) it is clear that $T_{h-1,n} \ge T_{h-2,n}$. Therefore the sum in the simplified expression for $C(z)$ is convolving a polynomial whose coefficients are all non-positive with a polynomial whose coefficients are all non-negative, and the result must be a polynomial whose coefficients are all non-positive.
But all of the coefficients of $C(z)$ should be non-negative, and Rains and Sloane explicitly give its initial coefficients as non-negative numbers.
Have I misunderstood something? Is there a sign error in the paper? Or is it a more serious flaw?
For what it's worth, I suspect that the third term of $C_{2h}$, which accounts for rooted trees with exactly one subtree at the root of height $h-1$, is missing an application of $S_k$, and should be $(T_{h-1} (z)-T_{h-2} (z))S_k(T_{h-1} (z) - 1)$, but I admit that I'm slightly out of my depth.
I've worked through some small terms with a CAS.
Firstly, I made an error in telescoping the first two terms, so that $-1$ shouldn't be there: this is clear when considering a finite telescope, as $$\sum_{h=0}^{n} (1 + z S_k(T_{h-1}(z))) - (1 + z S_k(T_{h-2}(z))) = z S_k(T_{n-1}(z)) - z S_k(T_{-2}(z))$$
Secondly, the telescoping doesn't carry over trivially from finite to infinite terms. That is, $$\sum_{h=0}^n C_{2h}(z) = z S_k(T_{n-1}(z)) + T_{n-1}(z) - \sum_{h=0}^n (T_{h-1}(z) - T_{h-2}(z)) T_{h-1}(z)$$
but the terms which telescoping has pulled out of the sum have larger (absolute, non-negative) coefficients than the (non-positive) coefficients of the convolution.