The Abstract

	Annals of Combinatorics 1 (1997) 27-53 Enumeration of Three-dimensional Convex Polygons Mireille Bousquet-Mélou and Anthony J. Guttmann LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France bousquet@labri.u-bordeaux.fr Department of Mathematics, The University of Melbourne, Parkville, Victoria 3052, Australia tonyg@maths.mu.oz.au Received July 12, 1996 AMS Subject Classification: 05A15 Abstract. A self-avoiding polygon (SAP) on a graph is an elementary cycle. Counting SAPs on the hypercubic lattice Z^d, with d ≥ 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 Z^d are defined up to a translation, and the relevant statistic is their perimeter. A SAP on Z^d is said to be convex 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 elementary 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 Z^d is always a quotient of differentiably finite power series. Keywords: self-avoiding polygons, convexity, differentiably finite series References 1. R.J. Baxter, Partition function of the three-dimensional Zamolodchikov model, Phys. Rev. Lett. 53 (1984) 1795–1798. 2. M. Bousquet-Mèlou, Codage des polyominos convexes et èquations pour l'ènumèration suivant làire, Discrete Appl. Math. 48 (1994) 21–43. 3. M. Bousquet-Mèlou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996) 1–25. 4. R. Brak, A.J. Guttmann, and I.G. Enting, Exact solution of the row-convex polygon perimeter generating function, J. Phys. A: Math. Gen. 23 (1990) 2319–2326. 5. M.-P. Delest, Generating functions for column-convex polyominoes, J. Combin. Theory Ser. A 48 (1988) 12–31. 6. M.-P. Delest and G. Viennot, Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci. 34 (1984) 169–206. 7. J. Denef and L. Lipschitz, Power series solution of algebraic differential equations, Math. Ann. 267 (1984) 213–238. 8. D. Dhar, Exact solution of a directed-site animals-enumeration problem in three dimensions, Phys. Rev. Lett. 51 (1983) 853–856. 9. J.W. Essam, Exact enumeration of parallel walks on directed lattices, J. Phys. A: Math. Gen. 26 (1993) L863–L869. 10. I.G. Enting, A.J. Guttmann, L.B. Richmond, and N.C. Wormald, Enumeration of almost-convex polygons on the square lattice, Random Structures and Algorithms 3 (1992) 445–461. 11. J.-M. Fèdou, Sommes de carrès de multinomiaux, preprint, 1993. 12. J.-M. Fèdou and N. Rouillon, Polyominos et q-analogues de fonctions de Bessel, une preuve combinatoire, In: Proc. 7th Conf. Formal Power Series and Algebraic Combinatorics, Marne-la-Vallèe, France, B. Leclerc and J.-Y. Thibon, Eds., June 1995. 13. S. Feretic, A new way of counting the column-convex polyominoes by perimeter, In: Proc. 7th Conf. Formal Power Series and Algebraic Combinatorics, Marne-la-Vallèe, France, B. Leclerc and J.-Y. Thibon, Eds., June 1995. 14. P. Flajolet, Pòlya festoons, Research Report INRIA 1991, Rocquencourt, France, 1991. 15. P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990) 216–240. 16. I. Gessel, A noncommutative generalization and $q$-analog of the Lagrange inversion formula, Trans. Amer. Math. Soc. 257 (1980) 455–481. 17. I. Gessel, On the number of convex polyominoes, preprint, 1990. 18. A.J. Guttmann and T. Prellberg, Staircase polygons, elliptic integrals, Heun functions and lattice Green functions, Phys. Rev. E 47 (1993) R2233–R2236. 19. J.M. Hammersley, On the rate of convergence to the connective constant of the hypercubical lattice, Quart. J. Math. Oxford Ser. 2 12 (1961) 250–256. 20. J.M. Hammersley and D.J.A. Welsh, Further results on the rate of convergence to the connective constant of the hypercubic lattice, Quart. J. Math. Oxford Ser. 2 13 (1962) 108–110. 21. P.~Henrici, Applied and Computational Complex Analysis, Vol. II, John Wiley & Sons, New-York, 1977. 22. B.D. Hughes, Random Walks and Random Environments. Vol. I, Random walks, Clarendon Press, Oxford, 1995. 23. G.S. Joyce, On the cubic lattice Green functions, Proc. Roy. Soc. London Ser. A 445 (1994) 463–477. 24. D. Kim, The number of convex polyominoes with given perimeter, Discrete Math. 70 (1988) 47–51. 25. K.Y. Lin and S.J. Chang, Rigorous results for the number of convex polygons on the square and honeycomb lattices, J. Phys. A: Math. Gen. 21 (1988) 2635–2642. 26. L. Lipschitz, D-finite power series, J. Algebra 122 (1989) 353–373. 27. P.A. MacMahon, Combinatory Analysis, Vols. I and II, Cambridge University Press, Cambridge, pp. 1915–1916, reprinted 1960. 28. N. Madras and G. Slade, The Self-Avoiding Walk, Probability and its Applications, Birkhäuser, Boston, 1993. 29. G. Pölya, On the number of certain lattice polygons, J. Combin. Theory 6 (1969) 102–105. 30. B. Salvy and P. Zimmermann, GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software 20 (1994) 163–167. 31. R.P. Stanley, Differentiably finite power series, Europ. J. Combin. 1 (1980) 175–188. 32. N.C. Wormald, Private communication. Get the LaTex \| DVI \| PS file of this abstract. back

