login
A376837
a(n) is the number of paths to reach a position outside an 8 X 8 chessboard after n steps, starting in one of the corners, when performing a walk with unit steps on the square lattice.
2
2, 2, 6, 12, 40, 100, 350, 982, 3542, 10738, 39556, 127272, 475332, 1602458, 6030830, 21056830, 79514918, 284645860, 1075801928, 3917238476, 14799350958, 54498514998, 205721183302, 763140403282, 2878050335900, 10726898070952, 40421307665420, 151112554663930, 569043610134622, 2131459901180670
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
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
Cf. A376606, A376607, {A052899}+1 is the analog for the 4X4 chessboard.
Sequence in context: A103872 A216641 A191970 * A175516 A244656 A159322
KEYWORD
nonn,easy
AUTHOR
Ruediger Jehn, Oct 06 2024
STATUS
approved