Enumeration of Remarkable Families of Polyominoes

Enumeration of Remarkable Families of Polyominoes

Dominique Gouyou-Beauchamps

LRI, Université de Paris Sud (Orsay)

Algorithms Seminar

Mars 2, 1998

[summary by Cyril Banderier]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

1 Introduction

Polyominoes are objects sprung from recreative mathematics and from different domains in physics (such as Ising's model; its generalisation, Pott's model; directed percolation and branched polymer problems) [14, 20, 21, 25]. Two great classes of problems relative to polyominoes are

tiling problems;
enumeration problems.

David Klarner began to study polyomino tilings in 1965. There are still open questions in this field [12, 15, 16, 17], however several (un)decidability results are known [1, 2]. What is more, aperiodic tilings are today a new spring of inspiration in noncommutative geometry [8]. In the remainder, we only consider enumeration problems. Exact asymptotics of polyominoes on a square lattice is still unknown. Accurate results are then limited to special families of polyominoes, for which we know a generative grammar. We are therefore brought back to the study of a functional equation which defines the generating function. Nevertheless, obtaining of a closed form (i.e., an explicit solution) or even any form of solution often remains difficult. We will show several methods to obtain them.

2 Definitions

A polyomino is a connected set on a lattice. A polyomino is said to be convex if it is both column-convex and row-convex. A polyomino is said to be directed if, for each couple of points of the polyomino, there exists a path only made of North and West steps which links this two points.

One can find in previous summaries [4, 13] how to obtain functional equations satisfied by the generating functions (most of the methods are tricky decompositions [5] of polyominoes into very regular smaller pieces, such as ``strata'' or ``wasp-waist'' decompositions). For results in dimension greater than 2, see [3, 6].

3 Differential Equation Method

Enumeration of convex polyominoes with perimeter 2n on the honeycomb (or ``hexagonal'') lattice can be solved with this method. Let P_n the number of such polyominoes with perimeter 2n+6, Enting [10] gives the following result. The generating function P(x)=å_n=0^¥p_nxⁿ satisfies the differential equation

P''(x) (x²-7x⁴-2x⁵+12x⁶+8x⁷)+P'(x)(-11x-4x²+53x³+22x⁴-40x⁵-16x⁶)

+P(x)(20+22x-52x²-20x³-16x⁴-32x⁵)=20+22x-52x²+8x³+4x⁴+8x⁵

which leads to

P(x)=

1-2x+x²-x⁴-x² (1-4x²)^1/2

(1+x)² (1-2x)²

Let us mention that the package GFUN in Maple is able to make such translations (recurrences, differential equations, algebraic equations, closed forms), see [23].

4 Temperley's Method

We are going to illustrate Temperley's method [24] with the enumeration of column convex polyominoes (on a square lattice) with respect to perimeter [7]. The generating function

G(y)=

n³ 2

y²ⁿ

can be rewritten as

G(y)=

r ³ 1

g_r(y)

where the g_r satisfy a recurrence

g_r+4-2(1+y²)g_r+3+(1+3y²+3y⁴-y⁶)g_r+2-2y²(1+y²)g_r+1+y⁴g_r=0

and g₁, g₂, g₃, g₄, the ``initial conditions'', are known.

If we ``guess'' that g_r has the shape l^r (or is a linear combination of such monomials), we can obtain l by solving the fourth degree equation associated to the recurrence formula, and we find, as the equation easily splits:

(l²-l(1+y+y²-y³)+y⁴)(l²-l (1-y+y²+y³)+y²)=0.

So solving the two second degree equations gives four values (closed forms) l₁, l₂, l₃, l₄, two of which are O(1) at 0. We then have to find the A_j such that g_r=å_j=1⁴ A_j l_j^r. But g_r=O(y^2r+2) at 0, so A_i=0 if l_i=O(1). There are still two coefficients to determine, say A₂ and A₄. They can be found by solving a system involving g₁, g₂, l₂, l₄, A₂, A₄ and one finally obtains a closed form

G(y)=

A₂ l₂

1-l₂

A₄ l₄

1-l₄

A very similar method is applied for unidirectional-convex polygons on the honeycomb lattice in [19].

5 Kernel Method

In his talk, Dominique Gouyou-Beauchamps has also presented an exploitation of the ``kernel method'' for the enumeration of parallelogram polyominoes with respect to horizontal and vertical half-perimeter, area and first column height, respectively marked by x, y, q, s.

