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

1, 4, 16, 68, 280, 1168, 4848, 20160, 83776, 348224, 1447296, 6015488, 25002240, 103917568, 431915008, 1795179520, 7461349376, 31011794944, 128895102976, 535729963008, 2226667929600, 9254755975168, 38465775239168

Offset: 0

Author

Johannes W. Meijer, Jul 28 2010

Keywords

• easy
• nonn

Comments

The a(n) represent the number of n-move routes of a fairy chess piece starting in the central square (m = 5) 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.

The sequence above corresponds to 36 red king vectors, i.e., A[5] vectors, with decimal values 15, 39, 45, 75, 78, 99, 102, 105, 108, 135, 141, 165, 195, 198, 201, 204, 225, 228, 267, 270, 291, 294, 297, 300, 330, 354, 360, 387, 390, 393, 396, 417, 420, 450, 456 and 480.

Links

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

Crossrefs

Cf. A179596, A179597 (central square).

Cf. A052904.

Programs

Maple

with(LinearAlgebra): nmax:=22; m:=5; 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]:= [0,0,0,0,0,1,1,1,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);

Mathematica

LinearRecurrence[{2,8,4},{1,4,16},30] (* Harvey P. Dale, Oct 20 2017 *)

Formula

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

a(n) = 2*a(n-1) + 8*a(n-2) + 4*a(n-3) with a(1)=1, a(2)=4 and a(3)=16.

a(n) = (8 + 3*z1 - 6*z1^2)*z1^(-n)/(z1*37) + (8 + 3*z2 - 6*z2^2)*z2^(-n)/(z2*37) + (8 + 3*z3 - 6*z3^2)*z3^(-n)/(z3*37) with z1, z2 and z3 the roots of f(x) = 1 - 2*x - 8*x^2 - 4*x^3 = 0.

alpha = arctan(3*sqrt(111));

z1 = sqrt(10)*cos(alpha/3)/6 + sqrt(30)*sin(alpha/3)/6 - 2/3 = 0.2405971520460078;

z2 = -sqrt(10)*cos(alpha/3)/3 - 2/3 = -1.585043243313016;

z3 = sqrt(10)*cos(alpha/3)/6 - sqrt(30)*sin(alpha/3)/6 - 2/3 = -0.6555539087329909.