A341269 Number of non-extendable self-avoiding walks in an n X n grid starting at the top left corner.

1, 2, 20, 548, 40440, 8442742, 5088482972, 8963926817126, 46591697187961736

Offset: 1

Author

Ryan Bresler, Feb 07 2021

Keywords

• nonn
• walk
• more

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.

Examples

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

Extensions

a(8)-a(9) from Andrew Howroyd, Feb 08 2021

a(6) corrected by Henry Bottomley, Oct 07 2021