La hauteur des polyominos dirigés verticalement convexes

Elena Barcucci, Alberto Del Lungo, Renzo Pinzani, Renzo Sprugnoli

Dipartimento di Sistemi e Informatica Via Lombroso 6/17- Firenze - Italy

1 Introduction

Les polyominos (et les animaux qui sont des structures équivalentes) ont été étudiés aussi bien par les mathématiciens, car ils constituent des objects combinatoires qui ont des propriétés très intéressantes [14], que par les physiciens car ils représentent des modèles pour plusieurs phénomènes physiques [13]. Si nous considérons le plan R × R nous pouvons définir une cellule comme un carré unitaire [i, i + 1] × [j, j + 1] (i, j ∈ N) et un polyomino comme un ensemble connexe de cellules qui sont deux à deux adjacentes par un côté. Les polyominos sont définis à une translation près. Pour obtenir un animal d’un polyomino il suffit considérer les centres des cellules qui le composent. Les définitions des paramètres caractérisant les polyominos sont très intuitives:

- l’aire d’un polyomino est le nombre de cellules qui le composent,

- le périmètre est la longueur de son contour,

- une colonne (resp. ligne) est l’intersection du polyomino avec une bande verticale (resp. horizontale) infinie [i, i + 1] × R (resp. R × [j, j + 1]).

Tant pour les polyominos que pour les animaux on peut introduire les notions de direction privilégiée et de convexité. Un polyomino dirigé est un polyomino qui peut être obtenu à partir d’une cellule appelée source en ajoutant des cellules dans deux directions (par exemple Nord et Est, c’est-à-dire au-dessus et à droite des cellules déjà présentes). De cette façon le polyomino se développe dans une direction (par exemple Nord-Est) qui est appelée direction privilégiée. Un polyomino est verticalement convexe (resp. horizontalement convexe, convexe) si ses colonnes (resp. lignes, lignes et colonnes) sont connexes. Même si les polyominos sont des structures apparemment simples les propriétés combinatoires qui les concernent ne sont pas faciles à étudier. Le problème de l’énumération selon l’aire, par exemple, a été résolu il y a cinq ans seulement par Gouyou-Beauchamps et Viennot [10] et ensuite d’une façon plus simple, par Penaud [11]. Plusieurs problèmes ont été résolus en utilisant des bijections [8] entre les objects étudiés et les mots d’un langage algébrique et en appliquant la méthodologie DSV [12] qui permet d’obtenir des fonctions génératrices à partir d’une grammaire non ambigüe. Différentes classes de polyominos ont été énumérées selon l’aire, ou le périmètre ou la largeur etc., ou une combinaison de ces paramètres [5]. Toutefois il y a encore plusieurs problèmes ouverts, par exemple l’énumération des polyominos dirigés selon le périmètre et la détermination de leur hauteur moyenne. Il faut remarquer que dans ce cas la hauteur d’un polyomino n’est pas le nombre de ses lignes mais le nombre de droites d’équation y = −x + k (k ∈ N) qui passent par les centres des cellules du polyomino. Cette définition s’accorde avec la définition standard de hauteur pour les arbres

[figure]

Figure 1: Polyomino dirigé verticalement convexe d’aire 36 et de hauteur 16

binaires et d’autres structures utilisées en l’informatique. Pour ce qui concerne la hauteur moyenne des polyominos dirigés il y a une conjecture formulée par les physiciens [9] qui a été confirmée par des résultats de simulation [2]. Dans ce papier nous étudions la classe des polyominos dirigés verticalement convexes et en utilisant des relations de récurrence, nous les énumérons selon l’aire et la hauteur et nous déterminons leur hauteur moyenne. L’évaluation théorique s’accorde parfaitement avec les résultats expérimentaux que nous avons obtenus par la génération aléatoire qui utilise l’algorithme présenté en [3]. Ce résultat concerne une classe particulière de polyominos mais, à la connaissance des auteurs, c’est le premier résultat exact sur la hauteur des polyominos dirigés.

2 Dénombrement des polyominos dirigés verticalement convexes selon les paramètres aire et hauteur

Proposition 2.1 Le nombre V_{n,k} de polyominos dirigés verticalement convexes d’aire n et de hauteur k satisfait la relation de récurrence suivante:

V_{n,k} = V_{n−1,k−1} + ∑_{j=1}^{k−1} V_{n−k,j} + ∑_{j=1}^{k−1} V_{n−j,k−1},  n > 1, k > 1.  (2.1)

Preuve. Soit P un polyomino dirigé verticalement convexe d’aire n et de hauteur k. Si P ne contient pas la cellule L adjacente au côté droit de la source S, en éliminant S de P on obtient un polyomino P′, d’aire n − 1 et de hauteur k − 1 (voir fig. 2). Si la cellule L

S  LP′

Figure 2: Polyomino P

appartient à P, alors P est obtenu attachant un polyomino P′′ à une colonne C de hauteur j, avec 1 ≤ j ≤ k, de façon que la source S_{1} de P′′ soit adjacente à la première cellule de la colonne C. Si j = k alors le polyomino P′′ est d’aire n−k et de hauteur i, avec 1 ≤ i ≤ k −1 (voir fig. 3). Si 1 ≤ j ≤ k − 1, le polyomino P′′ est d’aire n − j et de hauteur k − 1 (voir

[figure: k; C; S_{1}; P′′]

Figure 3: Polyomino P ayant la première colonne de hauteur k

fig. 4). Ainsi on obtient:

[figure: j; C; S_{1}; P′′]

Figure 4: Polyomino P ayant la première colonne de hauteur j < k

V_{n,k} = V_{n−1,k−1} + ∑_{j=1}^{k−1} V_{n−k,j} + ∑_{j=1}^{k−1} V_{n−j,k−1}.

On a V_{n,k} = 0 pour n ≤ 0 k ≤ 0, et V_{1,1} = 1. Donc l’équation (2.1) est modifiée de la façon suivante:

V_{n,k} = V_{n−1,k−1} + ∑_{j=1}^{k−1} V_{n−k,j} + ∑_{j=1}^{k−1} V_{n−j,k−1} + [n = 1, k = 1].

En posant:

V_{k}(t) = ∑_{n} V_{n,k}t^{n},

de la récurrence (2.1) on obtient:

V_{k}(t) = t V_{k−1}(t) + t^{k} ∑_{j=1}^{k−1} V_{j}(t) + \frac{t − t^{k}}{1 − t} V_{k−1}(t) + [k = 1] t.  (2.2)

Si on définit:

V (t, z) = ∑_{n,k} V_{n,k} t^{n}z^{k},  (2.3)

on a:

V (t, z) = ∑_{k} V_{k}(t) z^{k},

et donc d’après (2.2):

Théorème 2.2 La fonction génératrice V (t, z) des polyominos dirigés verticalement convexes comptés suivant l’aire et la hauteur par t et z respectivement, satisfait l’équation suivante:

V (t, z) = \frac{zt(1 − t)}{1 − t − 2zt + zt^{2}} + \frac{zt^{2}(z − 1)}{(1 − t − 2zt + zt^{2})(1 − zt)}V (t, tz).  (2.4)

Remarque. En posant z = 1 on retrouve la fonction génératrice F (t) des polyominos dirigés verticalement convexes comptés selon l’aire:

F (t) = V (t, 1) = \frac{t(1 − t)}{1 − 3t + t^{2}}

(voir [1, 7]).

3 Hauteur moyenne des polyominos dirigés verticalement convexes

Pour obtenir la hauteur moyenne on détermine une estimation de la somme des hauteurs des polyominos dirigés verticalement convexes d’aire fixée.

Proposition 3.1 Soit S_{n} la somme des hauteurs des polyominos dirigés verticalement convexes d’aire n. La fonction génératrice S(t) = ∑_{n} S_{n} t^{n} est:

S(t) = \frac{t(1 − t)^{2}}{(1 − 3t + t^{2})^{2}} + \frac{t^{2}}{(1 − t)(1 − 3t + t^{2})} V (t, t).  (3.1)

