login
A335729
Number of "coprime" pairs of binary trees with n carets (see comments).
1
1, 2, 10, 68, 546, 4872, 46782, 474180, 5010456, 54721224, 613912182, 7042779996, 82329308040, 978034001472
OFFSET
1,2
COMMENTS
a(n) is the number of ordered pairs of rooted binary trees (with all nodes having either 2 or 0 ordered children) each with n non-leaf nodes (sometimes called carets) such that the pair is "coprime".
Call such a tree-pair (A, B) coprime if, upon labeling the leaves 1 through n + 1 (left to right), there does not exist a non-leaf, non-root node a of A and a non-leaf, non-root node b of B such that the set of labels on the descendant leaves of a equals the set of labels on the descendant leaves of b, i.e., if A and B have no proper subtrees "in the same place".
EXAMPLE
A coprime tree-pair with 5 carets:
. .
/ \ / \
/ \ \ / \
/ / \ \ / \ \
/ / \ \ \ / \ \ \
/ / \ \ \ \ / \ \ \ / \
1 2 3 4 5 6 1 2 3 4 5 6
A non-coprime tree-pair (both have a subtree on leaves 1-2-3-4):
. .
/ \ / \
/ \ \ / \
/ \ \ \ / \ \
/ \ \ \ / / \ \
/ \ / \ \ \ / / \ \ / \
1 2 3 4 5 6 1 2 3 4 5 6
Below we will represent a binary tree by a bracketing of the leaf labels 1 through n + 1 (a vertex of an associahedron). A tree is represented by a balanced string, and its left and right child subtrees are represented by two maximal balanced proper substrings, in order.
For n = 2, the a(2) = 2 coprime tree-pairs are:
([[12]3], [1[23]]),
([1[23]], [[12]3]).
For n = 3, the a(3) = 10 coprime tree-pairs are:
([1[2[34]]], [[1[23]]4]),
([1[2[34]]], [[[12]3]4]),
([1[[23]4]], [[12][34]]),
([1[[23]4]], [[[12]3]4]),
([[12][34]], [1[[23]4]]),
([[12][34]], [[1[23]]4]),
([[1[23]]4], [1[2[34]]]),
([[1[23]]4], [[12][34]]),
([[[12]3]4], [1[2[34]]]),
([[[12]3]4], [1[[23]4]]).
CROSSREFS
a(n) counts a subset of the tree-pairs that A111713 counts; "coprime" is a stronger condition than "reduced". It appears that for n > 1, a(n)/2 coincides with A257887.
Sequence in context: A074603 A110520 A136633 * A361769 A082580 A231492
KEYWORD
nonn,more
AUTHOR
Dennis Sweeney, Jul 17 2020
STATUS
approved