login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Self-Avoiding Walks of a Rook

Self-Avoiding Walks of a Rook

Date: 	  Sat, 7 Sep 1996 17:30:10 +0200
From: 	  Philippe Flajolet 
To: 	  sfinch@.com
Subject:  Re: Self-Avoiding Walks of a Rook on a Chessboard

...

The generating function of W(n,k) for a fixed k is always 
going to be rational. The reason is that there is a finite-state
model that enables you to add a slice, and there are only a finite 
(though exponential in k) number of "gluing" combinations to do so.
This is a very general technique, usually known by physicists
as a transfer matrix method. Consequently, the generating function
of any sequence {W_{n,k}}_n is going to be rational with a
denominator whose degree grows very fast with k. On the positive 
side, any such generating function is in principle computable 
mechanically.

(This is of course what your formula for W(n,3) says...)

This method is very general. The rational character applies for
instance to dimer coverings of an (n*k) chessboard, a property
that I remember learning from Ron Read in the late 70's and certainly
well-known to many people (Temperley?). Similarly, nonattacking kings on
an (n*k) chessboard will lead A PRIORI to rational GF's. And, again for
similar reasons, the number of knight tours (Hamiltonian path in a
certain graph) on an (n*k) chessboard will have a rational GF;
this is one of the topics that Knuth discussed in his Paris lecture
last Spring. I believe that the knight tour problem is discussed
by Wilf, probably in the Electronic Journal Of Combinatorics.

The results obtained in this way are mechanical, but far from uniform 
as they are based on exhausting an a priori unstructured collection 
of "gluing" possibilities.

There is a huge quantitative jump if one wants to get results where
k varies with n (typically k=n), and much finer analysis is required,
and even often lacking. Problems become soon of the same type as
the general SAW problem. An exception is dimer coverings which
(if my memory serves me right, see Percus) is equivalent to
the 2-d Ising problem and has explicit solutions.

...

In this thread, it may be interesting to point to the works of 
Tony Guttmann (tonyg@maths.mu.OZ.AU) in Melbourne. Tony and his 
collaborators investigated various models that "interpolate" between
staircase walks and the pure model of SAWs,  taking into account
various parameters like perimeter, area, number of turns, etc.
This relates in turn to the study of "polygons" and "polyominoes".
The yearly FPSAC (Formal Power Series and Algebraic Combinatorics)
Conference has every year interesting work on this questions.
Some perimeter problems lead to rational or algebraic GF's,
area problems often lead to interesting and explicit q-analogues.

...

	Cheers,

	Philippe

Return to Self-Avoiding Walks of a Rook on a Chessboard.

Copyright © 1995-2001 by Steven Finch.
All rights reserved.

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:39 EDT 2024. Contains 371235 sequences. (Running on oeis4.)