Enumeration of three-dimensional convex polygons |
| |
Authors: | Mireille Bousquet-Mélou Anthony J Guttmann |
| |
Institution: | (1) LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France;(2) Department of Mathematics, The University of Melbourne, Parkville, 3052 Victoria, Australia |
| |
Abstract: | A self-avoiding polygon (SAP) on a graph is an elementary cycle. Counting SAPs on the hypercubic lattice ℤ
d
withd≥2, is a well-known unsolved problem, which is studied both for its combinatorial and probabilistic interest and its connections
with statistical mechanics. Of course, polygons on ℤ
d
are defined up to a translation, and the relevant statistic is their perimeter.
A SAP on ℤ
d
is said to beconvex if its perimeter is “minimal”, that is, is exactly twice the sum of the side lengths of the smallest hyper-rectangle containing
it. In 1984, Delest and Viennot enumerated convex SAPs on the square lattice 6], but no result was available in a higher
dimension.
We present an elementar approach to enumerate convex SAPs in any dimension. We first obtain a new proof of Delest and Viennot's
result, which explains combinatorially the form of the generating function. We then compute the generating function for convex
SAPs on the cubic lattice. In a dimension larger than 3, the details of the calculations become very cumbersome. However,
our method suggests that the generating function for convex SAPs on ℤ
d
is always a quotient ofdifferentiably finite power series. |
| |
Keywords: | 05A15 |
本文献已被 SpringerLink 等数据库收录! |
|