|
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.
|