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 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.
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
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 *)
PROG
(PARI) Vec(1/(1-serreverse(x*(1-x)/(1-x^4) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Eric Rowland, Apr 23 2009
STATUS
approved