Annals of Combinatorics 1 (1997) 27-53

Enumeration of Three-dimensional Convex Polygons

Mireille Bousquet-Mélou and Anthony J. Guttmann

LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France
bousquet@labri.u-bordeaux.fr

Department of Mathematics, The University of Melbourne, Parkville, Victoria 3052, Australia
tonyg@maths.mu.oz.au

Received July 12, 1996

AMS Subject Classification: 05A15

Abstract. A self-avoiding polygon (SAP) on a graph is an elementary cycle. Counting SAPs on the hypercubic lattice Z^d, with d ≥ 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 Z^d are defined up to a translation, and the relevant statistic is their perimeter.
A SAP on Z^d is said to be convex 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 elementary 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 Z^d is always a quotient of differentiably finite power series.

Keywords: self-avoiding polygons, convexity, differentiably finite series

References

1. R.J. Baxter, Partition function of the three-dimensional Zamolodchikov model, Phys. Rev. Lett. 53 (1984) 1795–1798.

2. M. Bousquet-Mèlou, Codage des polyominos convexes et èquations pour l'ènumèration suivant làire, Discrete Appl. Math. 48 (1994) 21–43.

3. M. Bousquet-Mèlou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996) 1–25.

4. R. Brak, A.J. Guttmann, and I.G. Enting, Exact solution of the row-convex polygon perimeter generating function, J. Phys. A: Math. Gen. 23 (1990) 2319–2326.

5. M.-P. Delest, Generating functions for column-convex polyominoes, J. Combin. Theory Ser. A 48 (1988) 12–31.

6. M.-P. Delest and G. Viennot, Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci. 34 (1984) 169–206.

7. J. Denef and L. Lipschitz, Power series solution of algebraic differential equations, Math. Ann. 267 (1984) 213–238.

8. D. Dhar, Exact solution of a directed-site animals-enumeration problem in three dimensions, Phys. Rev. Lett. 51 (1983) 853–856.

9. J.W. Essam, Exact enumeration of parallel walks on directed lattices, J. Phys. A: Math. Gen. 26 (1993) L863–L869.

10. I.G. Enting, A.J. Guttmann, L.B. Richmond, and N.C. Wormald, Enumeration of almost-convex polygons on the square lattice, Random Structures and Algorithms 3 (1992) 445–461.

11. J.-M. Fèdou, Sommes de carrès de multinomiaux, preprint, 1993.

12. J.-M. Fèdou and N. Rouillon, Polyominos et q-analogues de fonctions de Bessel, une preuve combinatoire, In: Proc. 7th Conf. Formal Power Series and Algebraic Combinatorics, Marne-la-Vallèe, France, B. Leclerc and J.-Y. Thibon, Eds., June 1995.

13. S. Feretic, A new way of counting the column-convex polyominoes by perimeter, In: Proc. 7th Conf. Formal Power Series and Algebraic Combinatorics, Marne-la-Vallèe, France, B. Leclerc and J.-Y. Thibon, Eds., June 1995.

14. P. Flajolet, Pòlya festoons, Research Report INRIA 1991, Rocquencourt, France, 1991.

15. P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990) 216–240.

16. I. Gessel, A noncommutative generalization and $q$-analog of the Lagrange inversion formula, Trans. Amer. Math. Soc. 257 (1980) 455–481.

17. I. Gessel, On the number of convex polyominoes, preprint, 1990.

18. A.J. Guttmann and T. Prellberg, Staircase polygons, elliptic integrals, Heun functions and lattice Green functions, Phys. Rev. E 47 (1993) R2233–R2236.

19. J.M. Hammersley, On the rate of convergence to the connective constant of the hypercubical lattice, Quart. J. Math. Oxford Ser. 2 12 (1961) 250–256.

20. J.M. Hammersley and D.J.A. Welsh, Further results on the rate of convergence to the connective constant of the hypercubic lattice, Quart. J. Math. Oxford Ser. 2 13 (1962) 108–110.

21. P.~Henrici, Applied and Computational Complex Analysis, Vol. II, John Wiley & Sons, New-York, 1977.

22. B.D. Hughes, Random Walks and Random Environments. Vol. I, Random walks, Clarendon Press, Oxford, 1995.

23. G.S. Joyce, On the cubic lattice Green functions, Proc. Roy. Soc. London Ser. A 445 (1994) 463–477.

24. D. Kim, The number of convex polyominoes with given perimeter, Discrete Math. 70 (1988) 47–51.

25. K.Y. Lin and S.J. Chang, Rigorous results for the number of convex polygons on the square and honeycomb lattices, J. Phys. A: Math. Gen. 21 (1988) 2635–2642.

26. L. Lipschitz, D-finite power series, J. Algebra 122 (1989) 353–373.

27. P.A. MacMahon, Combinatory Analysis, Vols. I and II, Cambridge University Press, Cambridge, pp. 1915–1916, reprinted 1960.

28. N. Madras and G. Slade, The Self-Avoiding Walk, Probability and its Applications, Birkhäuser, Boston, 1993.

29. G. Pölya, On the number of certain lattice polygons, J. Combin. Theory 6 (1969) 102–105.

30. B. Salvy and P. Zimmermann, GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software 20 (1994) 163–167.

31. R.P. Stanley, Differentiably finite power series, Europ. J. Combin. 1 (1980) 175–188.

32. N.C. Wormald, Private communication.

Get the LaTex | DVI | PS file of this abstract.

back