Preuve. Puisque V_{n,k} est le nombre des polyominos dirigés d’aire n et de hauteur k on a:

S_{n} = ∑_{k} k V_{n,k},

et donc d’après (2.3):

S(t) = \frac{∂}{∂z} V (t, z)_{|z=1}.

En utilisant l’équation (2.4) on a:

(1 − t − 2zt + zt^{2}) V (t, z) = zt(1 − t) + \frac{zt^{2}(z − 1)}{1 − zt}V (t, tz),

d’où en dérivant par rapport à z et en posant z = 1, on déduit:

S(t) = \frac{t(1 − t)^{2}}{(1 − 3t + t^{2})^{2}} + \frac{t^{2}}{(1 − t)(1 − 3t + t^{2})} V (t, t).

Maintenant nous calculons une estimation de la somme des hauteurs des polyominos dirigés verticalement convexes d’aire n, c’est-à-dire la valeur S_{n}. De la proposition 3.1 on a:

S(t) = f(t) + g(t) V (t, t),

où,

f(t) = \frac{t(1 − t)^{2}}{(1 − 3t + t^{2})^{2}} ,  g(t) = \frac{t^{2}}{(1 − t)(1 − 3t + t^{2})},  V (t, t) = ∑_{k} V_{k}(t) t^{k}.

La fonction f(t) a deux pôles du second ordre, un dans t_{0} = \frac{1}{ϕ^{2}} et l’autre dans t_{1} = \frac{1}{ϕ̂^{2}} , où

ϕ = \frac{1+\sqrt{5}}{2} et ϕ̂ = 1 − ϕ. Le point singulier dominant de la f(t) est t_{0} et donc:

f_{n} = [t^{n}] f(t) ≈ (a_{0} n + a_{1}) ϕ^{2n},

où

a_{0} = lim_{t→ \frac{1}{ϕ^{2}}} (1 − ϕ^{2} t)^{2} f(t),  (3.2)
a_{1} = −\frac{1}{ϕ^{2}} lim_{t→ \frac{1}{ϕ^{2}}} \frac{d}{dt} ((1 − ϕ^{2} t)^{2} f(t)) .  (3.3)

Mais f(t) = \frac{t(1−t)^{2}}{(1−ϕ^{2} t)^{2} (1−ϕ̂^{2} t)^{2}} et ϕ̂^{2} = \frac{1}{ϕ^{2}} , et ainsi d’après (3.2):

a_{0} = \frac{\frac{1}{ϕ^{2}} (1 − \frac{1}{ϕ^{2}} )^{2}}{(1 − \frac{1}{ϕ^{4}} )^{2}} = \frac{1}{5}.

Puisque:

\frac{d}{dt} ((1 − ϕ^{2} t)^{2} f(t)) = \frac{(1 − 4t + 3t^{2})(1 − ϕ̂^{2} t) + 2ϕ̂^{2} t(1 − t)^{2}}{(1 − ϕ̂^{2} t)^{3}} ,

d’après (3.3):

a_{1} = −\frac{5 − 2\sqrt{5}}{25},

et par conséquent:

f_{n} = [t^{n}] f(t) ≈ \frac{1}{5}(n − \frac{5 − 2\sqrt{5}}{5}) ϕ^{2n}.

Maintenant on considère le deuxième terme de S(t), c’est-à-dire g(t) V (t, t) = ∑_{n} c_{n} t^{n}. En utilisant la récurrence (2.2) on obtient:

V_{k+1}(t) = \frac{2t − t^{2}}{1 − t} V_{k}(t) + \frac{t^{k+2}}{1 − t} V_{k}(t) + t^{k+1} ∑_{j=1}^{k−1} V_{j}(t).  (3.4)

En posant δ_{k} = V_{k}(\frac{1}{2}) on a:

δ_{k+1} = \frac{3}{2} δ_{k} − \frac{1}{2^{k+1}} δ_{k} + \frac{1}{2^{k+1}} ∑_{j=1}^{k−1} δ_{j},

