A159770 Number of n-leaf binary trees that do not contain (()(()(((()())())()))) as a subtree.

1, 1, 2, 5, 14, 41, 124, 384, 1211, 3875, 12548, 41040, 135370, 449791, 1504057, 5057668, 17092030, 58018150, 197727023, 676290905, 2320721255, 7987481185, 27566740439, 95379299734, 330774138321, 1149589209136, 4003322875481

Offset

1,3

Comments

By 'binary tree' we mean a rooted, ordered tree in which each vertex has either 0 or 2 children.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

CombOS - Combinatorial Object Server, Generate binary trees

Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.

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.

Formula

G.f. f(x) satisfies x f(x)^3 + (-2 x^2 + 3 x - 1) f(x)^2 + x (x^2 - 3 x + 1) f(x) + x^3 = 0

Crossrefs

Sequence in context: A366046 A159772 A161898 * A159773 A159769 A159771

Adjacent sequences: A159767 A159768 A159769 * A159771 A159772 A159773

Keyword

nonn

Author

Eric Rowland, Apr 23 2009

Status

approved