A003192 -id:A003192 - cp's OEIS frontend

A323131 Number of uncrossed rooted knight's paths of length n on an infinite board.

1, 7, 47, 303, 1921, 11963, 74130, 454484, 2779152, 16882278, 102384151, 618136584, 3727827148, 22408576099, 134595908277, 806452390868

Offset: 1

Hugo Pfoertner, Jan 05 2019

The direction of the first move is kept fixed.

The average number of steps of a random walk using such knight moves with forbidden crossing is 45 (compare to A322831).

			a(1) = 1: The fixed initial move.
a(2) = 7: Relative to the direction given by the initial move, there are 7 possible direction changes. The backward direction is illegal for the self-avoiding uncrossed path. Only for the right angle turn its mirror image would coincide with the turn in the opposite direction. Therefore this move would be eliminated in the unrooted walks, making a(2) > A323132(2) = 6.
a(3) = 47: 2 of all 7*7 = 49 continuation moves already lead to a crossing of the first path segment.
See illustrations at Pfoertner link.

Hugo Pfoertner, Illustrations of rooted uncrossed knight's paths of length <= 3, (2019).

Cf. A003192, A272773, A323132, A323133, A323134, A323559.

Erroneous (as pointed out by Bert Dobbelaere) a(8) and a(10) corrected by Hugo Pfoertner, Jan 18 2019

a(12)-a(16) from Bert Dobbelaere, Jan 18 2019

A323141 Number of self-trapped uncrossed king's paths on an infinite board after n steps, reduced for symmetry.

Original entry on oeis.org

0, 0, 0, 0, 2, 19, 150, 1043, 6843, 43192, 266529, 1619983, 9746883, 58220994, 345919915

Offset: 1

Hugo Pfoertner, Jan 05 2019

The average number of moves of a self-avoiding uncrossed random walk of a king on an infinite chessboard to self-trapping is 69.865+-0.008. - Hugo Pfoertner, Oct 22 2024

			a(5) = 2: There are 2 walks where the king is blocked after 5 steps, because for the diagonal moves it would have to cross its previous path.
.
  o       2       o       o       3        o
        /   \                   /   \
      /       \               /        \
    /           \           /            \
  3       5       1       4 - - - 5        2
  |     /       /                        /
  |   /       /                        /
  | /       /                        /
  4       S       o       S - - -  1       o

Hugo Pfoertner, Probability density for the number of moves to self-trapping, (2019).

Cf. A003192, A077482, A272773, A323140, A323562.

A323140 Number of uncrossed king's paths of length n, reduced for symmetry, A272773/8.

Original entry on oeis.org

1, 7, 45, 280, 1712, 10351, 62082, 370142, 2196701, 12988928, 76572159, 450277842, 2642226994, 15476427641, 90508059371

Offset: 1

Hugo Pfoertner, Jan 05 2019

For comments, programs, references see A272773.

Cf. A272773, A003192, A046661, A323141.

a(n) = A272773(n) / 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))

A323132 Number of uncrossed unrooted knight's paths of length n on an infinite board.

Original entry on oeis.org

1, 6, 25, 160, 966, 6018, 37079, 227357

Offset: 1

Hugo Pfoertner, Jan 05 2019

Paths which are equivalent under rotation, reflection or reversal are counted only once.

			See illustrations at Pfoertner link.

Hugo Pfoertner, Illustrations of unrooted uncrossed knight's paths of length <= 4, (2019).

Cf. A003192, A001334, A151541, A272773, A306178, A323131, A323133, A323134.

A323134 Number of polygons made of uncrossed knight's paths of length 2*n on an infinite board.

Original entry on oeis.org

0, 3, 13, 178, 3031, 64866

Offset: 1

Hugo Pfoertner, Jan 05 2019

			See Pfoertner link.

Hugo Pfoertner, Illustrations of uncrossed Knight's path polygons, (2019).

Cf. A003192, A157416, A258206, A266549, A284869, A316198.

A157416 Length of maximal uncrossed cycle of knight moves on n X n board.

Original entry on oeis.org

0, 0, 0, 4, 8, 12, 24, 32, 42, 54

Offset: 1

Don Knuth, Jun 24 2010

