A376837 - OEIS

%I #19 Oct 16 2024 16:34:56

%S 2,2,6,12,40,100,350,982,3542,10738,39556,127272,475332,1602458,

%T 6030830,21056830,79514918,284645860,1075801928,3917238476,

%U 14799350958,54498514998,205721183302,763140403282,2878050335900,10726898070952,40421307665420,151112554663930,569043610134622,2131459901180670

%N 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.

%C 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.

%C Because of the mirror symmetry of the problem to the board diagonal, all terms are even.

%H Andrew Howroyd, <a href="/A376837/b376837.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (5,9,-69,21,225,-171,-162,108,32,-16).

%F a(n) == 0 (mod 2).

%F 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

%e 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.

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

%o (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

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

%K nonn,easy

%O 1,1

%A _Ruediger Jehn_, Oct 06 2024