Hamiltonian cycles on square grids.

[Max Alekseyev]

If I understand correctly, the only isomorphisms of the square grid
are those obtained by rotations and reflections (thus, there are just
8 of them). Therefore, counting Hamiltonian cycles up to isomorphism
sounds as an easy task on counting of various symmetric Hamiltonian
cycles and application of Burnside's lemma.

Regards,
Max

On Thu, Jul 31, 2008 at 9:26 AM, Tanya Khovanova
<mathoflove-seqfan at yahoo.com> wrote:
> Hello Seqfans,
>
> Does anyone know the number of Hamiltonian cycles on a 2nx2n square
> grid of points up to isomorphism?
>
> I only found this sequence: A003763 Number of Hamiltonian cycles on 2n
> X 2n square grid of points.
> It starts: 1, 6, 1072, 4638576, ...
>
> If we take the cycles up to isomorphism it should start: 1, 2, ...
>
> Is there such a sequence on the OEIS? Does anyone know the next number?
>
> I am working on a blog entry where it would be nice to have a reference
> to this sequence.
>
> Best, Tanya Khovanova
>



jvp quoted by rm:


So, Richard Mathar, is it worth your submitting the matrix, read by
antidiagonals
A[k,n] = n-th value of k-th Witt transform of A000012


me:


k-th Witt transform? A new name for an old transform?

I take this was an off list conversation that came on list.

On 8/23/2002 there were messages on seqfan about calculation of Witt
vectors leading me to suggest the "Witt transform" as an aid in
calculating them defined as follows:


me on 8/23/2002:


For a sequence a[]

Let b[n] = SUM ( L(n/d, a[d]) ), d|n

where L(n, z) is the number of Lyndon words (aperiodic necklaces) with n
beads
of z colors
= 1/n SUM ( mu(n/d)*z^d ), d|n

[Note that z is not necessarily an integer, but n is a nonnegative integer.]

I call b[] the inverse Witt transform of a[] and a[] the Witt transform of
b[].


me (now):


This is implemented in
http://www.research.att.com/~njas/sequences/transforms_pari.txt
as trv_witt

though what you're calling the "k-th Witt transform" is a version of
what's implemented as the "Lyndon transform" in that same file.
To get this k-th Witt transform, input a matrix with column 1 equal to
the input sequence and all other terms 0 to the matrix version of the
Lyndon transform (trm_lyndon). The k-th column of the output is the
transform you described.

? mx=matrix(11,11,m,n,n==2)
%53 = 
[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

[0 1 0 0 0 0 0 0 0 0 0]

? trm_lyndon(mx)
%54 = 
[1 1 0 0 0 0 0 0 0 0 0]

[0 1 1 1 1 1 1 1 1 1 1]

[0 1 1 2 2 3 3 4 4 5 5]

[0 1 2 3 5 7 9 12 15 18 22]

[0 1 2 5 8 14 20 30 40 55 70]

[0 1 3 7 14 25 42 66 99 143 200]

[0 1 3 9 20 42 75 132 212 333 497]

[0 1 4 12 30 66 132 245 429 715 1144]

[0 1 4 15 40 99 212 429 800 1430 2424]

[0 1 5 18 55 143 333 715 1430 2700 4862]

[0 1 5 22 70 200 497 1144 2424 4862 9225]

(I would call it the Lyndon_k transform.)

Christian


rm:


The array A(r,n), the n-th term of the r-th Witt transform
of the all-1 sequence, r>=1, n>=0,

240   285   330 
969  1197  1463 
...