A335729 Number of "coprime" pairs of binary trees with n carets (see comments).

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

Links

Table of n, a(n) for n=1..14.

S. Cleary and R. Maio, Counting difficult tree pairs with respect to the rotation distance problem, arXiv:2001.06407 [cs.DS], 2020.

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

Adjacent sequences: A335726 A335727 A335728 * A335730 A335731 A335732

Keyword

nonn,more

Author

Dennis Sweeney, Jul 17 2020

Status

approved