A376607 -id:A376607 - cp's OEIS frontend

A376606 a(n) is the numerator of the expected number of moves to reach a position outside an nXn chessboard, starting in one of the corners, when performing a random walk with unit steps on the square lattice.

1, 2, 11, 10, 99, 122, 619, 4374, 187389, 482698, 11031203, 33386106, 32723853563, 139832066, 150236161755, 633573154269934, 5755694771977, 189378719187729770, 509943025510535499, 6031948951257694364778, 1044408374351599765540157091, 27891966006517951087819226666

Offset: 1

Ruediger Jehn and Hugo Pfoertner, Oct 03 2024

The moves are that of chess rook with moves of unit length or of a chess king restricted to the Von Neumann neighborhood (see A272763). The piece does not pay attention to its position and will fall off the board if it makes a move beyond the edge of the board.

			1, 2, 11/4, 10/3, 99/26, 122/29, 619/136, 4374/901, 187389/36562, 482698/89893, ...
Approximately 1, 2, 2.75, 3.333, 3.808, 4.207, 4.551, 4.855, 5.125, 5.370, 5.593, ...

Hugo Pfoertner, Table of n, a(n) for n = 1..45
Hugo Pfoertner, Plot of A376606(n)/A376607(n) vs n, using Plot 2.

A376607 are the corresponding denominators.
A376609 and A376610 are similar for a chess king visiting the Moore neighborhood.
A376736 and A376737 are similar for a chess knight.
Cf. A001263, A007764, A272763.

droprob(n,moves=[[1,0],[0,1],[0,-1],[-1,0]], nmoves=4) = {my(np=n^2+1, M=matrix(np), P=1/nmoves); for(t=1, nmoves, for( i=1, n, my(ti=i+moves[t][1]); for(j=1,n,my(tj=j+moves[t][2]); my(m=(i-1)*n+j); if(ti<1 || ti>n || tj<1 || tj>n, M[m,np]+=P, my(mt=(ti-1)*n+tj); M[m,mt]+=P)))); vecsum((1/(matid(np)-M))[,1])};
a376606(n) = numerator(droprob(n))

A376609 a(n) is the numerator of the expected number of random moves of a chess king to reach a position outside an nXn chessboard, starting in one of the corners.

Original entry on oeis.org

1, 8, 72, 46, 23747, 94968, 12161644, 158536576, 165181795263, 1779861954248, 60921563004721184, 136512657826472304, 38548316743830620183051, 581371653539561314, 2630585854108441990301102856, 120104329127347395409698056, 5092493809189909792181005355935991197, 6666722670813237580783418910187983288

Offset: 1

Hugo Pfoertner, Oct 03 2024

The king visits the Moore neighborhood (see A272763). The piece does not pay attention to its position and will fall off the board if it makes a move beyond the edge of the board.

			1, 8/5, 72/35, 46/19, 23747/8723, 94968/31879, 12161644/3797647, 158536576/46627015, 165181795263/46174521031, ...
Approximately 1, 1.6, 2.057, 2.421, 2.722, 2.979, 3.202, 3.400, 3.577, 3.738, ...

Hugo Pfoertner, Table of n, a(n) for n = 1..45
Hugo Pfoertner, Plot of A376609(n)/A376610(n) vs n, using Plot 2.
Hugo Pfoertner, Results of a simulation of 10^9 walks on the 8X8 board.

A376610 are the corresponding denominators.
A376606 and A376607 are similar for a rook walk with unit steps.
A376736 and A376737 are similar for a chess knight.
Cf. A140518, A272763, A323140, A323561, A323562.

\\ Uses function droprob from A376606
kingmoves = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [-1, 1], [1, -1], [1, 1]];
a376609(n) = numerator(droprob(n,kingmoves,8))

A376736 a(n) is the numerator of the expected number of random moves of a chess knight to reach a position outside an nXn chessboard, starting in one of the corners.

Original entry on oeis.org

1, 1, 4, 62, 269, 1766, 395497, 101338, 44125237, 227721959, 3361699348115, 483866477194862, 277887411827604127, 790848403160840410, 2785714552717079970073201, 89715505143567836216964174, 2034961072108249587083318018747, 457177774768288408431166142758841, 1085703228381446052419019696184520372520

Offset: 1

Hugo Pfoertner, Oct 03 2024

The piece does not pay attention to its position and will fall off the board if it makes a move beyond the edge of the board.

			1, 1, 4/3, 62/43, 269/167, 1766/1017, 395497/213488, 101338/51901, 44125237/21578387, 227721959/106983448, ...
Approximately 1, 1, 1.333, 1.442, 1.611, 1.736, 1.853, 1.953, 2.045, 2.129, 2.206, ...

Hugo Pfoertner, Table of n, a(n) for n = 1..45
Hugo Pfoertner, Plot of A376736(n)/A376737(n) vs n, using Plot 2.
Hugo Pfoertner, Results of a simulation of 10^9 walks on the 8X8 board.

A376737 are the corresponding denominators.
A376606 and A376607 are similar for a rook walk with unit steps.
A376609 and A376610 are similar for a chess king.
Cf. A003192, A212715, A323131, A323132, A323559, A323560.

\\ Uses function droprob from A376606
knightmoves = [[2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2], [2, -1]];
a376736(n) = numerator(droprob(n, knightmoves, 8))

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.

Original entry on oeis.org

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

Ruediger Jehn, Oct 06 2024

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.

			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.

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

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

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

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

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

cp's OEIS Frontend

A376606 a(n) is the numerator of the expected number of moves to reach a position outside an nXn chessboard, starting in one of the corners, when performing a random walk with unit steps on the square lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A376609 a(n) is the numerator of the expected number of random moves of a chess king to reach a position outside an nXn chessboard, starting in one of the corners.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A376736 a(n) is the numerator of the expected number of random moves of a chess knight to reach a position outside an nXn chessboard, starting in one of the corners.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula