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

1, 1, 2, 5, 14, 41, 124, 385, 1220, 3929, 12822, 42309, 140922, 473169, 1599864, 5442561, 18615176, 63975857, 220816906, 765121477, 2660426630, 9280204025, 32466050612, 113883898241, 400464335116, 1411407234697, 4984885122974

Offset

1,3

Comments

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

For n >= 2, number of Motzkin paths of length n-2 with two colors of flat steps and avoiding UU. - David Scambler, Jun 24 2013

For n >= 2, number of Motzkin paths of length n-2 with two colors of flat steps and avoiding DU. - Torsten Muetze, May 10 2023

Links

Michael De Vlieger, Table of n, a(n) for n = 1..1757

Jean-Luc Baril and Paul Barry, Two kinds of partial Motzkin paths with air pockets, arXiv:2212.12404 [math.CO], 2022.

Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.

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.

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

Formula

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

a(n) = Sum_{k=0..floor(n/2)} 1/(n-k+0^(n-k))*C(n-k,k)*C(n-k,k+1)*2^(n-2k-1). - Paul Barry, Nov 18 2009

G.f.: ((1-2*x+3*x^2) - sqrt((1+x^2)*(1-4*x+x^2)))/(4*x). - Paul D. Hanna, Aug 02 2012

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

Mathematica

((1 - 2x + 3x^2) - Sqrt[(1 + x^2)(1 - 4x + x^2)])/(4x) + O[x]^28 // CoefficientList[#, x]& // Rest (* Jean-François Alcover, Oct 27 2018 *)

Prog

(PARI) {a(n)=polcoeff(((1-2*x+3*x^2) - sqrt((1+x^2)*(1-4*x+x^2)+x^2*O(x^n)))/(4*x), n)} \\ Paul D. Hanna, Aug 02 2012

Crossrefs

Sequence in context: A159770 A159773 A159769 * A159768 A128739 A356698

Adjacent sequences: A159768 A159769 A159770 * A159772 A159773 A159774

Keyword

nonn

Author

Eric Rowland, Apr 23 2009

Status

approved