OFFSET
0,2
COMMENTS
The a(n) represent the number of n-move routes of a fairy chess piece starting in a given side square (m = 2, 4, 6 or 8) on a 3 X 3 chessboard. This fairy chess piece behaves like a rook on the eight side and corner squares but on the central square the rook goes berserk and turns into a berserker, see A180140.
The sequence above corresponds to 16 A[5] vectors with decimal values between 3 and 384. These vectors lead for the corner squares to A123620 and for the central square to A155116.
This sequence appears among the members of a family of sequences with g.f. (1 + x - k*x^2)/(1 - 3*x + (k-4)*x^2). Berserker sequences that are members of this family are 4*A007482 (k=2; with leading 1 added), A180142 (k=1; this sequence), A000302 (k=0), A180140 (k=-1) and 4*A154964 (k=-2; n>=1 and a(0)=1). Some other members of this family are 2*A180148 (k=3; with leading 1 added), 4*A025192 (k=4; with leading 1 added), 2*A005248 (k=5; with leading 1 added) and A123932 (k=6).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,3).
FORMULA
G.f.: (1 + x - x^2)/(1 - 3*x - 3*x^2).
a(n) = 3*a(n-1) + 3*a(n-2) for n >= 2 with a(0)=1, a(1)=4 and a(2)=14.
a(n) = (6-2*A)*A^(-n-1)/21 + (6-2*B)*B^(-n-1)/21 with A=(-3+sqrt(21))/6 and B=(-3-sqrt(21))/6.
MAPLE
with(LinearAlgebra): nmax:=23; m:=2; A[5]:=[0, 0, 0, 0, 0, 0, 0, 1, 1]: A:= Matrix([[0, 1, 1, 1, 0, 0, 1, 0, 0], [1, 0, 1, 0, 1, 0, 0, 1, 0], [1, 1, 0, 0, 0, 1, 0, 0, 1], [1, 0, 0, 0, 1, 1, 1, 0, 0], A[5], [0, 0, 1, 1, 1, 0, 0, 0, 1], [1, 0, 0, 1, 0, 0, 0, 1, 1], [0, 1, 0, 0, 1, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1, 1, 1, 0]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m, k], k=1..9): od: seq(a(n), n=0..nmax);
# second Maple program:
a:= n-> ceil((<<0|1>, <3|3>>^n. <<2/3, 4>>)[1, 1]):
seq(a(n), n=0..25); # Alois P. Heinz, Jul 14 2021
MATHEMATICA
LinearRecurrence[{3, 3}, {1, 4, 14}, 26] (* Jean-François Alcover, Jan 18 2025 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Johannes W. Meijer, Aug 13 2010
STATUS
approved