login
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.
3

%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