A006629 -id:A006629 - cp's OEIS frontend

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

Murray R. Bremner, May 21 2017

"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.

			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]].

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

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

Maple
```
See attached a-file under Links.
```

A073148 Triangle of numbers {a(n,k), n >= 0, 0<=k<=n} defined by a(0,0)=1, a(n,0)=A006013(n), a(n+1,n)=A001764(n+1), a(n,m) = Sum A001764(n-k)*a(n,k), k=0..m.

Original entry on oeis.org

1, 2, 3, 7, 9, 12, 30, 37, 43, 55, 143, 173, 194, 218, 273, 728, 871, 961, 1045, 1155, 1428, 3876, 4604, 5033, 5393, 5778, 6324, 7752, 21318, 25194, 27378, 29094, 30744, 32655, 35511, 43263, 120175

Offset: 0

Paul D. Hanna, Jul 18 2002

Compare to A073147. Related to generalized Catalan numbers; in particular, C(3n,n)/(2n+1) (enumerates ternary trees and also non-crossing trees)(A001764).

These numbers are cardinalities of some intervals in the Tamari lattices. - F. Chapoton, Jul 15 2021

			{1}, {2,3}, {7,9,12}, {30,37,43,55}, {143,173,194,218,273},{728,871,961,1045,1155,1428}, {3876,4604,5033,5393,5778,6324,7752}, ...

Cf. A073147, A001764, A006013, A006629, A028364.

a(n, m) = Sum A001764(n-k)*a(n, k), k=0..m.

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple