%I #65 Jan 30 2024 01:59:43
%S 1,3,18,80,400,1904,9248,44544,215296,1039104,5018112,24227840,
%T 116985856,564850688,2727354368,13168803840,63584665600,307013812224,
%U 1482394042368,7157631156224,34560101318656,166870928850944,805724122775552,3890380202311680,18784417308737536,90699190027419648
%N On a 3 X 3 board, the number of n-move paths for a chess king ending in a given corner 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 a given corner square m (m = 1, 3, 7, 9). 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 king's graph, or we can sum the components of the row vector A^n[m,k], see the Maple program.
%C Inverse binomial transform of A079291 (without the leading 0).
%C (End)
%C From _R. J. Mathar_, Oct 12 2010: (Start)
%C The row n=3 of an array counting king walks on an n X n board with k steps, starting from a corner:
%C 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, ...;
%C 1, 3, 18, 80, 400, 1904, 9248, 44544, 215296, 1039104, 5018112, ...;
%C 1, 3, 18, 105, 615, 3600, 21075, 123375, 722250, 4228125, 24751875, ...;
%C 1, 3, 18, 105, 684, 4359, 28278, 182349, 1179792, 7622667, 49283802, ...;
%C 1, 3, 18, 105, 684, 4550, 30807, 209867, 1434279, 9815190, 67209723, ...;
%C 1, 3, 18, 105, 684, 4550, 31340, 218056, 1533712, 10829360, 76720288, ...;
%C 1, 3, 18, 105, 684, 4550, 31340, 219555, 1559835, 11177190, 80573373, ...;
%C 1, 3, 18, 105, 684, 4550, 31340, 219555, 1564080, 11259785, 81765550, ...;
%C 1, 3, 18, 105, 684, 4550, 31340, 219555, 1564080, 11271876, 82025163, ...;
%C 1, 3, 18, 105, 684, 4550, 31340, 219555, 1564080, 11271876, 82059768, ...;
%C 1, 3, 18, 105, 684, 4550, 31340, 219555, 1564080, 11271876, 82059768, ...;
%C The partial sums along the rows are documented in A123109 (king walks with between 1 and k steps). (End)
%D Gary Chartrand, Introductory Graph Theory, pp. 217-221, 1984. [From _Johannes W. Meijer_, Aug 01 2010]
%H G. C. Greubel, <a href="/A086346/b086346.txt">Table of n, a(n) for n = 0..1000</a>
%H Mike Oakes, <a href="http://groups.yahoo.com/group/primenumbers/message/12980">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 Zak Seidov, <a href="http://groups.yahoo.com/group/primenumbers/message/12947">KingMovesForPrimes</a>.
%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/32)*(2*(-2)^(n+2) + (2+sqrt(8))^(n+2) + (2-sqrt(8))^(n+2)).
%F From _R. J. Mathar_, Jul 22 2010: (Start)
%F a(n) = 2*a(n-1) + 12*a(n-2) + 8*a(n-3).
%F G.f.: (1+x) / ( (1+2*x)*(1-4*x-4*x^2) ).
%F a(n) = (2*A057087(n-1) + 3*A057087(n) + (-2)^n)/4. (End)
%F Limit_{k->oo} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2). - _Johannes W. Meijer_, Aug 01 2010
%F a(n) = A110048(n) + A110048(n-1). - _R. J. Mathar_, Mar 08 2021
%F a(n) = 2^(n-3)*(A002203(n+2) + 2*(-1)^n). - _G. C. Greubel_, Aug 18 2022
%p with(LinearAlgebra):
%p nmax:=19; m:=1;
%p A[5]:= [1, 1, 1, 1, 0, 1, 1, 1, 1]:
%p 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]]):
%p 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/32)(2(-2)^(n+2)+(2+Sqrt[8])^(n+2)+(2-Sqrt[8])^(n+2)), {n, 0, 19}] // FullSimplify
%t LinearRecurrence[{2,12,8}, {1,3,18}, 31] (* _G. C. Greubel_, Aug 18 2022 *)
%o (Magma) [2^(n-3)*(Evaluate(DicksonFirst(n+2,-1), 2) +2*(-1)^n): n in [0..30]]; // _G. C. Greubel_, Aug 18 2022
%o (SageMath) [2^(n-3)*(lucas_number2(n+2,2,-1) +2*(-1)^n) for n in (0..30)] # _G. C. Greubel_, Aug 18 2022
%o (PARI) Vec((1+x)/((1+2*x)*(1-4*x-4*x^2))+O(x^30)) \\ _Joerg Arndt_, Jan 29 2024
%Y Cf. A086347, A086348, A086349.
%Y Cf. A179596. - _Johannes W. Meijer_, Aug 01 2010
%Y Cf. A002203, A057087, A079291, A084128, A110048, A123109.
%K nonn,easy
%O 0,2
%A _Zak Seidov_, Jul 17 2003
%E Offset changed and edited by _Johannes W. Meijer_, Jul 15 2010