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

%I #30 Feb 12 2022 17:55:19

%S 1,4,14,44,132,384,1096,3088,8624,23936,66144,182208,500800,1374208,

%T 3766400,10313984,28226304,77211648,211138048,577223680,1577772032,

%U 4312088576,11783915520,32200396800,87985401856,240405151744

%N 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.

%C 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.

%C 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

%H Vincenzo Librandi, <a href="/A094309/b094309.txt">Table of n, a(n) for n = 3..1000</a>

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-4).

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

%F From _Paul Barry_, Jul 28 2004: (Start)

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

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

%F 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)

%t 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 *)

%t LinearRecurrence[{4,-2, -4},{1,4,14},40] (* _Vincenzo Librandi_, Jun 24 2012 *)

%t CoefficientList[Series[1/(1-4 x+2 x^2+4 x^3),{x,0,30}],x] (* _Harvey P. Dale_, Aug 04 2021 *)

%o (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

%K easy,nonn

%O 3,2

%A _Herbert Kociemba_, Jun 02 2004