|
Self-Avoiding Walks of a Rook on a Chessboard
Suggested by Andreas Gammel
How many self-avoiding walks W(m,n) can a rook take from one corner to the
opposite corner on an m-by-n chessboard? What can be said about the
asymptotic behavior of W(m,n) as m and n approach infinity?
For small values of m and n, the first question has received quite a bit of
attention [1-5]. Clearly W(2,2)=2 and W(3,2)=4. In the picture below we
verify that W(3,3)=12.
The values in the following table were computed
independently by David Blume [1], Heiner Marxen, Jim Gillogly, Dave
Dodson [2], Andreas Gammel [3], Christoph Dürr [4]
and certainly many others.
m\n |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
2 |
2 |
3 |
4 |
12 |
4 |
8 |
38 |
184 |
5 |
16 |
125 |
976 |
8512 |
6 |
32 |
414 |
5382 |
79384 |
1262816 |
7 |
64 |
1369 |
29739 |
752061 |
20562673 |
575780564 |
8 |
128 |
4522 |
163496 |
7110272 |
336067810 |
16230458696 |
789360053252 |
9 |
256 |
14934 |
896476 |
67005561 |
5493330332 |
459133264944 |
38603590450777 |
3266598486981642 |
10 |
512 |
49322 |
4913258 |
630588698 |
89803472792 |
11 |
1024 |
162899 |
26932712 |
12 |
2048 |
538020 |
147657866 |
13 |
4096 |
1776961 |
14 |
8192 |
5868904 |
John Van Rosendale (1981) is credited in [5] with computing W(n,n) up to
n=11 and Donald Knuth (1995) with W(12,12). Heiner Marxen recently
reported the values of W(n,n) up to n=15 - see the Postscript below.
m=n |
W(n,n) |
1 |
1 |
2 |
2 |
3 |
12 |
4 |
184 |
5 |
8512 |
6 |
1262816 |
7 |
575780564 |
8 |
789360053252 |
9 |
3266598486981642 |
10 |
41044208702632496804 |
11 |
1568758030464750013214100 |
12 |
182413291514248049241470885236 |
13 |
64528039343270018963357185158482118 |
14 |
69450664761521361664274701548907358996488 |
15 |
227449714676812739631826459327989863387613323440 |
It is easy to check that for all
. Several expressions for W(m,3)
were found by H. L. Abbott & D. Hanson [7,8], including a recursive formula:
a generating function-type formula:
and an exact algebraic formula (where i denotes the imaginary unit):
which is well-approximated for large m by:
As an extension, Abbott & Hanson proved that, for each fixed n,
exists and provided the following bounds for n=4 and n=5:
where c and C are unspecified constants. They additionally proved that
exists and gave the following estimate:
The upper bound here can be improved [8]. Precise estimates of the above
limiting values remain as difficult unsolved problems, as far as I know.
If one restricts attention to staircase-like walks, i.e, self-avoiding
walks of minimal length from one corner to the opposite corner, then
enumeration becomes easy [6,9-11]. The number of such walks is
(by definition of binomial coefficients)
We point out that this is what is meant by the phrase lattice paths
in much of the combinatorial and statistical literature. Among many
related results: if m=n, then the number of such paths which do not
cross the main diagonal line y=x (except at the starting and ending corners)
is
i.e., twice the (n-1)th Catalan number.
A generalization of this fact is called Chung-Feller theorem, which is
related to the solution of the classical Bertrand-André ballot
problem.
The enumeration problems discussed above are special cases of the problem
of counting self-avoiding walks from two fixed vertices u and v (possibly
u=v) on a graph G. In the above, G is a finite square lattice. One could
also take, for example, G to be a finite triangular or hexagonal lattice
and obtain completely different results. As another example, one could
take G to be a finite cubic lattice in 3-dimensional space.
Relevant essays include:
- Self-avoiding-walk connective constants
(related enumeration problems for which one typically fixes the number of time
steps, not the final destination)
- Pólya's random walk constants
(within an infinite cubic lattice, what is the probability that a random
walk returns to its origin?)
- Hard square entropy constant
(what is the number of configurations of non-attacking Princes on an n-by-n chessboard,
where a "Prince" attacks the four adjacent, non-diagonal places?)
Postscript
Philippe Flajolet has kindly visited and here is an e-message he sent.
One has the impression of a massive theory, of which the above is only a
special detail, that is inexorably coming together.
A recent e-message from Heiner Marxen gives a much larger table
of W(m,n) values, for which I am grateful. Marxen also points out a web
page, The rook path problem,
by Frans Faase, which provides recursive formulas for W(m,4) and W(m,5).
Faase reports that he found the formulas for W(m,4) and W(m,5) by
a program which implements the Abbott-Hanson matrix method mentioned
above. Rook paths are related to Hamilton paths in a
graph (a Hamilton path has to visit all
vertices of the graph, so not all rook paths are Hamilton).
An overview of this work is found in Faase's web page
Counting Hamilton cycles in product graphs, and in his paper [12].
Anthony Guttmann has also visited, points out a physics literature
on this problem (including [13]), and promises to submit a list
of recent papers soon.
References
- The rec.puzzles newsgroup FAQ, and the Utrecht University Puzzles Archive.
- D. Radcliffe, personal communication.
- A. Gammel, personal communication.
- C. Dürr, Deau Mariages et aucun Enterrement,
Laboratoire de Recherche en Informatique report (1994).
- N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, Entry A007764.
- E. W. Weisstein, Staircase Walk (MathWorld).
- N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, Entry A006192.
- H. L. Abbott and D. Hanson, A lattice path problem, Ars Combinatoria
6 (1978) 163-178;
MR 80m:05009.
- S. G. Mohanty, Lattice Path Counting and Applications, Academic
Press, 1979;
MR 81f:60020.
- T. V. Narayana, Lattice Path Combinatorics with Statistical
Applications, Univ. of Toronto Press, 1979;
MR 81f:60019.
- N. Ya. Vilenkin, Combinatorics,
Academic Press, 1971;
MR 46 #5133.
- F. J. Faase, On the number of specific spanning subgraphs of the
graphs , Ars Combinatoria
49 (1998) 129-154;
MR 99g:05104.
- S. G. Whittington and A. J. Guttmann, Self-avoiding walks which cross
a square, J. Phys. A 23 (1990) 5601-5609;
MR 92e:82038.
- R. M. Dickau, All self-avoiding paths through a 2-D grid.
Copyright © 1995-2001 by Steven Finch.
All rights reserved.
|