cp's OEIS Frontend

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

%I A335729 #39 Sep 04 2020 15:41:22
%S A335729 1,2,10,68,546,4872,46782,474180,5010456,54721224,613912182,
%T A335729 7042779996,82329308040,978034001472
%N A335729 Number of "coprime" pairs of binary trees with n carets (see comments).
%C A335729 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".
%C A335729 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".
%H A335729 S. Cleary and R. Maio, <a href="https://arxiv.org/abs/2001.06407">Counting difficult tree pairs with respect to the rotation distance problem</a>, arXiv:2001.06407 [cs.DS], 2020.
%e A335729 A coprime tree-pair with 5 carets:
%e A335729        .              .
%e A335729       / \            / \
%e A335729      / \ \          /   \
%e A335729     / / \ \        / \   \
%e A335729    / / \ \ \      / \ \   \
%e A335729   / / \ \ \ \    / \ \ \ / \
%e A335729   1 2 3 4 5 6    1 2 3 4 5 6
%e A335729 A non-coprime tree-pair (both have a subtree on leaves 1-2-3-4):
%e A335729        .              .
%e A335729       / \            / \
%e A335729      / \ \          /   \
%e A335729     / \ \ \        / \   \
%e A335729    /   \ \ \      / / \   \
%e A335729   / \ / \ \ \    / / \ \ / \
%e A335729   1 2 3 4 5 6    1 2 3 4 5 6
%e A335729 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.
%e A335729 For n = 2, the a(2) = 2 coprime tree-pairs are:
%e A335729   ([[12]3], [1[23]]),
%e A335729   ([1[23]], [[12]3]).
%e A335729 For n = 3, the a(3) = 10 coprime tree-pairs are:
%e A335729   ([1[2[34]]], [[1[23]]4]),
%e A335729   ([1[2[34]]], [[[12]3]4]),
%e A335729   ([1[[23]4]], [[12][34]]),
%e A335729   ([1[[23]4]], [[[12]3]4]),
%e A335729   ([[12][34]], [1[[23]4]]),
%e A335729   ([[12][34]], [[1[23]]4]),
%e A335729   ([[1[23]]4], [1[2[34]]]),
%e A335729   ([[1[23]]4], [[12][34]]),
%e A335729   ([[[12]3]4], [1[2[34]]]),
%e A335729   ([[[12]3]4], [1[[23]4]]).
%Y A335729 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.
%K A335729 nonn,more
%O A335729 1,2
%A A335729 _Dennis Sweeney_, Jul 17 2020