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

1, 5, 17, 81, 325, 1413, 5913, 25193, 106429, 451421, 1911089, 8097825, 34298293, 145299189, 615478665, 2607246617, 11044399597, 46784976077, 198184041761, 839521667409, 3556269662821, 15064602415845, 63814675131897

Offset

0,2

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 toes crazy and turns into a red king, see A179596.

The sequence above corresponds to 4 red king vectors, A[5] vectors, with decimal [binary] values 327 [1,0,1,0,0,0,1,1,1], 333 [1,0,1,0,0,1,1,0,1], 357 [1,0,1,1,0,0,1,0,1] and 453 [1,1,1,0,0,0,1,0,1]. These vectors lead for the corner squares to A179604 and for the side squares to A015448.

Links

Table of n, a(n) for n=0..22.

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

Formula

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

a(n) = 2*a(n-1) + 9*a(n-2) + 2*a(n-3) with a(0)=1, a(1)=5 and a(2)=17.

a(n) = (-4/11)*(-1/2)^(-n) + ((17+41*A)*A^(-n-1) + (17+41*B)*B^(-n-1))/110 with A = (-2+sqrt(5)) and B =(-2-sqrt(5)).

Limit_{k->oo} a(n+k)/a(k) = (-1)^(n+1)/(A001076(n)*sqrt(5) - A001077(n)).

Maple

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

Crossrefs

Cf. A001076, A001077, A015448, A179596, A179597 (central square), A179604.

Sequence in context: A359206 A149749 A149750 * A149751 A303713 A188231

Adjacent sequences: A179602 A179603 A179604 * A179606 A179607 A179608

Keyword

easy,nonn

Author

Johannes W. Meijer, Jul 28 2010

Status

approved