d’où

\frac{δ_{k+1}}{δk} = \frac{3}{2} − \frac{1}{2^{k+1}} + \frac{1}{2^{k+1}} \frac{1}{δ_{k}} ∑_{j=1}^{k−1} δ_{j}.

Mais:

V (\frac{1}{2}, \frac{1}{2}) = ∑_{k} V_{k}(\frac{1}{2}) \frac{1}{2^{k}} = ∑_{k} \frac{δ_{k}}{2^{k}} ,

donc

lim_{k→+∞} \frac{\frac{δ_{k+1}}{2^{k+1}}}{\frac{δ_{k}}{2^{k}}} = \frac{3}{4} < 1,

et ainsi d’après le critère de D’Alembert la série V (t, t) converge dans t = \frac{1}{2}. Par conséquent, d’après le théorème d’Abel, le rayon de convergence ρ de V (t, t) est tel que ρ ≥ \frac{1}{2}. La fonction g(t) a rayon de convergence ρ′ = \frac{1}{ϕ^{2}} , et donc:

ρ > ρ′ > 0.  (3.5)

Le point singulier dominant de g(t) est t_{0} = \frac{1}{ϕ^{2}} et ainsi:

g_{n} = [t^{n}] g(t) ≈ b_{0} ϕ^{2n},

où

b_{0} = lim_{t→ \frac{1}{ϕ^{2}}} (1 − ϕ^{2} t) g(t) = \frac{5 − \sqrt{5}}{10}.

Donc:

lim_{n→+∞} \frac{g_{n+1}}{g_{n}} = \frac{1}{ϕ^{2}} .  (3.6)

Maintenant nous prouvons que V (\frac{1}{ϕ^{2}} , \frac{1}{ϕ^{2}} ) ≠ 0. Puisque V_{k}(t) = ∑_{n≥k} V_{n,k} t^{n}, et V_{n,k} ≥ 0 on a:

t^{k} V_{k}(t) > V_{k}(t^{2}), t < 1,

et:

V (t, t) > ∑_{k} V_{k}(t^{2}), t < 1.

Mais:

V (t^{2}, 1) = ∑_{k} V_{k}(t^{2}) = \frac{t^{2}(1 − t^{2})}{1 − 3t^{2} + t^{4}} ,

donc on obtient:

V (\frac{1}{ϕ^{2}} , \frac{1}{ϕ^{2}} ) > V (\frac{1}{ϕ^{4}} , 1) > 0.  (3.7)

En utilisant les conditions (3.5), (3.6) et (3.7) on peut appliquer le théorème 2 de Bender [4], d’où on déduit que le coefficient c_{n} de t^{n} dans g(t) V (t, t) est tel que:

c_{n} ≈ g_{n} V (\frac{1}{ϕ^{2}} , \frac{1}{ϕ^{2}} ),

et ainsi:

c_{n} ≈ \frac{5 − \sqrt{5}}{10} V (\frac{1}{ϕ^{2}} , \frac{1}{ϕ^{2}} ) ϕ^{2n}.

En posant α_{k} = V_{k}(\frac{1}{ϕ^{2}} ) on a:

V (\frac{1}{ϕ^{2}} , \frac{1}{ϕ^{2}} ) = ∑_{k=1}^{∞} \frac{α_{k}}{ϕ^{2k}} .

D’après (3.4):

α_{k+1} = (1 − \frac{1}{ϕ^{2k+3}} ) α_{k} + \frac{1}{ϕ^{2k+2}} ∑_{j=1}^{k−1} α_{j}.  (3.8)

En utilisant cette récurrence, on détermine expérimentalement que la valeur de la somme est:

V (\frac{1}{ϕ^{2}} , \frac{1}{ϕ^{2}} ) ≈ 0.229265982292,

et donc:

c_{n} ≈ 0.6336757901 ϕ^{2n}.

Puisque S_{n} = f_{n} + c_{n} d’après ce qui précède on déduit:

Proposition 3.2 La somme S_{n} des hauteurs des polyominos dirigés verticalement convexes d’aire n est:

