%I #40 May 31 2022 14:29:55
%S 1,1,3,11,46,209,1006,5053,26227,139726,760398,4211959,23681987,
%T 134869448,776657383,4516117107,26486641078,156532100029,931426814462,
%U 5576590927886,33574649282538,203169756237944,1235156720288767,7541099028832261,46222213821431646
%N Naturally embedded ternary trees having no internal node of label greater than 1.
%H Alois P. Heinz, <a href="/A233389/b233389.txt">Table of n, a(n) for n = 0..1000</a>
%H Markus Kuba, <a href="https://doi.org/10.37236/629">A note on naturally embedded ternary trees</a>, Electronic Journal of Combinatorics, Volume 18 (1), paper P142, 2011.
%H Markus Kuba, <a href="http://arxiv.org/abs/0902.2646">A note on naturally embedded ternary trees</a>, arXiv:0902.2646 [math.CO], 2009.
%F 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.
%F From _Peter Bala_, Feb 06 2022: (Start)
%F 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.
%F 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)
%p a:= proc(n) option remember; `if`(n<3, 1+n*(n-1),
%p ((1349*n^2-2738*n+953)*n*a(n-1) -(5567*n^3-20114*n^2
%p +22439*n-7320)*a(n-2)-(3*(3*n-4))*(19*n-11)*(3*n-5)
%p *a(n-3))/((2*(2*n-1))*(n+1)*(19*n-30)))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jul 03 2017
%t 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))];
%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 09 2017, after _Alois P. Heinz_ *)
%o (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
%Y Cf. A000139, A001764.
%K nonn,easy
%O 0,3
%A _Markus Kuba_, Dec 08 2013
%E More terms from _F. Chapoton_, May 26 2016