A086346 On a 3 X 3 board, the number of n-move paths for a chess king ending in a given corner square.

1, 3, 18, 80, 400, 1904, 9248, 44544, 215296, 1039104, 5018112, 24227840, 116985856, 564850688, 2727354368, 13168803840, 63584665600, 307013812224, 1482394042368, 7157631156224, 34560101318656, 166870928850944, 805724122775552, 3890380202311680, 18784417308737536, 90699190027419648

Offset

0,2

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

Inverse binomial transform of A079291 (without the leading 0).

(End)

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

The row n=3 of an array counting king walks on an n X n board with k steps, starting from a corner:

1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, ...;

1, 3, 18, 80, 400, 1904, 9248, 44544, 215296, 1039104, 5018112, ...;

1, 3, 18, 105, 615, 3600, 21075, 123375, 722250, 4228125, 24751875, ...;

1, 3, 18, 105, 684, 4359, 28278, 182349, 1179792, 7622667, 49283802, ...;

1, 3, 18, 105, 684, 4550, 30807, 209867, 1434279, 9815190, 67209723, ...;

1, 3, 18, 105, 684, 4550, 31340, 218056, 1533712, 10829360, 76720288, ...;

1, 3, 18, 105, 684, 4550, 31340, 219555, 1559835, 11177190, 80573373, ...;

1, 3, 18, 105, 684, 4550, 31340, 219555, 1564080, 11259785, 81765550, ...;

1, 3, 18, 105, 684, 4550, 31340, 219555, 1564080, 11271876, 82025163, ...;

1, 3, 18, 105, 684, 4550, 31340, 219555, 1564080, 11271876, 82059768, ...;

1, 3, 18, 105, 684, 4550, 31340, 219555, 1564080, 11271876, 82059768, ...;

The partial sums along the rows are documented in A123109 (king walks with between 1 and k steps). (End)

References

Gary Chartrand, Introductory Graph Theory, pp. 217-221, 1984. [From Johannes W. Meijer, Aug 01 2010]

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Mike Oakes, 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]

Zak Seidov, KingMovesForPrimes.

Sleephound, KingMovesForPrimes.

Index entries for linear recurrences with constant coefficients, signature (2,12,8).

Formula

a(n) = (1/32)*(2*(-2)^(n+2) + (2+sqrt(8))^(n+2) + (2-sqrt(8))^(n+2)).

From R. J. Mathar, Jul 22 2010: (Start)

a(n) = 2*a(n-1) + 12*a(n-2) + 8*a(n-3).

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

a(n) = (2*A057087(n-1) + 3*A057087(n) + (-2)^n)/4. (End)

Limit_{k->oo} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2). - Johannes W. Meijer, Aug 01 2010

a(n) = A110048(n) + A110048(n-1). - R. J. Mathar, Mar 08 2021

a(n) = 2^(n-3)*(A002203(n+2) + 2*(-1)^n). - G. C. Greubel, Aug 18 2022

Maple

with(LinearAlgebra):
nmax:=19; m:=1;
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/32)(2(-2)^(n+2)+(2+Sqrt[8])^(n+2)+(2-Sqrt[8])^(n+2)), {n, 0, 19}] // FullSimplify
LinearRecurrence[{2, 12, 8}, {1, 3, 18}, 31] (* G. C. Greubel, Aug 18 2022 *)

Prog

(Magma) [2^(n-3)*(Evaluate(DicksonFirst(n+2, -1), 2) +2*(-1)^n): n in [0..30]]; // G. C. Greubel, Aug 18 2022
(SageMath) [2^(n-3)*(lucas_number2(n+2, 2, -1) +2*(-1)^n) for n in (0..30)] # G. C. Greubel, Aug 18 2022
(PARI) Vec((1+x)/((1+2*x)*(1-4*x-4*x^2))+O(x^30)) \\ Joerg Arndt, Jan 29 2024

Crossrefs

Cf. A086347, A086348, A086349.

Cf. A179596. - Johannes W. Meijer, Aug 01 2010

Cf. A002203, A057087, A079291, A084128, A110048, A123109.

Sequence in context: A308853 A309257 A135371 * A337193 A036290 A078904

Adjacent sequences: A086343 A086344 A086345 * A086347 A086348 A086349

Keyword

nonn,easy

Author

Zak Seidov, Jul 17 2003

Extensions

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

Status

approved