login
A365508
Number of n-vertex binary trees that do not contain 0[0(0[0(00)])] as a subtree.
2
1, 2, 5, 14, 41, 123, 375, 1157, 3603, 11304, 35683, 113219, 360805, 1154140
OFFSET
1,2
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 P as a subtree, where P is one of 0[0(0((00)0))], 0[0((00)(00))], 0[0((0(00))0)], 0[(00)(0(00))], 0[(00)((00)0)], 0[(0(00))(00)], 0[((00)0)(00)], 0[(0((00)0))0], 0[((00)(00))0], 0[((0(00))0)0], 0(([0(00)]0)0), 0(([(00)0]0)0).
Number of restricted growth strings of set partitions of {1,...,n} that avoid the two patterns 1212 and p, where p is one of 12232, 12113, 12322, 11213.
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.
Sequence in context: A360569 A326254 A054391 * A176677 A365510 A108626
KEYWORD
nonn,more
AUTHOR
Torsten Muetze, Sep 07 2023
STATUS
approved