A239106 Ordered trees with branches of length at most 3.

1, 1, 2, 5, 13, 39, 121, 388, 1277, 4288, 14630, 50575, 176762, 623563, 2217379, 7939821, 28603591, 103600632, 377033451, 1378023887, 5056021292, 18615654196, 68758804039, 254706453524, 946038872000, 3522439937992, 13145057553230, 49157901220299

Offset

0,3

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Beáta Bényi, Toufik Mansour, and José L. Ramírez, Set partitions and non-crossing partitions with l-neighbors and l-isolated elements, Australasian J. Comb. (2022) Vol. 84, No. 2, 325-340.

Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees and branch lengths, Discrete Math., 282, 2004, 89-94. See p. 93.

Formula

a(n) = Sum_{k= ceiling(n/3)..n} trinomial(k,3;n-k) A001006(k-1).

G.f.: (1+x+x^2+x^3-sqrt(-3*x^6-6*x^5-9*x^4-8*x^3-5*x^2-2*x+1))/ (2*x^3+2*x^2+2*x). - Vladimir Kruchinin, Mar 03 2016

Recurrence: (n+1)*a(n) = (n-2)*a(n-1) + 6*(n-2)*a(n-2) + 3*(5*n - 13)*a(n-3) + (22*n - 83)*a(n-4) + (23*n - 112)*a(n-5) + 18*(n-6)*a(n-6) + 9*(n-7)*a(n-7) + 3*(n-8)*a(n-8). - Vaclav Kotesovec, Mar 03 2016

a(n) ~ sqrt(3*(3 - 1/(3-2*sqrt(2))^(1/3) - (3-2*sqrt(2))^(1/3))/2) * ((108-54*sqrt(2))^(1/3)/3 + (4+2*sqrt(2))^(1/3) + 1)^n / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 03 2016

Maple

beta := proc(n, k)
    coeftayl((x+x^2+x^3)^k, x=0, n) ;
end proc:
A239106 := proc(n)
    add( A001006(k-1)*beta(n, k), k=ceil(n/3)..n) ;
end proc: # R. J. Mathar, Apr 02 2014

Mathematica

CoefficientList[Series[(1 + x + x^2 + x^3 - Sqrt[-3*x^6 - 6*x^5 - 9*x^4 - 8*x^3 - 5*x^2 - 2*x + 1])/(2*x^3 + 2*x^2 + 2*x), {x, 0, 50}], x] (* G. C. Greubel, Apr 05 2017 *)

Prog

(PARI) x='x+O('x^50); Vec((1+x+x^2+x^3-sqrt(-3*x^6-6*x^5-9*x^4-8*x^3-5*x^2-2*x+1))/ (2*x^3+2*x^2+2*x)) \\ G. C. Greubel, Apr 05 2017

Crossrefs

Cf. A001006.

Sequence in context: A006823 A319378 A151446 * A022894 A332415 A149861

Adjacent sequences: A239103 A239104 A239105 * A239107 A239108 A239109

Keyword

nonn

Author

N. J. A. Sloane, Mar 26 2014

Status

approved