%I #27 Feb 06 2022 23:09:23
%S 1,1,7,61,591,6101,65719,729933,8297247,96044101,1128138567,
%T 13411861629,161066465583,1950996039669,23808159962839,
%U 292413627476141,3611870017079871,44838216520062117,559127724970143079,7000374603097246173,87964883375131331151
%N Number of 3n-length 3-ary words, either empty or beginning with the first letter of the alphabet, that can be built by repeatedly inserting triples of identical letters into the initially empty word.
%H Alois P. Heinz, <a href="/A218473/b218473.txt">Table of n, a(n) for n = 0..300</a>
%F a(n) = (1/n) * Sum_{j=0..n-1} binomial(3*n,j)*(n-j)*2^j for n>0, a(0) = 1.
%F a(n) ~ 3^(3*n-3/2)/(sqrt(Pi)*2^(n-1)*n^(3/2)). - _Vaclav Kotesovec_, May 22 2013
%F G.f. (for n>0): (1/(81*x-3)+2/((3-81*x)*(1-27*x-3*sqrt(3*x*(27*x-2)))^(2/3))). - _Vaclav Kotesovec_, Jul 06 2013
%F From _Peter Bala_, Feb 06 2022: (Start)
%F The o.g.f. A(x) satisfies the algebraic equation 8*x - 36*x*A(x) + (54*x - 1)*A(x)^2 + (-27*x + 1)*A(x)^3 = 0.
%F A(x) = (6 - 4*T(2*x))/(2*T(2*x)^2 - 9*T(2*x) + 9), where T(x) = 1 + x*T(x)^3 is the o.g.f. of A001764.
%F A(x) = 1 + 2*x*B'(2*x)/B(2*x), where B(x) = 2 + x + 2*x^2 + 6*x^3 + 22*x^4 + 91*x^5 + ... is the o.g.f. of A000139.
%F exp(Sum_{n >= 1} a(n)*x*n/n) = 1 + x + 4*x^2 + 24*x^3 + 176*x^4 + 1456*x^5 + ... is the o.g.f. of A000309, a power series with integral coefficients. It follows that the Gauss congruences a(n*p^k) == a(n*p*(k-1)) (mod p^k) hold for all prime p and positive integers n and k. (End)
%p a:= n-> `if`(n=0, 1, add(binomial(3*n, j)*(n-j)*2^j, j=0..n-1)/n):
%p seq(a(n), n=0..20);
%p # second Maple program
%p a:= proc(n) a(n):= `if`(n<3, [1, 1, 7][n+1], (-81*(3*n-1)*(3*n-5)*a(n-2)
%p +(81*n^2-81*n+15)*a(n-1))/ ((2*n-1)*n))
%p end:
%p seq(a(n), n=0..20);
%t Flatten[{1,Table[1/n*Sum[Binomial[3*n,j]*(n-j)*2^j,{j,0,n-1}],{n,1,20}]}] (* _Vaclav Kotesovec_, May 22 2013 *)
%t Flatten[{1,Table[FullSimplify[SeriesCoefficient[(1/(81*x-3)+2/((3-81*x)*(1-27*x-3*Sqrt[3*x*(27*x-2)])^(2/3))),{x,0,n}]],{n,1,10}]}] (* _Vaclav Kotesovec_, Jul 06 2013 *)
%Y Column k=3 of A213027. Cf. A000139, A000309, A001764.
%K nonn,easy
%O 0,3
%A _Alois P. Heinz_, Oct 29 2012