A175660 Eight bishops and one elephant on a 3 X 3 chessboard. a(n) = 2^(n+2) - 3*F(n+2).

1, 2, 7, 17, 40, 89, 193, 410, 859, 1781, 3664, 7493, 15253, 30938, 62575, 126281, 254392, 511745, 1028281, 2064314, 4141171, 8302637, 16638112, 33329357, 66744685, 133628474, 267482023, 535328225, 1071245704, 2143444841

Offset

0,2

Comments

The a(n) represent the number of n-move routes of a fairy chess piece starting in a given corner square (m = 1, 3, 7, 9) on a 3 X 3 chessboard. This fairy chess piece behaves like a bishop on the eight side and corner squares but on the central square the bishop turns into a raging elephant, see A175654.

The sequence above corresponds to four A[5] vectors with decimal values 171, 174, 234 and 426. These vectors lead for the side squares to A000079 and for the central square to A175661 (a(n) = 2^(n+2) - 3*F(n+1)).

Links

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (3, -1, -2).

Formula

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

a(n) = 3*a(n-1) - a(n-2) - 2*a(n-3) with a(0)=1, a(1)=2 and a(2)=7.

a(n) = 2^(n+2) - 3*F(n+2) with F(n)=A000045(n).

Maple

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

Table[2^(n+2)-3Fibonacci[n+2], {n, 0, 30}] (* or *) LinearRecurrence[ {3, -1, -2}, {1, 2, 7}, 30] (* Harvey P. Dale, Dec 28 2012 *)

Crossrefs

Cf. A008466 (2^n-F(n+2)), A027934 (2^n-F(n+1)), A027974 (2^(n+3)-F(n+5)-F(n+3)), A074878 (3*2^n-2*F(n+2)), A142585 ((-1)^(n+1)*(2^(n-1)-F(n+1)-F(n-1))), A175661 (2^(n+2)-3*F(n+1)), A179610 (convolution of (-4)^n and F(n+1)).

Sequence in context: A067038 A209398 A364756 * A365069 A347079 A370304

Adjacent sequences: A175657 A175658 A175659 * A175661 A175662 A175663

Keyword

easy,nonn

Author

Johannes W. Meijer, Aug 06 2010, Aug 10 2010

Status

approved