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

Author

Markus Kuba, Dec 08 2013

Keywords

• nonn
• easy

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.

Crossrefs

Cf. A000139, A001764.

Programs

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 *)

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

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)

Extensions

More terms from F. Chapoton, May 26 2016