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

1, 1, 2, 5, 14, 41, 124, 384, 1212, 3885, 12614, 41400, 137132, 457841, 1539150, 5205612, 17700450, 60473476, 207491052, 714668954, 2470156910, 8564900629, 29783782326, 103846841946, 362970362118, 1271546963124, 4463801464608

Offset

1,3

Comments

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

a(n) is also the number of Dyck words of semilength n-1 with no DDUUU.

Links

Table of n, a(n) for n=1..27.

CombOS - Combinatorial Object Server, Generate binary trees

Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2008-2010.

Jean-Luc Baril, Daniela Colmenares, José L. Ramírez, Emmanuel D. Silva, Lina M. Simbaqueba, and Diana A. Toquica, Consecutive pattern-avoidance in Catalan words according to the last symbol, Univ. Bourgogne (France 2023).

Eric Rowland and Reem Yassawi, Automatic congruences for diagonals of rational functions, arXiv:1310.8635 [math.NT], 2013.

Formula

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

Conjecture: 2*(n+1)*a(n) +3*(-3*n+1)*a(n-1) +2*(2*n-1)*a(n-2) +4*(2*n-7)*a(n-3) +2*(-2*n+7)*a(n-4)=0. - R. J. Mathar, May 30 2014

Crossrefs

Sequence in context: A161898 A159770 A159773 * A159771 A159768 A128739

Adjacent sequences: A159766 A159767 A159768 * A159770 A159771 A159772

Keyword

nonn

Author

Eric Rowland, Apr 23 2009

Status

approved