Enumeration of Remarkable Families of Polyominoes
Dominique GouyouBeauchamps
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 columnconvex and rowconvex.
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 ``waspwaist''
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_{n}x^{n} satisfies
the differential equation
P''(x) (x^{2}7x^{4}2x^{5}+12x^{6}+8x^{7})+P'(x)(11x4x^{2}+53x^{3}+22x^{4}40x^{5}16x^{6}) 
+P(x)(20+22x52x^{2}20x^{3}16x^{4}32x^{5})=20+22x52x^{2}+8x^{3}+4x^{4}+8x^{5} 
which leads to
P(x)= 
12x+x^{2}x^{4}x^{2} (14x^{2})^{1/2} 

(1+x)^{2} (12x)^{2} 

. 
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 can be rewritten as
where the g_{r} satisfy a recurrence
g_{r+4}2(1+y^{2})g_{r+3}+(1+3y^{2}+3y^{4}y^{6})g_{r+2}2y^{2}(1+y^{2})g_{r+1}+y^{4}g_{r}=0
and g_{1}, g_{2}, g_{3}, g_{4}, 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^{2}l(1+y+y^{2}y^{3})+y^{4})(l^{2}l (1y+y^{2}+y^{3})+y^{2})=0.
So solving the two second degree equations gives four values (closed
forms)
l_{1}, l_{2}, l_{3}, l_{4}, two of which are O(1) at 0.
We then have to find the A_{j} such that g_{r}=å_{j=1}^{4} 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_{2} and A_{4}.
They can be found by solving a system involving
g_{1}, g_{2}, l_{2}, l_{4}, A_{2}, A_{4} and one finally obtains a closed form
A very similar method is applied for
unidirectionalconvex polygons on the honeycomb lattice in [19].
5 Kernel Method
In his talk, Dominique GouyouBeauchamps has also presented an
exploitation of the ``kernel method'' for the enumeration of
parallelogram polyominoes
with respect to horizontal and vertical halfperimeter, area and first column
height, respectively marked by x, y, q, s.
Remember that the generating function P with respect to
horizontal and vertical halfperimeter is easy to obtain:
The waspwaist decomposition directly leads to P=xy+xP+yP+P^{2} so
P(x, y)= 
1xy(12x2y+x^{2}+y^{2}2xy)^{1/2} 

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)= 

+ 

P(x, y, q, 1) 

P(x, y, q, sq). 
When q=1, this can be rewritten
(1(1xy)s+y^{2}) P(x, y, 1, s) =xsP(x, y, 1, 1)+xys(1s).
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(1xy)s+y^{2}),
i.e., one finds s_{0} such that (1(1xy)s_{0}+y^{2})=0,
then one gets 0=xs_{0}P(x, y, 1, 1)+xys_{0}(1s_{0}), 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) = 
xs 
æ ç ç è 
1xy(12x2y2xy+x^{2}+y^{2})^{1/2} 

2 


ö ÷ ÷ ø 
+xys(1s) 


1(1xy)s+y^{2} 

. 
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_{r1}^{s1}+N_{r}^{s1}+N_{r+1}^{s1}
(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}= 


ó õ 

(1+e^{it}) e^{irt} (1+2 cos t)^{s1} dt
and in particular 
N_{1}^{s}=(s1)! 



. 
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}= 


and thus 


a_{n} t^{n} = 


