A233389 Naturally embedded ternary trees having no internal node of label greater than 1.

1, 1, 3, 11, 46, 209, 1006, 5053, 26227, 139726, 760398, 4211959, 23681987, 134869448, 776657383, 4516117107, 26486641078, 156532100029, 931426814462, 5576590927886, 33574649282538, 203169756237944, 1235156720288767, 7541099028832261, 46222213821431646

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Markus Kuba, A note on naturally embedded ternary trees, Electronic Journal of Combinatorics, Volume 18 (1), paper P142, 2011.

Markus Kuba, A note on naturally embedded ternary trees, arXiv:0902.2646 [math.CO], 2009.

Formula

G.f.: (T(z) - 2)*T^3(z)/(T^2(z) - 3*T(z) + 1), where T(z) = 1 + z*T^3(z) is the generating function of ternary trees - see A001764.

From Peter Bala, Feb 06 2022: (Start)

a(n) = (2/(n+1))*binomial(3*n,n) + Sum_{k=0..n} (-1)^(k+1)*Fibonacci(k+1)* binomial(3*n,n-k)*(n*(11*k+5)-2*k(k+1))/(n*(2*n+k+1)) for n >= 1. See Kuba, Corollary 1, p. 6.

O.g.f.: A(x) = (1/x)*(B(x) - 2)/(B(x) - 1), where B(x) = Sum_{n >= 0} 2*(3*n)!/((2*n+1)!*((n+1)!))*x^n is the o.g.f. of A000139. (End)

Maple

a:= proc(n) option remember; `if`(n<3, 1+n*(n-1),
      ((1349*n^2-2738*n+953)*n*a(n-1) -(5567*n^3-20114*n^2
       +22439*n-7320)*a(n-2)-(3*(3*n-4))*(19*n-11)*(3*n-5)
       *a(n-3))/((2*(2*n-1))*(n+1)*(19*n-30)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 03 2017

Mathematica

a[n_] := a[n] = If[n < 3, 1 + n*(n - 1), ((1349*n^2 - 2738*n + 953)*n*a[n - 1] - (5567*n^3 - 20114*n^2 + 22439*n - 7320)*a[n - 2] - (3*(3*n - 4)) * (19*n - 11)*(3*n - 5)*a[n - 3])/((2*(2*n - 1))*(n + 1)*(19*n - 30))];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 09 2017, after Alois P. Heinz *)

Prog

(PARI) N=66; x='x+O('x^N); T=serreverse(x-x^3)/x; v=Vec(((T-2)*T^3/(T^2-3*T+1))); vector(#v\2, n, v[2*n-1]) \\ Joerg Arndt, May 26 2016

Crossrefs

Cf. A000139, A001764.

Sequence in context: A193074 A287891 A371428 * A281548 A086521 A225293

Adjacent sequences: A233386 A233387 A233388 * A233390 A233391 A233392

Keyword

nonn,easy

Author

Markus Kuba, Dec 08 2013

Extensions

More terms from F. Chapoton, May 26 2016

Status

approved