Remember that the generating function P with respect to horizontal and vertical half-perimeter is easy to obtain: The wasp-waist decomposition directly leads to P=xy+xP+yP+P² so

P(x, y)=

1-x-y-(1-2x-2y+x²+y²-2xy)^1/2

The full generating function P(x, y, q, s) satisfies a more intricate equation (obtained by a strata decomposition), namely

P(x, y, q, s)=

xysq

1-ysq

xsq

(1-sq)(1-ysq)

P(x, y, q, 1)-

xsq

(1-sq)(1-ysq)

P(x, y, q, sq).

When q=1, this can be rewritten

(1-(1-x-y)s+y²) P(x, y, 1, s) =xsP(x, y, 1, 1)+xys(1-s).

It is typically the type of equation on which the kernel method applies. This method belongs to mathematical folklore (see [18], exercise 2.2.1.4 for an early example). It works as follows: If one cancels the kernel (1-(1-x-y)s+y²), i.e., one finds s₀ such that (1-(1-x-y)s₀+y²)=0, then one gets 0=xs₀P(x, y, 1, 1)+xys₀(1-s₀), from which follows a closed form for P(x, y, 1, 1) and finally one obtains a closed form for P(x, y, 1, s), viz.,

P(x, y, 1, s) =

æ
ç
ç
è

1-x-y-(1-2x-2y-2xy+x²+y²)^1/2

ö
÷
÷
ø

+xys(1-s)

1-(1-x-y)s+y²

6 Physicists' Guesses

We have already mentioned that polyominoes are present in physical problems and in fact the first people who found interesting results on this subject where physicists. They sometimes base their works on empirical results. For example, in [9], the authors are doing as if

N_r^s=N_r-1^s-1+N_r^s-1+N_r+1^s-1

(N_r^s is the number of directed animals of size s with a ``compact source'' of size r) was a recurrence formula satisfied by the N_r^s although it is only empirically verified for the first values. Nevertheless, they go on and find that

N_r^s=

ó
õ

2 p

(1+e^it) e^-irt (1+2 cos t)^s-1 dt and in particular

N₁^s=(s-1)!

ë s/2û

q=0

s-q

q!² (s-2q)!

Another example of a typical physicist's method is [14] (enumeration of directed animals on a strip of width k); they consider a transfer matrix as an operator acting on a spin space and are drawing their inspiration from standard techniques on integrable systems.

When k tends to infinity, they obtain:

a_n=

0£ i £ n

æ
è

n-1

ö
ø

æ
è

ë i/2 û

ö
ø

and thus

n³ o

a_n tⁿ =

æ
ç
ç
è

(

1+t

1-3t

)^1/2 -1

ö
÷
÷
ø

Analysis of singularities gives

a_n ~ 3ⁿ n^-1/2.

7 Matricial and Continued Fraction Method

We will show on a simple example (Dyck paths) how this method works. Let

d_h(x)=

l³ 0

a_{h, l} x^l

the ordinary generating function of Dyck paths which end at height h.

A path of length n which ends at height h is either a path of length n-1 which ends at height h-1 followed by a NE step, or a path of length n-1 which ends at height h+1 followed by a SE step. Thus one obtains the following infinite system

ì
ï
ï
ï
ï
í
ï
ï
ï
ï
î

d₀(x)=1+x d₁(x)

d₁(x)=xd₀(x)+xd₂(x)

d₂(x)=xd₁(x)+xd₃(x)

·
·
·

d_h(x)=xd_h-1(x)+xd_h+1(x)

·
·
·

which can be written as

æ
ç
ç
ç
ç
ç
ç
è

-1	x	0	0	...
x	-1	x	0	...
0	x	-1	x	...
0	0	x	-1	...
· · ·	· · ·	· · ·	· · ·	· · ·

ö
÷
÷
÷
÷
÷
÷
ø

æ
ç
ç
ç
ç
ç
ç
è

d₀(x)

d₁(x)

d₂(x)

d₃(x)

·
·
·

ö
÷
÷
÷
÷
÷
÷
ø

æ
ç
ç
ç
ç
ç
ç
è

-1

·
·
·

ö
÷
÷
÷
÷
÷
÷
ø

With an analog of Cramer's formula for infinite matrices, one has

d₀(x)=

