%I #35 Oct 07 2021 16:23:05
%S 1,2,20,548,40440,8442742,5088482972,8963926817126,46591697187961736
%N Number of non-extendable self-avoiding walks in an n X n grid starting at the top left corner.
%C 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.
%C 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.
%e Example of a self-avoiding walk on a 3 X 3 grid that visits every node (Hamiltonian path):
%e .
%e 1---2---3
%e |
%e 6---5---4
%e |
%e 7---8---9
%e .
%e Two examples of a self-avoiding walk on a 3 X 3 grid that do not visit every node:
%e .
%e 1---2 7
%e | |
%e X 3 6
%e | |
%e X 4---5
%e .
%e or
%e .
%e 1 8---7
%e | |
%e 2---3 6
%e | |
%e X 4---5
%e .
%Y Cf. A145157 (Hamiltonian case).
%K nonn,walk,more
%O 1,2
%A _Ryan Bresler_, Feb 07 2021
%E a(8)-a(9) from _Andrew Howroyd_, Feb 08 2021
%E a(6) corrected by _Henry Bottomley_, Oct 07 2021