A378902 a(n) is the number of paths of a chess king on square a1 to reach a position outside an 8 X 8 chessboard after n steps.

5, 6, 39, 156, 922, 5060, 31165, 196605, 1301490, 8844147, 61504902, 434181564, 3098427480, 22270496859, 160854381441, 1165549608378, 8463549600999, 61543303627788, 447926999731974, 3262077526200660, 23765765966223849, 173189189528260281, 1262299887268848702, 9201356346994752339

Offset

1,1

Comments

The king visits the Moore neighborhood, and the 8 possible moves relative to its current position are E, NE, N, NW, W, SW, S, and SE.

Links

Ruediger Jehn, Table of n, a(n) for n = 1..100

Example

a(1) = 5: only the 3 moves E, NE, and N end on target squares on the chessboard, the other 5 leave the board.
a(2) = 6: the 6 combinations of step directions leaving the board in exactly 2 moves are [E,SW], [E,S], [E,SE], [N,NE], [N,E], and [N,SE].

Mathematica

LinearRecurrence[{9, 9, -159, -108, 810, 900, -513, -729, -27, 81}, {5, 6, 39, 156, 922, 5060, 31165, 196605, 1301490, 8844147}, 25] (* Hugo Pfoertner, May 17 2025 *)

Prog

(Python)
from numpy import ones, array
P = ones((11, 11), dtype=int) # transition matrix, a1=0, b1=1, c1=2, d1=3, b2=4, c2=5, d2=6, c3=7, d3=8, d4=9, off board=10
P = [[0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 5, ],
     [1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 3, ],
     [0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 3, ],
     [0, 0, 1, 1, 0, 1, 2, 0, 0, 0, 3, ],
     [1, 2, 2, 0, 0, 2, 0, 1, 0, 0, 0, ],
     [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, ],
     [0, 0, 1, 2, 0, 1, 1, 1, 2, 0, 0, ],
     [0, 0, 0, 0, 1, 2, 2, 0, 2, 1, 0, ],
     [0, 0, 0, 0, 0, 1, 2, 1, 2, 2, 0, ],
     [0, 0, 0, 0, 0, 0, 0, 1, 4, 3, 0, ],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ]]
pop = array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], dtype=object) # king starts in a1
cycle = 100  # simulation period
for i in range(cycle):
    pop = pop @ P
    print(i+1, pop[10]) # Ruediger Jehn, May 17 2025

Crossrefs

Cf. A140518, A376609, A376610, A377018.

Sequence in context: A386634 A349051 A137254 * A262308 A355137 A352641

Adjacent sequences: A378899 A378900 A378901 * A378903 A378904 A378905

Keyword

nonn,walk

Author

Hugo Pfoertner, Dec 10 2024

Extensions

a(16) and beyond from Ruediger Jehn, May 17 2025

Status

approved