A323562 Number of rooted self-avoiding king's walks on an infinite chessboard trapped after n moves.

8, 200, 2446, 21946, 169782, 1205428, 8119338, 52862872, 336465352, 2108185746

Offset

8,1

Comments

The first step is either (0,0)->(1,0) or (0,0)->(1,1). Rotated paths are not counted separately.

The average number of moves of a self-avoiding random walk of a king on an infinite chessboard to self-trapping is 209.71. The corresponding number of moves for paths with forbidden crossing (A323141) is 69.865.

a(n)=0 for n<8.

Links

Table of n, a(n) for n=8..17.

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

Example

a(8) = 8, because the following 8 walks of 8 moves of a king starting at S with a first move (0,0)->(1,0) visit all neighbors of the trapping location T. The starting point itself is also blocked. There are no such shortest walks with first move (0,0)->(1,1).
.
  o <-- o <-- o   o     o <-- o   o --> o --> o   o <-- o <-- o
  |           ^   ^ \ /       ^   ^           |   |           ^
  v           |   | / \       |   |           v   v           |
  o --> T     o   o     T     o   o     T     o   o     T     o
              ^               ^     \    \    |   |   /       ^
              |               |       \    \  v   v /         |
  S --> o --> o   S --> o --> o   S --> o     o   o     S --> o
.
  S --> o --> o   S --> o --> o   S --> o     o   o     S --> o
              |               |       /    /  ^   ^ \         |
              v               v     /    /    |   |   \       v
  o --> T     o   o     T     o   o     T     o   o     T     o
  ^           |   | \ /       |   |           ^   ^           |
  |           v   v / \       v   v           |   |           v
  o <-- o <-- o   o     o <-- o   o --> o --> o   o <-- o <-- o
- Hugo Pfoertner, Jul 23 2020

Crossrefs

Cf. A077482, A322831, A323141, A323560, A323561.

Sequence in context: A020329 A232518 A229265 * A034861 A221121 A264124

Adjacent sequences: A323559 A323560 A323561 * A323563 A323564 A323565

Keyword

nonn,walk,more

Author

Hugo Pfoertner, Jan 17 2019

Status

approved