A159768 -id:A159768 - cp's OEIS frontend

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

1, 2, 5, 14, 41, 123, 376, 1168, 3678, 11716, 37688, 122261, 399533, 1314023

Offset: 1

Torsten Muetze, Sep 07 2023

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 P as a subtree, where P is one of 0((00)[(00)0]), 0((0[0(00)])0), 0((0[(00)0])0), (00)(0[0(00)]), (00)(0[(00)0]).

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.
Toufik Mansour and Mark Shattuck, On ascent sequences avoiding 021 and a pattern of length four, arXiv:2507.17947 [math.CO], 2025. See p. 11.
Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2008-2010.
Eric S. Rowland, Pattern avoidance in binary trees, J. Comb. Theory A 117 (6) (2010) 741-758.

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

A161746 The number of equivalence classes of n-leaf binary trees with respect to contiguous pattern avoidance.

Original entry on oeis.org

1, 1, 1, 2, 3, 7, 15, 43, 136

Offset: 1

Eric Rowland, Jun 17 2009

			Representatives of the a(6) = 7 equivalence classes of 6-leaf binary trees are given in A036766, A159768, A159769, A159770, A159771, A159772, and A159773.

Andrey T. Cherkasov and Dmitri Piontkovski, Wilf classes of non-symmetric operads, arXiv:2105.08880 [math.CO], 2021.
L. Pudwell, Pattern avoidance in trees, (slides from a talk, mentions many sequences), 2012. - _N. J. A. Sloane_, Jan 03 2013
Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2008-2010.
Eric S. Rowland, Pattern avoidance in binary trees, J. Comb. Theory A 117 (6) (2010) 741-758.

Cf. A099952.

Per Cherkasov and Piontkovski, a(8) corrected by Eric Rowland, May 22 2021

a(9) from Eric Rowland, Apr 25 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs