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

%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