A194723 Number of ternary words either empty or beginning with the first character of the alphabet, that can be built by inserting n doublets into the initially empty word.

1, 1, 5, 29, 181, 1181, 7941, 54573, 381333, 2699837, 19319845, 139480397, 1014536117, 7426790749, 54669443141, 404388938349, 3004139083221, 22402851226749, 167640057210981, 1258340276153229, 9471952718661621, 71481616200910749, 540715584181142661

Offset: 0

Author

Alois P. Heinz, Sep 02 2011

Keywords

• nonn

Examples

			a(2) = 5: aaaa, aabb, aacc, abba, acca (with ternary alphabet {a,b,c}).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• C. Kassel and C. Reutenauer, Algebraicity of the zeta function associated to a matrix over a free group algebra, arXiv preprint arXiv:1303.3481 [math.CO], 2013-2014.

Crossrefs

Column k=3 of A183134.

Cf. A194726.

Programs

Magma

[1] cat [&+[(Binomial(2*n, k)*(n-k)*2^k)/n: k in [0..n]]: n in [1..25]]; // Vincenzo Librandi, Apr 08 2018

Maple

a:= n-> `if`(n=0, 1, add(binomial(2*n, j) *(n-j) *2^j, j=0..n-1)/n):
seq(a(n), n=0..25);

Mathematica

CoefficientList[Series[2/3+4/(3*(1+3*Sqrt[1-8*x])), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 20 2012 *)
a[n_] := 2^(n+1) CatalanNumber[n] Hypergeometric2F1[2, 1-n, n+2, -2] - 3^(2n - 1);
Table[If[n == 0, 1, a[n]], {n, 0, 22}] (* Peter Luschny, Apr 08 2018 *)

PARI

a(n) = if (n==0, 1, sum(j=0, n-1, binomial(2*n,j)*(n-j)*2^j)/n); \\ Michel Marcus, Apr 07 2018

PARI

x='x+O('x^99); Vec(4/(3*(1+3*(1-8*x)^(1/2)))+2/3) \\ Altug Alkan, Apr 07 2018

Formula

G.f.: 2/3 + 4/(3*(1+3*sqrt(1-8*x))).

a(0) = 1, a(n) = 1/n * Sum_{j=0..n-1} C(2*n,j)*(n-j)*2^j for n>0.

D-finite with recurrence: n*a(n) = (17*n-12)*a(n-1) - 36*(2*n-3)*a(n-2). - Vaclav Kotesovec, Oct 20 2012

a(n) ~ 2^(3*n+1)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 20 2012

G.f.: 2-4/( Q(0) + 3), where Q(k) = 1 + 8*x*(4*k+1)/( 4*k+2 - 8*x*(4*k+2)*(4*k+3)/( 8*x*(4*k+3) + 4*(k+1)/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Nov 20 2013

From Karol A. Penson, Jul 13 2015: (Start)

Special values of the hypergeometric function 2F1, in Maple notation:

a(n+1) = (16/9)*8^n*GAMMA(n+3/2)*hypergeom([1, n+3/2], [n+3],8/9)/(sqrt(Pi)*(n+2)!), n=0,1,... .

Integral representation as the n-th moment of a positive function W(x) = sqrt((8-x)*x)*(1/(9-x))/(2*Pi) on (0,8): a(n+1) = int(x^n*W(x),x=0..8), n=0,1,... . This representation is unique as W(x) is the solution of the Hausdorff moment problem. (End)

a(n) = 2^(n+1)*binomial(2*n,n)*hypergeom([2,1-n],[n+2],-2)/(n+1) - 3^(2*n-1) for n>=1. - Peter Luschny, Apr 07 2018