æ ç ç è 
( 

)^{1/2} 1 
ö ÷ ÷ ø 
. 
Analysis of singularities gives a_{n} ~ 3^{n} n^{1/2}.
7 Matricial and Continued Fraction Method
We will show on a simple example (Dyck paths) how this method works.
Let
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 n1 which ends at height h1 followed by
a NE step,
or a path of length n1 which ends at height h+1 followed by
a SE step. Thus one obtains the following infinite system
ì ï ï ï ï í ï ï ï ï î 
d_{0}(x)=1+x d_{1}(x) 
d_{1}(x)=xd_{0}(x)+xd_{2}(x) 
d_{2}(x)=xd_{1}(x)+xd_{3}(x) 
· · · 
d_{h}(x)=xd_{h1}(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_{0}(x) 
d_{1}(x) 
d_{2}(x) 
d_{3}(x) 
· · · 

ö ÷ ÷ ÷ ÷ ÷ ÷ ø 

=


.

With an analog of Cramer's formula for infinite matrices, one has
d_{0}(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 
... 
· · · 
· · · 
· · · 
· · · 
· · · 

ö ÷ ÷ ÷ ÷ ÷ ÷ ø 



= 



= 


where ()_{k × k}
stands for the k× k truncated associated matrices.
The special structure of these matrices gives the recurrence
ì í î 
P_{k}(x)=Q_{k1}(x)=P_{k1}(x)x^{2} P_{k2}(x)

with P_{1}(x)=1, 
Q_{k}(x)=Q_{k1}(x)x^{2}Q_{k2}(x) 
with Q_{1}(x)=1 and Q_{2}(x)=1x^{2}. 

from which follows

= 

=

Q_{k1}(x) 

Q_{k1}(x)x^{2} Q_{k2}(x) 

=


=


and then
hence
d_{0}(x)= 

i.e., d_{0}(x)= 
1(14x^{2})^{1/2} 

2 x^{2} 

. 
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) 

l_{k, ki} P_{ki}(x). 
One then defines a multicontinued fraction by
L(l, t)= 
1 

1l_{0, 0}t
 

l_{p, 0}t^{p+1} 


1 

1l_{i, i}t
 

l_{q+i, 0}t^{q+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:
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 kth 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. 125.
 [2]

Berger (Robert). 
The undecidability of the domino problem. Memoirs of the
American Mathematical Society, vol. 66, 1966, p. 72.
 [3]

BousquetMélou (M.) and Guttmann (A. J.). 
Threedimensional selfavoiding convex polygons. Physical Review
E. Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary
Topics. Third Series, vol. 55, n°6, part A, 1997,
pp. R6323R6326.
 [4]

BousquetMélou (Mireille). 
Counting convex polyominoes according to their area. In Algorithms seminar 19951996. 
INRIA, 1996. Available at http://pauillac.inria.fr/algo/seminars/sem9596/bousquet1.ps.
 [5]

BousquetMélou (Mireille). 
A method for the enumeration of various classes of columnconvex
polygons. Discrete Mathematics, vol. 154, n°13,
1996, pp. 125.
 [6]

BousquetMélou (Mireille) and Guttmann (Anthony J.). 
Enumeration of threedimensional convex polygons. Annals of
Combinatorics, vol. 1, n°1, 1997, pp. 2753.
 [7]

Brak (R.), Guttmann (A. J.), and Enting (I. G.). 
Exact solution of the rowconvex polygon perimeter generating
function. Journal of Physics. A. Mathematical and General, vol. 23,
n°12, 1990, pp. 23192326.
 [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 twodimensional lattices.
Journal of Physics. A. Mathematical and General, vol. 15, n°6,
1982, pp. L279L284.
 [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. 13711384.
 [11]

Flajolet (P.). 
Combinatorial aspects of continued fractions. Discrete
Mathematics, n°2, 1980, pp. 125161.
 [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 19961997. 
1997. Available at http://pauillac.inria.fr/algo/seminars/sem9697/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. L213L218.
 [15]

Klarner (D.). 
My life among the polyominoes. Nieuw Archief voor Wiskunde.
Derde Serie, vol. 29, n°2, 1981, pp. 156177.
 [16]

Klarner (David A.). 
Some results concerning polyominoes. The Fibonacci Quarterly,
vol. 3, 1965, pp. 920.
 [17]

Klarner (David A.). 
Packing a rectangle with congruent nominoes. Journal of
Combinatorial Theory, vol. 7, 1969, pp. 107115.
 [18]

Knuth (Donald E.). 
The art of computer programming. 
AddisonWesley Publishing Co., Reading, Mass.LondonAmsterdam,
1973, second edition, xxii+634p. Volume 1: Fundamental
algorithms, AddisonWesley Series in Computer Science and Information
Processing.
 [19]

Lin (K. Y.) and Wu (F. Y.). 
Unidirectionalconvex polygons on the honeycomb lattice. Journal
of Physics. A. Mathematical and General, vol. 23, n°21,
1990, pp. 50035010.
 [20]

Privman (V.) and Svrakic (N. M.). 
Difference equations in statistical mechanics. I. Cluster
statistics models. Journal of Statistical Physics, vol. 51, n°56,
1988, pp. 10911110. 
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 finitesize properties. 
SpringerVerlag, Berlin, 1989, Lecture Notes in
Physics, vol. 338, vi+120p.
 [22]

Roblet (Emmanuel) and Viennot (Xavier Gérard). 
Théorie combinatoire des Tfractions 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. 271288. 
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. 163177. 
ftp://ftp.inria.fr/INRIA/publication/publipsgz/RT/RT0143.ps.gz.
 [24]

Temperley (H. N. V.). 
Combinatorial problems suggested by the statistical mechanics of
domains and of rubberlike molecules. Physical Review (2), vol. 103,
1956, pp. 116.
 [25]

Viennot (Gérard). 
Problèmes combinatoires posés par la physique statistique. Astérisque, n°121122, 1985, pp. 225246. 
Seminar Bourbaki, Vol. 1983/84.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.