A094306 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) = 4.

1, 3, 10, 30, 88, 252, 712, 1992, 5536, 15312, 42208, 116064, 318592, 873408, 2392192, 6547584, 17912320, 48985344, 133926400, 366085632, 1000548352, 2734316544, 7471826944, 20416481280, 55785005056, 152419749888

Offset

2,2

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.

Links

Colin Barker, Table of n, a(n) for n = 2..1000

Index entries for linear recurrences with constant coefficients, signature (4,-2,-4).

Formula

a(n) = ((1-sqrt(3))^n + (1+sqrt(3))^n - 2^n)/4.

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

From Colin Barker, Oct 29 2019: (Start)

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

a(n) = 4*a(n-1) - 2*a(n-2) - 4*a(n-3) for n>4.

(End)

Mathematica

f[n_] := FullSimplify[ TrigToExp[(1/3)Sum[ Sin[Pi*k/3] Sin[2Pi*k/3] (1 + 2Cos[Pi*k/6])^n, {k, 1, 5}]]]; Table[ f[n], {n, 2, 27}] (* Robert G. Wilson v, Jun 18 2004 *)

Prog

(PARI) Vec(x^2*(1 - x) / ((1 - 2*x)*(1 - 2*x - 2*x^2)) + O(x^35)) \\ Colin Barker, Oct 29 2019

Crossrefs

Sequence in context: A027205 A026937 A320564 * A257596 A261336 A026109

Adjacent sequences: A094303 A094304 A094305 * A094307 A094308 A094309

Keyword

easy,nonn

Author

Herbert Kociemba, Jun 02 2004

Status

approved