OFFSET
0,2
COMMENTS
More precisely, for nodes labeled 2, the first child must be greater than or equal to the third child in lex order. Lex order on trees is defined as follows: (1) A tree with fewer internal nodes precedes a tree with more internal nodes. (2) Suppose S and T are trees with the same number of internal nodes. Let d(S) and d(T) be the words from the alphabet {1,2,X} (X = leaf) obtained by depth-first traversal. Then S precedes T if and only if d(S) precedes d(T) in lex order with 1 < 2 < X.
The sequence may also be interpreted as the number of normal forms for association types of nonassociative monomials in two ternary operations: the first operation has no symmetry, but the second operation has reversal symmetry: (a,b,c) = (c,b,a), so we may assume that a >= c in lex order of association types. The index starts at 0 and counts the number of operations in each term (called the weight). Hence the first entry in the sequence (with index 0) is 1, corresponding to a single argument (indeterminate) X with no operations (and weight 0).
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
FORMULA
G.f.: A(x) satisfies A(x) = 1 + x*A(x)*(3*A(x)^2 + A(x^2))/2. - Andrew Howroyd, Dec 02 2025
EXAMPLE
For index 2, the 10 nonassociative ternary monomials are
[X, X, [X, X, X, 1], 1],
[X, X, [X, X, X, 2], 1],
[X, [X, X, X, 1], X, 1],
[X, [X, X, X, 2], X, 1],
[[X, X, X, 1], X, X, 1],
[[X, X, X, 2], X, X, 1],
[X, [X, X, X, 1], X, 2],
[X, [X, X, X, 2], X, 2],
[[X, X, X, 1], X, X, 2],
[[X, X, X, 2], X, X, 2],
where X is a generic argument symbol, and the last entry in each sublist indicates either operation 1 with no symmetry or operation 2 with reversal symmetry.
MAPLE
maxweight := 25:
# procedure to compute compositions of w into 3 parts allowing 0 as a part
comp3 := proc( w )
return [ seq( [ c[1]-1, c[2]-1, c[3]-1 ], c in combinat[composition]( w+3, 3 ) ) ]
end:
TT := table():
TT[0] := 1:
for w to maxweight do
TT[w] := 0:
# operation 1: without symmetry
for c in comp3( w-1 ) do TT[w] := TT[w] + TT[c[1]]*TT[c[2]]*TT[c[3]] od:
# operation 2: with reversal symmetry
for c in comp3( w-1 ) do
if c[1] > c[3] then TT[w] := TT[w] + TT[c[1]]*TT[c[2]]*TT[c[3]] fi:
if c[1] = c[3] then TT[w] := TT[w] + binomial(TT[c[1]]+1, 2)*TT[c[2]] fi
od
od:
seq(TT[n], n=0..maxweight);
PROG
(PARI) seq(n)={my(p=1+O(x)); for(n=1, n, p = 1 + x*p*(3*p^2 + subst(p, x, x^2))/2); Vec(p)} \\ Andrew Howroyd, Dec 02 2025
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Murray R. Bremner, Dec 02 2025
STATUS
approved