det

æ
ç
ç
ç
ç
ç
ç
è

-1	x	0	0	...
0	-1	x	0	...
0	x	-1	x	...
0	0	x	-1	...
· · ·	· · ·	· · ·	· · ·	· · ·

ö
÷
÷
÷
÷
÷
÷
ø

det

æ
ç
ç
ç
ç
ç
ç
è

-1	x	0	0	...
x	-1	x	0	...
0	x	-1	x	...
0	0	x	-1	...
· · ·	· · ·	· · ·	· · ·	· · ·

ö
÷
÷
÷
÷
÷
÷
ø

lim

k® ¥

det

(

)

k× k

det

(

)

k× k

lim

k® ¥

P_k(x)

Q_k(x)

where ()_{k × k} stands for the k× k truncated associated matrices. The special structure of these matrices gives the recurrence

ì
í
î

P_k(x)=-Q_k-1(x)=-P_k-1(x)-x² P_k-2(x)	with P₁(x)=-1,
Q_k(x)=-Q_k-1(x)-x²Q_k-2(x)	with Q₁(x)=-1 and Q₂(x)=1-x².

from which follows

P_k(x)

Q_k(x)

-Q_k-1(x)

Q_k(x)

-Q_k-1(x)

-Q_k-1(x)-x² Q_k-2(x)

1-x²

Q_k-2(x)

-Q_k-1(x)

1-x²

P_k-1(x)

Q_k-1(x)

and then

d₀(x)=

lim

k® ¥

P_k(x)

Q_k(x)

x²

·
·
·

hence

d₀(x)=

1-x²d₀(x)

i.e., d₀(x)=

1-(1-4x²)^1/2

2 x²

In fact the continued fraction is a special case of a much more general result that we will express in the next section.

8 Multicontinued Fractions Theorem

We will need the following notations. Let (l_{l, k})_{0£ k £ l} be a family of elements of a commutative field and let (P_k)_{k³ 0} be a family of monic polynomials which satisfy a recurrence relation:

P_k+1(x)=xP_k(x)-

i=0

l_{k, k-i} P_k-i(x).

One then defines a multicontinued fraction by

L(l, t)=

1-l_{0, 0}t -

p=1

l_{p, 0}t^p+1

i=1

1-l_{i, i}t -

q=1

l_{q+i, 0}t^q+1

i=1

·
·
·

Let d be the operator defined by d(l_{k, l})=l_{k+1, l+1}. We note P^* the reciprocal polynomial of P:

P^*(x):= x

deg(P)

Theorem 1 [Roblet, Viennot] If one sets l_{i, j}:=0 in L(l, t) for i³ k+1 and j£ i, one gets a rational fraction L_k(t), it is the k-th convergent of the multicontinued fraction L(l, t) and we have

L_k(t)=

d P_k^*(t)

P_k+1^* (t)

and the following approximation near t=0 holds

L(l, t)=L_k(t)+O(t^k+1).

For a deeper understanding of links between continued fractions and combinatorics, see [11, 22]. The multicontinued fraction method allows to find the generating functions of diagonally convex directed, diagonally convex, parallelogram, vertically convex directed, vertically convex polyominoes and remains to be exploited to obtain generating functions of other classes of polyominoes or directed animals.

You are now ready to try the different kinds of methods presented here on your favourite class of polyominoes or even on other classes of combinatorial objects!

References

