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

%I #30 Jul 02 2023 18:09:09

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

%T 233967616,1129709568,5454692352,26337640448,127169265664,

%U 614027755520,2964787822592,14315262836736

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

%C From _Johannes W. Meijer_, Aug 01 2010: (Start)

%C 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).

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

%C (End)

%C From _R. J. Mathar_, Oct 12 2010: (Start)

%C 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:

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

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

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

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

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

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

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

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

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

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

%H Mike Oakes, <a href="http://groups.yahoo.com/group/primenumbers/message/12980">KingMovesForPrimes</a>.

%H Zak Seidov, <a href="http://groups.yahoo.com/group/primenumbers/message/12947">KingMovesForPrimes</a>.

%H Zak Seidov et al., <a href="/A086346/a086346.txt">New puzzle? King moves for primes</a>, digest of 28 messages in primenumbers group, Jul 13 - Jul 23, 2003. [Cached copy]

%H Sleephound, <a href="http://groups.yahoo.com/group/primenumbers/message/12976">KingMovesForPrimes</a>.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2, 12, 8).

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

%F From _Johannes W. Meijer_, Aug 01 2010: (Start)

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

%F 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.

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

%F 2*a(n) = 3*A057087(n) + 2*A057087(n-1) - (-2)^n. - _R. J. Mathar_, May 21 2019

%p 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

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

%Y Cf. A086346, A086347.

%Y Cf. A179597.

%K nonn,easy

%O 0,2

%A _Zak Seidov_, Jul 17 2003

%E Offset changed and edited by _Johannes W. Meijer_, Jul 15 2010