Annals of Combinatorics 3 (1999) 311-321

Q-Grammars and Wall Polyominoes

Philippe Duchon

LaBRI, Université Bordeaux 1, 351 Cours de la Libération, F-33407 Talence Cedex, France

Received October 30, 1998

AMS Subject Classification: 05B50, 05A16, 39B32, 82B23

Abstract. We use a variant of the q-grammar method to write functional equations for the generating functions of a subclass of vertically convex polyominoes and directed walks, according to specified parameters, which include the area. The form of these equations, and some simple singularity computations, are used to prove that the area of wall polyominoes of perimeter 2n has the Airy distribution as a limit law.

Keywords: polyominoes, asymptotic enumeration, functional equations


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

2.  M. Delest and J.-M. Fèdou, Attribute grammars are useful for combinatorics, J. Theor. Comput. Sci. 98 (1992) 65–76.

3.  M. Delest, D. Gouyou-Beauchamp, and B. Vauquelin, Enumeration of parallelogram polyominoes with given bond and site perimeter, Graphs Comb. 3 (1987) 325–339.

4.  P. Duchon, Asymptotic distributions in functional equations with variable substitutions, in preparation.

5.  P. Duchon, Q-grammaires, un outil pour l'ènumèration, Thèse de doctorat, Universitè Bordeaux 1, 1998.

6.  I. Dutour and J.-M. Fèdou, Object grammars and random generation, Discrete Mathematics and Theoretical Computer Science 2 (1998) 47–61.

7.  S. Feretic, The column-convex polyominoes perimeter generating function for everybody, Croatica Chemica Acta 69 (1996) 741–756.

8.  S. Feretic, A new way of counting the column-convex polyominoes by perimeter, Discrete Math. 180 (1998) 173–184.

9.  P. Flajolet, P. Poblete, and A. Viola, On the analysis of linear probing hashing, Rapport de recherche 3265, INRIA, 1997.

10.  G. Louchard, The Brownian excursion: A numerical analysis, Computers and Mathematics with Applications 10 (1984) 413–417.

11.  G. Louchard, Kac's formula, Lèvy's local time and brownian excursion, J. Appl. Prob. 21 (1984) 479–499.

12.  A.L. Owczarek and T. Prellberg, Exact solution of the discrete (1+1)--dimensional SOS model with field and surface interactions, J. Stat. Phys. 70 (1993) 1175–1194.

13.  T. Prellberg and R. Brak, Critical exponents from non-linear functional equations for directed cluster models, J. Stat. Phys. 78 (1995) 701–730.

14.  L. Takàcs, The asymptotic distribution of the total heights of random rooted trees, Acta Scientifica Mathematica (Szeged) 57 (1993) 613–625.

15.  H.N.V. Temperley, Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules, Phys. Rev. 103 (1956) 1–16.

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