Annals of Combinatorics 4 (2000) 269-284


Bijections for Directed Animals on Infinite Families of Lattices

S. Corteel, A. Denise, and D. Gouyou-Beauchamps

LRI, CNRS UMR 8623, Université Paris-Sud, 91405 Orsay Cedex, France
{corteel, denise, dgb}@lri.fr

Received December 8, 1998

AMS Subject Classification: 05A15

Abstract. Bousquet-Mélou and Conway in [1] found algebraic equations for the area generating function of directed animals on an infinite family of regular, non-planar, two-dimensional lattices by using equivalences with hard particle models. We give in this paper a bijective proof of their results which is a generalization of Viennot's heaps of pieces [10,12]. Based on this proof we get exact enumeration formulas for the number of configurations with area n which could not be deduced directly from the algebraic equation. Moreover, we give an extension of these results to another infinite family of lattices.

Keywords: directed animal, generating functions, bijective proofs, exact enumeration formulas


References

1.  M. Bousquet, Mélou and A. Conway, Enumeration of directed animals on an infinite family of lattices, J. Phys. A: Math. Gen. 29 (1996) 3357–3365.

2.  M. Bousquet–Mélou, Les animaux dirigés croissants ou agrégats, preprint.

3.  M. Bousquet-Mélou, New enumerative results on two-dimensional directed animals, Discrete Math. 180 (1998) 73–106.

4.  D. Gouyou, Beauchamps and X.G. Viennot, Equivalence of two-dimensional directed animal problem to a one-dimensional path problem, Adv. Appl. Math.49 (1988) 334–57.

5.  A.R. Conway and A.J. Guttmann, Longitudinal size exponent for square-lattice directed animals, J. Phys. A: Math. Gen. 27 (1994) 7007–7010.

6.  S. Corteel, Problèmes énumératifs issus de l’Informatique, de la Physique et de la Combinatoire, Université Paris XI, Ph.D. Thesis, 2000.

7.  D. Dhar, Equivalence of two-dimensional directed site animal problem to Baxter’s hardsquare lattice-gas model, Phys. Rev. Lett. 49 (1982) 959–962.

8.  J. Bétréma and J.G. Penaud, Modèles avec particules dures, animaux dirig´es et séries en variables partiellement commutatives, LABRI, Université Bordeaux I, 1993.

9.  P. Flajolet and A. Odylzko, The average height of binary trees and other simple trees, J. Comp. and System Sci. 25 (1982) 171–213.

10.  J. G. Penaud, Habilitation à diriger des recherches, LABRI, Universit´e Bordeaux I, 1990.

11.  X.G. Viennot, Problèmes combinatoires posés par la physique statistique, Séminaire Bourbaki 626, Astérisque, Soc. Math. France 121, 122 (1985) 225–246.

12.  X.G. Viennot, Heaps of pieces, I: Basic definitions and combinatorial lemmas, Combinatoire ´enum´erative, Lecture Notes in Maths. Springer-Verlag, Berlin Vol. 1234 pp. 210–245, 1986.


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