A194725 Number of 5-ary 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, 9, 97, 1145, 14289, 185193, 2467137, 33563481, 464221105, 6507351113, 92236247841, 1319640776249, 19031570387857, 276368559434025, 4037555902072065, 59299855337012505, 875056238174271345, 12967283824008178185, 192889769468751321825, 2879117809973276680185

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

C. Kassel and C. Reutenauer, Algebraicity of the zeta function associated to a matrix over a free group algebra, arXiv preprint arXiv:1303.3481, 2013

Formula

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

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

a(n) ~ 2^(4*n+2)/(9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 13 2013

Recurrence: n*a(n) = (41*n-24)*a(n-1) - 200*(2*n-3)*a(n-2). - Vaclav Kotesovec, Aug 13 2013

Example

a(2) = 9: aaaa, aabb, aacc, aadd, aaee, abba, acca, adda, aeea (with 5-ary alphabet {a,b,c,d,e}).

Maple

a:= n-> `if`(n=0, 1, add(binomial(2*n, j) *(n-j) *4^j, j=0..n-1) /n):
seq(a(n), n=0..20);
# second Maple program
a:= proc(n) a(n):= `if`(n<3, [1, 1, 9][n+1],
       ((41*n-24)*a(n-1) +(600-400*n)*a(n-2))/n)
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Oct 30 2012

Mathematica

FullSimplify[Flatten[{1, Table[4^(2*n+1)*(1/2 (2*n-1))! Hypergeometric2F1[1, 1/2+n, 2+n, 16/25]/(25*Sqrt[Pi]*(n+1)!), {n, 1, 20}]}]] (* Vaclav Kotesovec, Aug 13 2013 *)

Crossrefs

Column k=5 of A183134.

Sequence in context: A241771 A180675 A083077 * A218500 A293986 A123821

Adjacent sequences: A194722 A194723 A194724 * A194726 A194727 A194728

Keyword

nonn

Author

Alois P. Heinz, Sep 02 2011

Status

approved