OFFSET
1,1
COMMENTS
a(n)/8^n is the probability that the knight falls off the chess board at step n. The average number of steps it takes the knight to fall off the board is Sum_{n>0} n*a(n)/8^n = A376736(8)/A376737(8) = 101338/51901 or approximately 1.953 steps.
Because of the mirror symmetry of the problem to the board diagonal, all terms are even.
LINKS
Ruediger Jehn, Table of n, a(n) for n = 1..30
Index entries for linear recurrences with constant coefficients, signature (3,27,-29,-162,42,276,16,-96).
FORMULA
G.f.: 2*x*(3 - 7*x - 71*x^2 + 39*x^3 + 390*x^4 + 94*x^5 - 484*x^6 - 240*x^7)/(1 - 3*x - 27*x^2 + 29*x^3 + 162*x^4 - 42*x^5 - 276*x^6 - 16*x^7 + 96*x^8). - Andrew Howroyd, Oct 16 2024
EXAMPLE
a(2) = 4. Starting on square a1 there are 4 paths for a knight to leave the chess board in two steps: b3-z2, b3-z4, c2-b0 and c2-d0 (z being the file left of the a-file).
MATHEMATICA
LinearRecurrence[{3, 27, -29, -162, 42, 276, 16, -96}, {6, 4, 32, 108, 880, 4420, 29560, 167068}, 24] (* Hugo Pfoertner, Oct 16 2024 *)
PROG
(PARI) Vec(2*(3 - 7*x - 71*x^2 + 39*x^3 + 390*x^4 + 94*x^5 - 484*x^6 - 240*x^7)/(1 - 3*x - 27*x^2 + 29*x^3 + 162*x^4 - 42*x^5 - 276*x^6 - 16*x^7 + 96*x^8) + O(x^30)) \\ Andrew Howroyd, Oct 16 2024
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ruediger Jehn, Oct 13 2024
STATUS
approved