A287211 The number of plane rooted complete ternary trees with 2n+1 unlabeled leaves (hence n internal nodes including the root where n starts at 0) satisfying these two conditions: (1) if one of the three children of any internal node is the greatest in deglex order then that child is not the leftmost child; (2) if one of the three children of any internal node is the smallest in deglex order then that child is not the rightmost child. Deglex order refers to degree-lexicographical order defined inductively on the number of leaves (see details under Comments).

1, 1, 2, 6, 21, 78, 308, 1264, 5332, 22994, 100896, 449004

Offset: 0

Author

Murray R. Bremner, May 21 2017

Keywords

• nonn
• more

Comments

"Plane" means "embedded in the plane" or (equivalently) the three children of each internal node (including the root) are ordered left, middle, right. Deglex order on trees with 2n+1 leaves is defined as follows: to compare two such trees T and U with children T_1, T_2, T_3 and U_1, U_2, U_3, first find the least index 1 <= i <= 3 for T_i <> U_i, then compare T_i and U_i in deglex order already defined inductively on trees with fewer than 2n+1 leaves; note that this requires comparing trees with different numbers of leaves, so we say that T_i precedes U_i if either (i) T_i has fewer leaves than U_i, or (ii) T_i and U_i have the same number of leaves, and T_i precedes U_i in deglex order.

An alternative description of this sequence: it counts the distinct association types in arity 2n+1 for a ternary operation [a,b,c] satisfying the cyclic-sum relation [a,b,c] + [b,c,a] + [c,a,b] = 0. The two conditions stated under "Name" are necessary to deal with the possibility of repeated factors: [a,a,b], [a,b,a], [b,a,a] where a < b in deglex order, and [a,b,b], [b,a,b], [b,b,a] where a < b in deglex order.

See further details in the comments to the Maple program which is attached as a a-file.

Examples

			Association types for arities 1, 3, 5, 7 are as follows in deglex order. See Links for a-file with association types for arities up to 11.
Arity 1, number of types 1:
a.
Arity 3, number of types 1:
[abc].
Arity 5, number of types 2:
[ab[cde]],
[a[bcd]e].
Arity 7, number of types 6:
[ab[cd[efg]]],
[ab[c[def]g]],
[a[bcd][efg]],
[a[bc[def]]g],
[a[b[cde]f]g],
[[abc]d[efg]].
		

Links

• Murray R. Bremner, Association types up to and including arity 11
• Murray R. Bremner, Maple worksheet for generating association types

Crossrefs

Cf. A357538, A000598, A000625, A001764, A006629, A036370, A036437, A233389.

Programs

Maple

See attached a-file under Links.