A365509 Number of n-vertex binary trees that do not contain 0(0[0(0(00))]) as a subtree.

1, 2, 5, 14, 41, 124, 383, 1202, 3819, 12255, 39651, 129190, 423469, 1395425

Offset: 1

Author

Torsten Muetze, Sep 07 2023

Keywords

• nonn
• more

Comments

By 'binary tree' we mean a rooted, ordered tree which is either empty, denoted by 0, or it has both a left subtree L and a right subtree R (which can be empty), and then it is denoted by (LR) if it is attached by a contiguous edge to its parent, [LR] if attached by a non-contiguous edge, or LR if it is does not have a parent, i.e., if is the root. A contiguous edge in the pattern tree corresponds to a parent-child relation in the host tree (as in Rowland's paper), whereas a non-contiguous edge in the pattern tree corresponds to an ancestor-descendant relation in the host tree (as in the paper by Dairyko, Pudwell, Tyner, and Wynn).

Number of n-vertex binary trees that do not contain 0(0[((00)0)0]) as a subtree.

Links

• CombOS - Combinatorial Object Server, Generate binary trees
• Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, arXiv:1203.0795 [math.CO], 2012.
• Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.
• Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
• Petr Gregor, Torsten Mütze, and Namrata, Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See pp. 33.12, 33.13.
• Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2010.
• Eric S. Rowland, Pattern avoidance in binary trees, J. Comb. Theory A 117 (6) (2010) 741-758.

Crossrefs

Cf. A007051 for pattern 0[0[0[0[00]]]], i.e., same tree shape, but all edges non-contiguous.

Cf. A036766 for pattern 0(0(0(0(00)))), i.e., same tree shape, but all edges contiguous.

Cf. A365508, A365510.