A062208 a(n) = Sum_{m>=0} binomial(m,3)^n*2^(-m-1).

1, 1, 63, 16081, 10681263, 14638956721, 35941784497263, 143743469278461361, 874531783382503604463, 7687300579969605991710001, 93777824804632275267836362863, 1537173608464960118370398000894641, 32970915649974341628739088902163732463

Offset

0,3

Comments

Number of alignments of n strings of length 3.

Conjectures: a(2*n) = 3 (mod 60) and a(2*n+1) = 1 (mod 60); for fixed k, the sequence a(n) (mod k) eventually becomes periodic with exact period a divisor of phi(k), where phi(k) is Euler's totient function A000010. - Peter Bala, Feb 04 2018

Links

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

J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

Formula

From Vaclav Kotesovec, Mar 22 2016: (Start)

a(n) ~ 3^(2*n + 1/2) * n!^3 / (Pi * n * 2^(n+3) * (log(2))^(3*n+1)).

a(n) ~ sqrt(Pi)*3^(2*n+1/2)*n^(3*n+1/2) / (2^(n+3/2)*exp(3*n)*(log(2))^(3*n+1)).

(End)

a(n) = Sum_{k = 3..3*n} Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)* binomial(i,3)^n. Row sums of A299041. - Peter Bala, Feb 04 2018

Maple

A000629 := proc(n) local k ; sum( k^n/2^k, k=0..infinity) ; end: A062208 := proc(n) local a, stir, ni, n1, n2, n3, stir2, i, j, tmp ; a := 0 ; if n = 0 then RETURN(1) ; fi ; stir := combinat[partition](n) ; stir2 := {} ; for i in stir do if nops(i) <= 3 then tmp := i ; while nops(tmp) < 3 do tmp := [op(tmp), 0] ; od: tmp := combinat[permute](tmp) ; for j in tmp do stir2 := stir2 union { j } ; od: fi ; od: for ni in stir2 do n1 := op(1, ni) ; n2 := op(2, ni) ; n3 := op(3, ni) ; a := a+combinat[multinomial](n, n1, n2, n3)*(A000629(3*n1+2*n2+n3)-1/2-2^(3*n1+2*n2+n3)/4)*(-3)^n2*2^n3 ; od: a/(2*6^n) ; end: seq(A062208(n), n=0..14) ; # R. J. Mathar, Apr 01 2008
a:=proc(n) options operator, arrow: sum(binomial(m, 3)^n*2^(-m-1), m=0.. infinity) end proc: seq(a(n), n=0..12); # Emeric Deutsch, Mar 22 2008

Mathematica

a[n_] = Sum[2^(-1-m)*((m-2)*(m-1)*m)^n, {m, 0, Infinity}]/6^n; a /@ Range[0, 12] (* Jean-François Alcover, Jul 13 2011 *)
With[{r = 3}, Flatten[{1, Table[Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, r]^k, {i, 0, j}], {j, 0, k*r}], {k, 1, 15}]}]] (* Vaclav Kotesovec, Mar 22 2016 *)

Crossrefs

Cf. A000670, A055203, A001850, A126086.

See A062204 for further references, formulas and comments.

Cf. A001850, A062204, A062205, A299041.

Row n=3 of A262809.

Sequence in context: A234629 A270507 A289875 * A132594 A212932 A349902

Adjacent sequences: A062205 A062206 A062207 * A062209 A062210 A062211

Keyword

nonn,easy

Author

Angelo Dalli, Jun 13 2001

Extensions

New definition from Vladeta Jovovic, Mar 01 2008

Edited by N. J. A. Sloane, Sep 19 2009 at the suggestion of Max Alekseyev

Status

approved