

A180140


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


14



1, 4, 18, 74, 312, 1306, 5478, 22964, 96282, 403666, 1692408, 7095554, 29748702, 124723876, 522915138, 2192364794, 9191670072, 38536834186, 161568852918, 677390729684, 2840016453642, 11907003009346, 49921091296248
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

a(n) gives the number of nmove routes of a fairy chess piece starting in a given side square (m = 2, 4, 6, 8) on a 3 X 3 chessboard. This fairy chess piece behaves like a rook on the four side and four corner (m = 1, 3, 7, 9) squares but on the center square (m = 5) it goes berserk and turns into a berserker. For this sequence, the berserker can move to three of the side squares and three of the corners from the center.
The berserker is one of the Lewis chessmen which were discovered in 1831 on the Isle of Lewis. They are carved from walrus ivory in Scandinavian style of the 12th century. The pawns look like decorated tombstones. The pieces have all human representations with facial expressions varying from gloom to anger. Some of the rooks show men biting their shield in the manner of berserkers. According to Hooper and Whyld none looks happy.
Let A be the adjacency matrix of the graph G, where V(G) = {v1, v2, v3, v4, v5, v6, v7, v8, v9}. Then the (m, k) entry of A^n is the number of different vmvk walks of length n in G, see the Chartrand reference. In the adjacency matrix A, see the Maple program, the A[1], A[3], A[7] and A[9] vectors represent the rook moves on the corner squares, the A[2], A[4], A[6] and A[8] vectors represent the rook moves on the side squares and the A[5] vector represents the moves of the berserker. On a 3 X 3 chessboard there are 2^9 = 512 ways a berserker could move from the center square (off the center the berserker behaves like a rook) so there are 512 different berserkers.
For the side squares the 512 berserker vectors lead to 42 different sequences, see the overview of berserker sequences. There are 16 berserker vectors that lead to the sequence given above. Their decimal [binary] values are: 111 [001 101 111] , 207 [011 001 111], 231 [011 100 111], 237 [011 101 101], 303 [100 101 111], 363 [101 101 011], 366 [101 101 110], 399 [110 001 111], 423 [110 100 111], 429 [110 101 101], 459 [111 001 011], 462 [111 001 110], 483 [111 100 011], 486 [111 100 110], 489 [111 101 001] and 492 [111 101 100]. These berserker vectors lead for the corner squares to sequence 4*A179606 (with leading term 1 added) and for the central square to sequence 6*A179606 (with leading term 1 added).
This sequence belongs to a family of sequences with GF(x)=(1+xk*x^2)/(13*x+(k4)*x^2), see A180142.


REFERENCES

Gary Chartrand, Introductory Graph Theory, pp. 217221, 1984.
David Hooper and Kenneth Whyld, The Oxford Companion to Chess, pp. 131, 225, 1992.


LINKS

Indranil Ghosh, Table of n, a(n) for n = 0..1603
Dougie MacLean, The Lewis Chessmen: "Marching Mystery"
Johannes W. Meijer, The berserker sequences.
Wikipedia, Lewis Chessmen
Index entries for linear recurrences with constant coefficients, signature (3,5)


FORMULA

G.f.: (1+x+x^2)/(13*x5*x^2).
a(n) = 3*a(n1) + 5*a(n2) for n>=3 with a(0)=1, a(1)=4 and a(2)=18.
a(n) = ((22+54*A)*A^(n1) + (22+54*B)*B^(n1))/145 with A=(3+sqrt(29))/10 and B=(3sqrt(29))/10 for n>=1 with a(0)=1.
5*a(n) = 2*( A015523(n) + 3*A015523(n+1)), n>0  R. J. Mathar, May 11 2013


MAPLE

nmax:=22; m:=2; A[1]:=[0, 1, 1, 1, 0, 0, 1, 0, 0]: A[2]:=[1, 0, 1, 0, 1, 0, 0, 1, 0]: A[3]:= [1, 1, 0, 0, 0, 1, 0, 0, 1]: A[4]:= [1, 0, 0, 0, 1, 1, 1, 0, 0]: A[5]:=[0, 0, 1, 1, 0, 1, 1, 1, 1]: A[6]:=[0, 0, 1, 1, 1, 0, 0, 0, 1]: A[7]:=[1, 0, 0, 1, 0, 0, 0, 1, 1]: A[8]:=[0, 1, 0, 0, 1, 0, 1, 0, 1]: A[9]:=[0, 0, 1, 0, 0, 1, 1, 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

CoefficientList[Series[(1+x+x^2)/(13*x5*x^2), {x, 0, 22}], x] (* or *) LinearRecurrence[{3, 5, 0}, {1, 4, 18}, 23] (* Indranil Ghosh, Mar 05 2017 *)


PROG

(PARI) print(Vec((1 + x + x^2)/(1 3*x  5*x^2) + O(x^23))); \\ Indranil Ghosh, Mar 05 2017


CROSSREFS

Cf. A180141 (corner squares) and A180147 (central square).
Cf. Berserker sequences side squares: 4*A007482 (with leading 1 added), A180144, A003500 (n>=1 and a(0)=1), A180142, A000302, A180140 (this sequence), 2*A001077 (n>=1 and a(0)=1), A180146, 4*A154964 (n>=1 and a(0)=1), 4*A123347 (with leading 1 added).
Sequence in context: A218059 A069008 A026560 * A245127 A037674 A066259
Adjacent sequences: A180137 A180138 A180139 * A180141 A180142 A180143


KEYWORD

nonn,easy


AUTHOR

Johannes W. Meijer, Aug 13 2010, Jun 15 2013


STATUS

approved



