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

1, 1, 2, 5, 14, 41, 124, 385, 1221, 3939, 12886, 42648, 142544, 480459, 1631287, 5574073, 19153815, 66146259, 229452587, 799140681, 2793373937, 9796395680, 34459558856, 121548541383, 429823475811, 1523511450184, 5411789548439

Offset: 1

Author

Eric Rowland, Apr 23 2009

Keywords

• nonn

Comments

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

Links

• 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.

Formula

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