VOOZH about

URL: https://oeis.org/A341269

⇱ A341269 - OEIS

login
A341269
Number of non-extendable self-avoiding walks in an n X n grid starting at the top left corner.
1
1, 2, 20, 548, 40440, 8442742, 5088482972, 8963926817126, 46591697187961736
OFFSET
1,2
COMMENTS
A self-avoiding walk is non-extendable if it ends on a square which has all its neighbors already visited. Not all paths are Hamiltonian. See examples.
All paths that start by moving one square to the right are symmetrical with all paths that start by moving one square down. This symmetry results in a(n) divisible by 2 for n > 1.
EXAMPLE
Example of a self-avoiding walk on a 3 X 3 grid that visits every node (Hamiltonian path):
.
1---2---3
|
6---5---4
|
7---8---9
.
Two examples of a self-avoiding walk on a 3 X 3 grid that do not visit every node:
.
1---2 7
| |
X 3 6
| |
X 4---5
.
or
.
1 8---7
| |
2---3 6
| |
X 4---5
.
CROSSREFS
Cf. A145157 (Hamiltonian case).
Sequence in context: A009344 A009699 A101927 * A157317 A350794 A009399
KEYWORD
nonn,walk,more
AUTHOR
Ryan Bresler, Feb 07 2021
EXTENSIONS
a(8)-a(9) from Andrew Howroyd, Feb 08 2021
a(6) corrected by Henry Bottomley, Oct 07 2021
STATUS
approved