A094309 Number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < 6 and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = 2, s(n) = 5.

1, 4, 14, 44, 132, 384, 1096, 3088, 8624, 23936, 66144, 182208, 500800, 1374208, 3766400, 10313984, 28226304, 77211648, 211138048, 577223680, 1577772032, 4312088576, 11783915520, 32200396800, 87985401856, 240405151744

Offset: 3

Author

Herbert Kociemba, Jun 02 2004

Keywords

• easy
• nonn

Comments

In general, a(n,m,j,k) = (2/m)*Sum_{r=1..m-1} sin(j*r*Pi/m)*sin(k*r*Pi/m)*(1+2*cos(Pi*r/m))^n is the number of (s(0), s(1), ..., s(n)) such that 0 < s(i) < m and |s(i) - s(i-1)| <= 1 for i = 1,2,...,n, s(0) = j, s(n) = k.

With offset = 1, a(n) is the number of length n words on {0,1,2} in which the longest run of consecutive 0's is exactly 1. - Geoffrey Critzer, Jan 13 2013

Links

• Vincenzo Librandi, Table of n, a(n) for n = 3..1000
• Index entries for linear recurrences with constant coefficients, signature (4,-2,-4).

Programs

Magma

I:=[1, 4, 14]; [n le 3 select I[n] else 4*Self(n-1)-2*Self(n-2)-4*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jun 24 2012

Mathematica

f[n_] := FullSimplify[ TrigToExp[(1/3)Sum[ Sin[Pi*k/3] Sin[5Pi*k/6](1 + 2Cos[Pi*k/6])^n, {k, 1, 5}]]]; Table[ f[n], {n, 3, 28}] (* Robert G. Wilson v, 2004 *)
LinearRecurrence[{4,-2, -4},{1,4,14},40] (* Vincenzo Librandi, Jun 24 2012 *)
CoefficientList[Series[1/(1-4 x+2 x^2+4 x^3),{x,0,30}],x] (* Harvey P. Dale, Aug 04 2021 *)

Formula

a(n) = (1/3) * Sum_{k=1..5} sin(Pi*k/3)*sin(5*Pi*k/6)*(1+2*cos(Pi*k/6))^n.

From Paul Barry, Jul 28 2004: (Start)

G.f. : x^3/((1-2*x)*(1-2*x-2*x^2));

a(n) = 4*a(n-1) - 2*a(n-2) - 4*a(n-3);

a(n) = (1+sqrt(3))^n*(3/2 + 5*sqrt(3)/6) + (1-sqrt(3))^n*(3/2 - 5*sqrt(3)/6) - 2^(n+1) [offset 0]. (End)