A086348 On a 3 X 3 board, number of n-move routes of chess king ending in the central square.

1, 8, 32, 168, 784, 3840, 18432, 89216, 430336, 2078720, 10035200, 48457728, 233967616, 1129709568, 5454692352, 26337640448, 127169265664, 614027755520, 2964787822592, 14315262836736

Offset: 0

Author

Zak Seidov, Jul 17 2003

Keywords

• nonn
• easy

Comments

From Johannes W. Meijer, Aug 01 2010: (Start)

The a(n) represent the number of n-move paths of a chess king on a 3 X 3 board that end or start in the central square m (m = 5).

Inverse binomial transform of A090390 (without the first leading 1).

(End)

From R. J. Mathar, Oct 12 2010: (Start)

The row n=3 of an array T(n,k) counting king walks on an n X n board starting on a square on the diagonal next to a corner:

1,8,32,168,784,3840,18432,89216,430336,2078720,10035200,48457728,233967616,

1,8,47,275,1610,9425,55175,323000,1890875,11069375,64801250,379353125,

1,8,47,318,2013,13140,84555,547722,3537081,22874400,147831399,955690326,

1,8,47,318,2134,14539,99267,679189,4650100,31848677,218164072,1494530576,

1,8,47,318,2134,14880,103920,733712,5187856,36796224,261164848,1855327584,

1,8,47,318,2134,14880,104885,748845,5382180,38880243,281743740,2045995632,

1,8,47,318,2134,14880,104885,751590,5430735,39556080,289541500,2127935700,

1,8,47,318,2134,14880,104885,751590,5438580,39710495,291852880,2156410817,

1,8,47,318,2134,14880,104885,751590,5438580,39733008,292340803,2164218694,

1,8,47,318,2134,14880,104885,751590,5438580,39733008,292405638,2165752797, (End)

Links

• Mike Oakes, KingMovesForPrimes.
• Zak Seidov, KingMovesForPrimes.
• Zak Seidov et al., New puzzle? King moves for primes, digest of 28 messages in primenumbers group, Jul 13 - Jul 23, 2003. [Cached copy]
• Sleephound, KingMovesForPrimes.
• Index entries for linear recurrences with constant coefficients, signature (2, 12, 8).

Crossrefs

Cf. A086346, A086347.

Cf. A179597.

Programs

Maple

with(LinearAlgebra): nmax:=19; m:=5; A[5]:= [1,1,1,1,0,1,1,1,1]: A:=Matrix([[0,1,0,1,1,0,0,0,0],[1,0,1,1,1,1,0,0,0],[0,1,0,0,1,1,0,0,0],[1,1,0,0,1,0,1,1,0],A[5],[0,1,1,0,1,0,0,1,1],[0,0,0,1,1,0,0,1,0],[0,0,0,1,1,1,1,0,1],[0,0,0,0,1,1,0,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); # Johannes W. Meijer, Aug 01 2010

Mathematica

Table[(1/16)(4(-2)^(n+1)+(2+Sqrt[8])^(n+2)+(2-Sqrt[8])^(n+2)), {n, 0, 19}]

Formula

a(n) = (1/16)(4(-2)^(n+1) + (2+sqrt(8))^(n+2) + (2-sqrt(8))^(n+2)).

From Johannes W. Meijer, Aug 01 2010: (Start)

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

a(n) = 2*a(n-1) + 12*a(n-2) + 8*a(n-3) with a(0)=1, a(1)=8 and a(2)=32.

Lim_{k->infinity} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2). (End)

2*a(n) = 3*A057087(n) + 2*A057087(n-1) - (-2)^n. - R. J. Mathar, May 21 2019

Extensions

Offset changed and edited by Johannes W. Meijer, Jul 15 2010