[1]: Beauquier (Danièle), Nivat (Maurice), Remila (Éric), and Robson (Mike). -- Tiling figures of the plane with two bars. Computational Geometry. Theory and Applications, vol. 5, n°1, 1995, pp. 1--25.
[2]: Berger (Robert). -- The undecidability of the domino problem. Memoirs of the American Mathematical Society, vol. 66, 1966, p. 72.
[3]: Bousquet-Mélou (M.) and Guttmann (A. J.). -- Three-dimensional self-avoiding convex polygons. Physical Review E. Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics. Third Series, vol. 55, n°6, part A, 1997, pp. R6323--R6326.
[4]: Bousquet-Mélou (Mireille). -- Counting convex polyominoes according to their area. In Algorithms seminar 1995-1996. -- INRIA, 1996. Available at http://pauillac.inria.fr/algo/seminars/sem95-96/bousquet1.ps.
[5]: Bousquet-Mélou (Mireille). -- A method for the enumeration of various classes of column-convex polygons. Discrete Mathematics, vol. 154, n°1-3, 1996, pp. 1--25.
[6]: Bousquet-Mélou (Mireille) and Guttmann (Anthony J.). -- Enumeration of three-dimensional convex polygons. Annals of Combinatorics, vol. 1, n°1, 1997, pp. 27--53.
[7]: Brak (R.), Guttmann (A. J.), and Enting (I. G.). -- Exact solution of the row-convex polygon perimeter generating function. Journal of Physics. A. Mathematical and General, vol. 23, n°12, 1990, pp. 2319--2326.
[8]: Connes (Alain). -- Noncommutative geometry. -- Academic Press Inc., San Diego, CA, 1994, xiv+661p.
[9]: Dhar (Deepak), Phani (Mohan K.), and Barma (Mustansir). -- Enumeration of directed site animals on two-dimensional lattices. Journal of Physics. A. Mathematical and General, vol. 15, n°6, 1982, pp. L279--L284.
[10]: Enting (I. G.) and Guttmann (A. J.). -- Polygons on the honeycomb lattice. Journal of Physics. A. Mathematical and General, vol. 22, n°9, 1989, pp. 1371--1384.
[11]: Flajolet (P.). -- Combinatorial aspects of continued fractions. Discrete Mathematics, n°2, 1980, pp. 125--161.
[12]: Grünbaum (Branko) and Shephard (G. C.). -- Tilings and patterns. -- W. H. Freeman and Company, New York, 1989, A Series of Books in the Mathematical Sciences, xii+446p. An introduction.
[13]: Guttmann (Tony). -- Staircase polygons, elliptic integrals and Heun functions. In Algorithms seminar 1996-1997. -- 1997. Available at http://pauillac.inria.fr/algo/seminars/sem96-97/guttmann.ps.
[14]: Hakim (V.) and Nadal (J. P.). -- Exact results for 2D directed animals on a strip of finite width. Journal of Physics. A. Mathematical and General, vol. 16, n°7, 1983, pp. L213--L218.
[15]: Klarner (D.). -- My life among the polyominoes. Nieuw Archief voor Wiskunde. Derde Serie, vol. 29, n°2, 1981, pp. 156--177.
[16]: Klarner (David A.). -- Some results concerning polyominoes. The Fibonacci Quarterly, vol. 3, 1965, pp. 9--20.
[17]: Klarner (David A.). -- Packing a rectangle with congruent n-ominoes. Journal of Combinatorial Theory, vol. 7, 1969, pp. 107--115.
[18]: Knuth (Donald E.). -- The art of computer programming. -- Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1973, second edition, xxii+634p. Volume 1: Fundamental algorithms, Addison-Wesley Series in Computer Science and Information Processing.
[19]: Lin (K. Y.) and Wu (F. Y.). -- Unidirectional-convex polygons on the honeycomb lattice. Journal of Physics. A. Mathematical and General, vol. 23, n°21, 1990, pp. 5003--5010.
[20]: Privman (V.) and Svrakic (N. M.). -- Difference equations in statistical mechanics. I. Cluster statistics models. Journal of Statistical Physics, vol. 51, n°5-6, 1988, pp. 1091--1110. -- New directions in statistical mechanics (Santa Barbara, CA, 1987).
[21]: Privman (V.) and Svrakic (N. M.). -- Directed models of polymers, interfaces, and clusters: scaling and finite-size properties. -- Springer-Verlag, Berlin, 1989, Lecture Notes in Physics, vol. 338, vi+120p.
[22]: Roblet (Emmanuel) and Viennot (Xavier Gérard). -- Théorie combinatoire des T-fractions et approximants de Padé en deux points. In Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993), vol. 153, pp. 271--288. -- 1996.
[23]: Salvy (Bruno) and Zimmermann (Paul). -- Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable. ACM Transactions on Mathematical Software, vol. 20, n°2, 1994, pp. 163--177. -- ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RT/RT-0143.ps.gz.
[24]: Temperley (H. N. V.). -- Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules. Physical Review (2), vol. 103, 1956, pp. 1--16.
[25]: Viennot (Gérard). -- Problèmes combinatoires posés par la physique statistique. Astérisque, n°121-122, 1985, pp. 225--246. -- Seminar Bourbaki, Vol. 1983/84.

This document was translated from L^AT_EX by H^EV^EA.