login
A377018
a(n) is the number of paths of a knight on square a1 to reach a position outside an 8 X 8 chessboard after n steps.
1
6, 4, 32, 108, 880, 4420, 29560, 167068, 1041440, 6128772, 37298680, 222571260, 1343492128, 8055277508, 48487848472, 291196932444, 1751154444320, 10522542700868, 63258161555448, 380185630909692, 2285299322957920, 13735692739737604, 82562224208247576, 496247752160871132
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
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