S_{n} ≈ \frac{n}{5} ϕ^{2n} (1 + \frac{1.21126498605}{n}) .  (3.9)

Le nombre V_{n} de polyominos dirigés verticalement convexes d’aire n est le nombre de Fibonacci F_{2n−1} [1, 7], donc:

V_{n} = F_{2n−1} ≈ \frac{1}{\sqrt{5}} ϕ^{2n−1},

et par conséquent, de la proposition (3.9) on déduit:

Théorème 3.3 La hauteur moyenne des polyominos dirigés verticalement convexes d’aire n est:

ξ_{∥}(n) ≈ \frac{ϕ}{\sqrt{5}} n + 0.87647957778.  (3.10)

Remarque. On peut déterminer le rayon de convergence ρ′′ de V (t, t) = ∑_{k} V_{k}(t) t^{k} = ∑_{i} v_{i} t^{i}. Posons

β_{k} = V_{k}(α), avec α ∈ ℜ. Alors d’après (3.4):

β_{k+1} = \frac{2α − α^{2}}{1 − α} β_{k} − \frac{α^{k+2}}{1 − α} β_{k} + α^{k+1} ∑_{j=1}^{k−1} β_{j},  (3.11)

et donc on a:

lim_{k→+∞} \frac{β_{k+1}}{β_{k}} = \frac{2α − α^{2}}{1 − α} .

On déduit, d’après le critère de D’Alembert, que la série V (α, α) = ∑_{k} β_{k} α^{k} converge si

\frac{2α^{2} − α^{3}}{1 − α} < 1.

Donc la série V (t, t) a rayon de convergence ρ′′ = λ où:

λ = \frac{2}{3} − \frac{\sqrt{7}}{3} cos (\frac{1}{3} arctan (3\sqrt{3})) + \sqrt{\frac{7}{3}} sin (\frac{1}{3} arctan (3\sqrt{3})) ≈ 0.554958132088.

Par conséquent:

Proposition 3.4 Le nombre v_{i} de polyominos dirigés verticalement convexes d’aire n et de hauteur k tels que i = n + k est:

v_{i} = O (\frac{1}{λ^{i}} ) .

4 Dénombrement des polyominos dirigés verticalement convexes selon la hauteur

Proposition 4.1 Le nombre W_{k} de polyominos dirigés verticalement convexes de hauteur k satisfait la relation de récurrence suivante:

W_{k+2} − (k + 4) W_{k+1} + (k + 1) W_{k} = 0,  (4.1)

où W_{0} = 1 et W_{1} = 1.

Preuve. Le nombre W_{k} est tel que:

W_{k} = ∑_{n=1}^{∞} V_{n,k},

donc

W_{k} = V_{k}(1).

En utilisant la relation (2.2) on déduit:

V_{k+1}(t) = t V_{k}(t) + ∑_{j=1}^{k} t^{j} V_{k}(t) + t^{k+1} ∑_{j=1}^{k} V_{j}(t) + [k = 0] t,

ainsi on a:

W_{k+1} = (k + 1) W_{k} + ∑_{j=1}^{k} W_{j},

et par conséquent:

W_{k+2} = (k + 4) W_{k+1} − (k + 1) W_{k}.

La fonction X_{k} = k! k est une solution de l’équation (4.1). En utilisant la transformation W_{k} = X_{k} Y_{k} dans l’équation (4.1) on a:

(k + 2)^{2} (Y_{k+2} − Y_{k+1}) − k (Y_{k+1} − Y_{k}) = 0.

En posant Z_{k} = Y_{k+1} − Y_{k}, on obtient:

Z_{k+1} = \frac{k}{(k + 2)^{2}} Z_{k},

d’où

Z_{k} = \frac{C_{1}}{k (k + 1) (k + 1)!},

et ainsi:

Y_{k} = ∑_{j=1}^{k−1} \frac{C_{1}}{j (j + 1) (j + 1)!} + C_{2},

où C_{1} et C_{2} sont deux constantes. Mais W_{1} = 1 et W_{2} = 3, et d’après ce qui précède, on a le résultat suivant:

