A180142 - OEIS

%I #13 Jan 18 2025 09:08:31

%S 1,4,14,54,204,774,2934,11124,42174,159894,606204,2298294,8713494,

%T 33035364,125246574,474845814,1800277164,6825368934,25876938294,

%U 98106921684,371951579934,1410175504854,5346381254364,20269670277654,76848154596054,291353474621124

%N Eight rooks and one berserker on a 3 X 3 chessboard. G.f.: (1 + x - x^2)/(1 - 3*x - 3*x^2).

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

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

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

%H Alois P. Heinz, <a href="/A180142/b180142.txt">Table of n, a(n) for n = 0..1000</a>

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

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

%F a(n) = 3*a(n-1) + 3*a(n-2) for n >= 2 with a(0)=1, a(1)=4 and a(2)=14.

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

%F Lim_{k->infinity} a(2*n+k)/a(k) = 2*A000244(n)/(A003501(n) - A004254(n)*sqrt(21)) for n >= 1.

%F Lim_{k->infinity} a(2*n-1+k)/a(k) = 2*A000244(n)/(A004253(n)*sqrt(21) - 3*A030221(n-1)) for n >= 1.

%p 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);

%p # second Maple program:

%p a:= n-> ceil((<<0|1>, <3|3>>^n. <<2/3, 4>>)[1,1]):

%p seq(a(n), n=0..25);  # _Alois P. Heinz_, Jul 14 2021

%t LinearRecurrence[{3, 3}, {1, 4, 14}, 26] (* _Jean-François Alcover_, Jan 18 2025 *)

%Y Cf. A180141 (corner squares), A180140 (side squares), A180147 (central square).

%K easy,nonn

%O 0,2

%A _Johannes W. Meijer_, Aug 13 2010