OFFSET
1,1
COMMENTS
a(n)/4^n is the probability that the 1-step rook falls off the chess board at step n. The average number of steps it takes this piece to fall off the board is Sum_{n>0} n*a(n)/4^n = A376606(8)/A376607(8) = 4374/901 or approximately 4.855 steps.
Because of the mirror symmetry of the problem to the board diagonal, all terms are even.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (5,9,-69,21,225,-171,-162,108,32,-16).
FORMULA
a(n) == 0 (mod 2).
G.f.: 2*x*(1 - 4*x - 11*x^2 + 51*x^3 + 11*x^4 - 143*x^5 + 42*x^6 + 78*x^7 - 12*x^8 - 8*x^9)/((1 - 2*x)*(1 - 3*x^2 + x^3)*(1 - 3*x + x^3)*(1 - 12*x^2 - 8*x^3)). - Andrew Howroyd, Oct 16 2024
EXAMPLE
a(3) = 6. Starting on square a1 there are 6 paths to leave the chess board: up-up-left, up-down-left, up-down-down, right-right-down, right-left-down and right-left-left.
MATHEMATICA
LinearRecurrence[{5, 9, -69, 21, 225, -171, -162, 108, 32, -16}, {2, 2, 6, 12, 40, 100, 350, 982, 3542, 10738}, 30] (* Hugo Pfoertner, Oct 16 2024 *)
PROG
(PARI) Vec(2*(1 - 4*x - 11*x^2 + 51*x^3 + 11*x^4 - 143*x^5 + 42*x^6 + 78*x^7 - 12*x^8 - 8*x^9)/((1 - 2*x)*(1 - 3*x^2 + x^3)*(1 - 3*x + x^3)*(1 - 12*x^2 - 8*x^3)) + O(x^30)) \\ Andrew Howroyd, Oct 16 2024
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Ruediger Jehn, Oct 06 2024
STATUS
approved