0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .