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.

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

Author

Ruediger Jehn, Oct 13 2024

Keywords

• nonn
• easy

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.

Examples

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

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

Crossrefs

Cf. A376736, A376737, A376837, A378902 (for a king).

Programs

Mathematica

LinearRecurrence[{3, 27, -29, -162, 42, 276, 16, -96}, {6, 4, 32, 108, 880, 4420, 29560, 167068}, 24] (* Hugo Pfoertner, Oct 16 2024 *)

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

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

a(n) ~ 0.10036158347592796... * 6.01066058303935...^n. - Ruediger Jehn, Nov 06 2024