[seqfan] Re: Quick question about self-avoiding walks
Jon Wild
wild at music.mcgill.ca
Sat Dec 10 15:30:51 CET 2011
On Sat, 10 Dec 2011, Alonso Del Arte wrote:
> Does the OEIS have the sequence of the number of distinct self-avoiding
> walks possible on an n^2 lattice where every vertex is visited? Here is an
> example of what I'm talking about:
> http://oeis.org/wiki/File:Walks_on_8_by_8_SqLattice.png I would look it up
> myself but I don't know the proper word for it nor have I thought about how
> to calculate terms.
Look for Hamiltonian cycles on a square grid. They're only possible for
squares of even side. Sequence A003763 is the main version and it
references A120443, A140519 and A140521.
I looked for these once before and found the OEIS didn't have the version
of the sequence reduced for symmetry i.e. where rotations and reflections
are not counted as distinct. I have the first few terms if anyone wants to
submit the sequence:
2x2: 1 rook's tour
4x4: 2 rook's tours
6x6: 149 rooks tours
8x8: 580717 rook's tours
--Jon
More information about the SeqFan
mailing list