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, 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

Author

Ruediger Jehn, Oct 06 2024

Keywords

• nonn
• easy

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.

Examples

			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.
		

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).

Crossrefs

Cf. A376606, A376607, {A052899}+1 is the analog for the 4X4 chessboard.

Programs

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 *)

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

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