login
Eight white kings and one red king on a 3 X 3 chessboard. G.f.: (1 + 2*x)/(1 - 3*x - 8*x^2).
3

%I #8 Jun 30 2023 16:21:21

%S 1,5,23,109,511,2405,11303,53149,249871,1174805,5523383,25968589,

%T 122092831,574027205,2698824263,12688690429,59656665391,280479519605,

%U 1318691881943,6199911802669,29149270463551,137047105812005

%N Eight white kings and one red king on a 3 X 3 chessboard. G.f.: (1 + 2*x)/(1 - 3*x - 8*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 king on the eight side and corner squares but on the central square the king goes crazy and turns into a red king, see A179596.

%C The sequence above corresponds to 10 red king vectors, i.e., A[5] vectors, with decimal values 239, 351, 375, 381, 431, 471, 477, 491, 494, and 501. These vectors lead for the corner squares to A015525 and for the central square to A179599.

%C Inverse binomial transform of A126501.

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

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

%F a(n) = 3*a(n-1) + 8*a(n-2) with a(0) = 1 and a(1) = 5.

%F a(n) = ((41+5*sqrt(41))*A^(-n-1) + (41-5*sqrt(41))*B^(-n-1))/328 with A = (-3+sqrt(41))/16 and B = (-3-sqrt(41))/16.

%p with(LinearAlgebra): nmax:=21; m:=2; A[1]:= [0,1,0,1,1,0,0,0,0]: A[2]:= [1,0,1,1,1,1,0,0,0]: A[3]:= [0,1,0,0,1,1,0,0,0]: A[4]:=[1,1,0,0,1,0,1,1,0]: A[5]:= [1,0,1,1,1,1,1,0,1]: A[6]:= [0,1,1,0,1,0,0,1,1]: A[7]:= [0,0,0,1,1,0,0,1,0]: A[8]:= [0,0,0,1,1,1,1,0,1]: A[9]:= [0,0,0,0,1,1,0,1,0]: A:=Matrix([A[1],A[2],A[3],A[4],A[5],A[6],A[7],A[8],A[9]]): 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);

%Y Cf. A126473 (side squares).

%K easy,nonn

%O 0,2

%A _Johannes W. Meijer_, Jul 28 2010