A159772 - OEIS

%I #50 Jan 13 2025 20:31:32

%S 1,1,2,5,14,41,124,384,1210,3865,12482,40677,133572,441468,1467296,

%T 4900760,16439370,55357305,187050302,633998079,2154950454,7343407521,

%U 25082709012,85858848820,294480653064,1011871145116,3482837144984,12006861566684,41454180382688

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

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

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

%C Also, number of ordered rooted trees with n nodes and all non-root nodes having outdegrees < 4. - _Andrew Howroyd_, Dec 04 2017

%H Andrew Howroyd, <a href="/A159772/b159772.txt">Table of n, a(n) for n = 1..200</a>

%H CombOS - Combinatorial Object Server, <a href="http://combos.org/btree">Generate binary trees</a>

%H Isaac DeJager, Madeleine Naquin, and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.

%H Petr Gregor, Torsten Mütze, and Namrata, <a href="https://arxiv.org/abs/2306.08420">Combinatorial generation via permutation languages. VI. Binary trees</a>, arXiv:2306.08420 [cs.DM], 2023.

%H Nickolas Hein and Jia Huang, <a href="http://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015.

%H Eric S. Rowland, <a href="http://arxiv.org/abs/0809.0488">Pattern avoidance in binary trees</a>, arXiv:0809.0488 [math.CO], 2008-2010.

%F 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.

%F 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

%F 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

%F G.f.: x/(1-x*G(x)) where G(x) is g.f. of A036765. - _Andrew Howroyd_, Dec 04 2017

%F From _Vaclav Kotesovec_, Dec 05 2017: (Start)

%F 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).

%F 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)

%F a(n+1) = Sum_{k=0..n} A064580(n,k). - _Georg Fischer_, Jul 20 2023

%t terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];

%t col[4] (* _Jean-François Alcover_, Dec 05 2017, after _Andrew Howroyd_ *)

%o (PARI) Vec(1/(1-serreverse(x*(1-x)/(1-x^4) + O(x*x^25)))) \\ _Andrew Howroyd_, Dec 04 2017

%o (Maxima)

%o 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 */

%Y Column k=4 of A295679.

%Y Cf. A036765, A064580.

%K nonn,changed

%O 1,3

%A _Eric Rowland_, Apr 23 2009