A180030 Number of n-move paths on a 3 X 3 chessboard of a queen starting or ending in a corner or side square.

1, 6, 38, 238, 1494, 9374, 58822, 369102, 2316086, 14533246, 91194918, 572240558, 3590762134, 22531735134, 141384772742, 887177744782, 5566966905846, 34932256487486, 219197017684198, 1375443140320878, 8630791843077974

Offset

0,2

Comments

The a(n) represent the number of n-move paths of a chess queen starting or ending in a given corner or side square (m = 1, 3, 7, 9; 2, 4, 6, 8) on a 3 X 3 chessboard. The central square leads to A180031.

To determine the a(n) we can either sum the components of the column vector A^n[k,m], with A the adjacency matrix of the queen's graph, or we can sum the components of the row vector A^n[m,k], see the Maple program.

Closely related with this sequence are the red queen sequences, see A180028 and A180032.

Inverse binomial transform of A015555 (without the leading 0).

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Index entries for linear recurrences with constant coefficients, signature (5, 8).

Formula

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

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

a(n) = ((7+11*A)*A^(-n-1) + (7+11*B)*B^(-n-1))/57 with A = (-5+sqrt(57))/16 and B = (-5-sqrt(57))/16.

Maple

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

Mathematica

LinearRecurrence[{5, 8}, {1, 6}, 201] (* Vincenzo Librandi, Nov 15 2011 *)

Prog

(Magma) I:=[1, 6]; [n le 2 select I[n] else 5*Self(n-1)+8*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 15 2011

Crossrefs

Sequence in context: A037499 A037676 A345464 * A135030 A217633 A162558

Adjacent sequences: A180027 A180028 A180029 * A180031 A180032 A180033

Keyword

nonn,easy

Author

Johannes W. Meijer, Aug 09 2010

Status

approved