Théorème 4.2 Le nombre W_{k} de polyominos dirigés verticalement convexes ayant la hauteur k est:

W_{k} = k! k (1 − ∑_{j=1}^{k−1} \frac{1}{j (j + 1) (j + 1)!}) .  (4.2)

Remarque.

∑_{j=0}^{∞} \frac{1}{(j + 1) (j + 1)!} = ∫_{0}^{1} \frac{e^{t} − 1}{t} dt,

∑_{j=1}^{∞} \frac{1}{j (j + 1)!} = ∫_{0}^{1} \frac{e^{t} − t − 1}{t^{2}} dt,

∑_{j=1}^{∞} \frac{1}{j (j + 1) (j + 1)!} = ∫_{0}^{1} \frac{te^{t} − t − 1}{t^{2}} dt = 3 − e,

donc on a:

W_{k} ≈ (e − 2) k! k.

Observons que pour k = 6 en approchant 1− ∑_{j=1}^{k−1} \frac{1}{j (j+1) (j+1)!} avec e−2 on commet une erreur

de l’ordre de 10^{−6}.

References

[1] E. Barcucci, R. Pinzani, E. Rodella et R. Sprugnoli, A Characterization of Binary Search Networks, Fundamentals of Computation Theory, ed. Budach, Lecture Notes in Computer Science, 529 (1991) 126-135.

[2] E. Barcucci, R. Pinzani et R. Sprugnoli, Génération aléatoire des animaux dirigés, Atelier de Combinatoire franco-québecois, eds. J. Labelle et J. G. Penaud, Publications du LACIM, n^{∘} 10, Université Bordeaux 1, (1991) 17-25.

[3] E. Barcucci, R. Pinzani et R. Sprugnoli, Directed Column-Convex Polyominoes by Recurrence Relations, TAPSOFT’93, eds. M. C. Gaudel, J. P. Jouannaud, Lecture Notes in Computer Science 668 (1993) 282-298.

[4] E. A. Bender, Asymptotic methods in enumeration, SIAM Rev., 16 (1974) 485-514.

[5] M. Bousquet-Mélou, q-Énumération de polyominos convexes, Publications du LACIM, n^{∘} 9, Université du Québec à Montreal, (Thèse de doctorat, Université Bordeaux 1, (1991)).

[6] M. Delest, Polyominoes and animals: Some recent results, Proc. Math/Chem/Comp 90, Dubrovnik, Croatie, J. of Computer and Chemistry, 8 (1991) 3-18.

[7] M. Delest et S. Dulucq, Enumeration of Directed Column-Convex Animals with given Perimeter and Area, rapport LaBRI n^{∘} 86-15, Université Bordeaux 1, (1987).

[8] M. Delest et X. G. Viennot, Algebraic languages and polyominoes enumeration, Theor. Comp. Sci., 34 (1984) 169-206.

[9] B. Derrida, J. P. Nadal et J. Vannimenus, Directed lattice animals in 2 dimensions: Numerical and exact results, J. Physique 43, (1982) 1561.

[10] D. Gouyou-Beauchamps et X. G. Viennot, Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Advances in Applied Mathematics 9, (1988) 334-357.

[11] J. G. Penaud, Une nouvelle bijection pour les animaux dirigés, Actés du 22ème Séminaire Lotharingien de combinatoire, Publi. IRMA, Université Strasbourg I (1989).

[12] M. P. Schützenberger, Context-free langages and pushdown automata, Information and Control 6, (1963) 246-264.

[13] X. G. Viennot, Problèmes combinatoires posés par la physique statistique, Séminaire Bourbaki n^{∘} 626, 36ème année, in Astérisque n^{∘} 121-122, (1985) 225-246, Soc. Math. France.

[14] X. G. Viennot, A Survey of Polyomino enumeration, Proc. Séries formelles et combinatoire algébrique, Montréal, Juin 1992, eds. P. Leroux et C. Reutenauer, Publications du LACIM, n^{∘} 11, Université du Québec à Montréal (1992).