Annals of Combinatorics 3 (1999) 223-249

Inversion Relations, Reciprocity and Polyominoes

M. Bousquet-Mélou1, A.J. Guttmann2,W.P. Orrick2, and A. Rechnitzer2

1Laboratoire Bordelais de Recherche en Informatique, Université Bordeaux I, 351 cours de la Libération, 33405 Talence Cedex, France

2Department of Mathematics and Statistics, The University of Melbourne, Parkville, Victoria 3052, Australia,

Received June 30, 1999

AMS Subject Classification: 05A15, 05B50, 82B20, 82B23

Abstract. We derive self-reciprocity properties for a number of polyomino generating functions, including several families of column-convex polygons, three-choice polygons, and staircase polygons with a staircase hole. In so doing, we establish a connection between the reciprocity results known to combinatorialists and the inversion relations used by physicists to solve models in statistical mechanics. For several classes of convex polygons, the inversion (reciprocity) relation, augmented by certain symmetry and analyticity properties, completely determines the anisotropic perimeter generating function.

Keywords: nversion relations, combinatorial reciprocity theorems, polyominoes, self-avoiding polygons, convex polygons, statistical mechanics


1.  R.J. Baxter, Hard hexagons: exact solution, J. Phys. A 13 (1980) L6170.

2.  M.P. Delest and X.G. Viennot, Algebraic languages and polyominoes enumeration, Theoretical Comput. Sci. 34 (1984) 69206.

3.  C. Domb, On the theory of cooperative phenomena in crystals, Adv. Phys. 19 (1970) 339 519.

4.  M.E. Fisher, Walks, walls, wetting and melting, J. Stat. Phys. 34 (1984) 667730.

5.  I.M. Gessel and X. Viennot, Determinants, paths, and plane partitions, 1989, preprint.

6.  B. Gordon, A proof of the Bender-Knuth conjecture, Pacific J. Math. 108 (1983) 99113.

7.  A.J. Guttmann and I.G. Enting, The number of convex polygons on the square and honeycomb lattices, J. Phys. A 21 (1988) L467474.

8.  S. Karlin and G. McGregor, Coincidence probabilities, Pacific J. Math. 9 (1959) 11411164.

9.  D. Kim, The number of convex polygons with given perimeter, Discrete Math. 70 (1988) 4751.

10.  E.H. Lieb, Exact solution of the problem of the entropy of two-dimensional square ice, Phys. Rev. Letts. 18 (1967) 692694.

11.  B. Lindström, On the vector representations of induced Matroids, Bull. Lond. Math. Soc. 5 (1973) 8590.

12.  L Onsager, Crystal statistics I: A two-dimensional model with an order-disorder transition, Phys. Rev. 65 (1944) 117149.

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