I had computed the values for n up to 8 long ago and reported them in a letter to the editor of the Journal of Recreational Mathematics 2 (1969), 155-157. The values for n=9 and n=10 are new, found using ZDDs.

For best known results see link to Alex Chernov's site. - Dmitry Kamenetsky, Mar 02 2021

			Lengths of longest uncrossed knight cycles on all sufficiently small rectangular boards m X n, with 3 <=m <= n:
......0...0...4...6...6...6...6..10
..........4...6...8..10..12..14..16
..............8..12..14..18..20..22
.................12..18..22..24..28
.....................24..26..32..36
.........................32..36..42
.............................42..50
.................................54

D. E. Knuth, Selected Papers on Fun and Games. CSLI, Stanford, CA, 2010. (CSLI Lecture Notes, vol. 192)

Alex Chernov, Uncrossed Knight's Tours.

Cf. A003192.

a(1)=a(2)=a(3)=0 prepended by Max Alekseyev, Jul 17 2011

A323133 Number of symmetric uncrossed unrooted knight's paths of length n on an infinite board.

Original entry on oeis.org

1, 6, 7, 29, 46, 170, 299, 969

Offset: 1

Hugo Pfoertner, Jan 05 2019

A path is considered as symmetric if its "spine", i.e., the connection of the end points of the moves by straight lines, has mirror or point symmetry. The non-symmetric details of a single move are ignored.

			See Pfoertner link.

Hugo Pfoertner, Illustrations of symmetric uncrossed knight's paths of length <= 6, (2019).

Cf. A003192, A306176, A306178, A323131, A323132, A323134.

A323699 Number of uncrossed knight's walks as specified in A323700, counting isomorphisms only once.

Original entry on oeis.org

1, 8, 56, 404, 2563, 16516, 102280, 639532, 3899662

Offset: 4

Hugo Pfoertner, Jan 24 2019

First differs at a(7)=404 from A323700(7)=406, because there are two walks of length 7 trapped at both ends. If seen as unrooted walks, their path shapes become identical after path reversal and reflection.

			In algebraic chess notation, the two walks double counted in A323700(7) are
  N c4 d2 e4 c5 a4 b2 d1 c3 and N d4 c2 e3 d5 b4 a2 c1 b3.

Hugo Pfoertner, Illustrations of uncrossed knight's walks trapped after n moves, (2019).
Hugo Pfoertner, Probability density for the number of moves to self-trapping, (2019).

Cf. A003192, A323131, A323559, A323560, A323700.

A323700 Number of rooted uncrossed knight's walks on an infinite chessboard trapped after n moves with first move specified.

Original entry on oeis.org

1, 8, 56, 406, 2572, 16596, 102654, 642441, 3914084

Offset: 4

Hugo Pfoertner, Jan 24 2019

Trapping occurs if the walk cannot be continued without reusing an already visited field or creating an intersection of the path segments formed by straight lines connecting consecutively visited fields.

The shortest self-trapped walk has 4 moves, i.e., a(n)=0 for n < 4.

			a(4) = 1 because there is only one trapped walk of 4 moves, written in algebraic chess notation: (N) b1 d2 b3 a1 c2.
For longer walks see link to illustrations in A323699.

Cf. A003192, A323131, A323559, A323560, A323699.

cp's OEIS Frontend

A323131 Number of uncrossed rooted knight's paths of length n on an infinite board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A323141 Number of self-trapped uncrossed king's paths on an infinite board after n steps, reduced for symmetry.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A323140 Number of uncrossed king's paths of length n, reduced for symmetry, A272773/8.

Views

Author

Keywords

Comments

Crossrefs

Formula

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

A323132 Number of uncrossed unrooted knight's paths of length n on an infinite board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A323134 Number of polygons made of uncrossed knight's paths of length 2*n on an infinite board.

Views

Author

Keywords

Examples

Links

Crossrefs

A157416 Length of maximal uncrossed cycle of knight moves on n X n board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A323133 Number of symmetric uncrossed unrooted knight's paths of length n on an infinite board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A323699 Number of uncrossed knight's walks as specified in A323700, counting isomorphisms only once.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A323700 Number of rooted uncrossed knight's walks on an infinite chessboard trapped after n moves with first move specified.

Views

Author

Keywords