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

1, 1, 2, 5, 14, 41, 124, 384, 1210, 3865, 12482, 40677, 133572, 441468, 1467296, 4900760, 16439370, 55357305, 187050302, 633998079, 2154950454, 7343407521, 25082709012, 85858848820, 294480653064, 1011871145116, 3482837144984, 12006861566684, 41454180382688

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.

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

Also, number of ordered rooted trees with n nodes and all non-root nodes having outdegrees < 4. - Andrew Howroyd, Dec 04 2017

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• CombOS - Combinatorial Object Server, Generate binary trees
• Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
• Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
• Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015.
• Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2008-2010.

Crossrefs

Column k=4 of A295679.

Cf. A036765, A064580.

Programs

Mathematica

terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];
col[4] (* Jean-François Alcover, Dec 05 2017, after Andrew Howroyd *)

Maxima

a(n):=if n=1 then 1 else sum(k*sum(binomial(n-1,j)*sum(binomial(j,i-j)*binomial(n-j-1,3*j-n-k-i+1),i,j,n-k+j-1),j,0,n-1),k,1,n-1)/(n-1); /* Vladimir Kruchinin, Oct 23 2011 */

PARI

Vec(1/(1-serreverse(x*(1-x)/(1-x^4) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017

Formula

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

a(n) = sum(k=1..n-1, k*sum(j=0..n-1, binomial(n-1,j)*sum(i=j..n-k+j-1, binomial(j,i-j)*binomial(n-j-1,3*j-n-k-i+1))))/(n-1), n>1. a(0)=0, a(1)=1. - Vladimir Kruchinin, Oct 23 2011

Conjecture: 2*(n-1)*(2*n-3)*a(n) +(-43*n^2+172*n-177)*a(n-1) +4*(44*n^2-266*n+411)*a(n-2) +8*(-43*n^2+358*n-741)*a(n-3) +96*(3*n^2-29*n+69)*a(n-4) -128*(n-4)*(n-6)*a(n-5) +512*(n-6)*(n-7)*a(n-6)=0. - R. J. Mathar, May 30 2014

G.f.: x/(1-x*G(x)) where G(x) is g.f. of A036765. - Andrew Howroyd, Dec 04 2017

From Vaclav Kotesovec, Dec 05 2017: (Start)

Recurrence (of order 4): 2*(n-1)*(2*n - 3)*(13*n^2 - 75*n + 104)*a(n) = 3*(117*n^4 - 1039*n^3 + 3315*n^2 - 4513*n + 2216)*a(n-1) - 12*(39*n^4 - 368*n^3 + 1268*n^2 - 1893*n + 1032)*a(n-2) - 16*(n-4)*(13*n^3 - 75*n^2 + 122*n - 54)*a(n-3) - 64*(n-5)*(n-4)*(13*n^2 - 49*n + 42)*a(n-4).

a(n) ~ sqrt(r*s*(r - s + 2*s^2) / (2*Pi*(r - 6*r^2 - 3*s + 12*r*s))) / (n^(3/2) * r^n), where r = 0.2769531794372340984240353119411920830379502290822... and s = 0.8081460429543529393193017440354060980373344931954... are real roots of the system of equations r^4 + r*(-1 + 6*r)*s^2 + (1 - 4*r)*s^3 = 4*r^3*s, s*(12*r^2 + 3*s - 2*r*(1 + 6*s)) = 4*r^3. (End)

a(n+1) = Sum_{k=0..n} A064580(n,k). - Georg Fischer, Jul 20 2023