Géométrie combinatoire

Polyominos

Le terme polyomino a été introduit par le mathématicien S. Golomb et consiste en une généralisation du mot domino, cet objet formé de deux carrés de même dimension. En effet, un polyomino est constitué de plusieurs carrés unitaires connectés par leurs côtés. Ces carrés sont souvent nommés des cellules. Tel que mentionné précédemment, les polyominos peuvent entre  autres être dénombrés en fonction de leur aire, de leur périmètre ou même des deux. L’aire d’un polyomino est le nombre de cellules qu’il contient, son périmètre est le nombre de côtés simultanément en contact avec une cellule à l’intérieur et à l’extérieur du polyomino et, finalement, le périmètre de site est le nombre de cellules voisines vacantes. De plus, on distingue parfois le périmètre horizontal du périmètre vertical, selon qu’il s’agit d’un côté horizontal ou vertical qui contribue au périmètre.

Produit diagonal

Une astuce élaborée afin de déterminer les séries génératrices de divers polyominos est l’utilisation du produit diagonal, également appelé concaténation . Ce produit consiste en un collage diagonal de polyominos obtenu en superposant deux cellules dans un coin, cette opération est symbolisée par « x » , mais ce dernier symbole étant utilisé pour les dimensions du rectangle circonscrit, on utilisera plutôt « . » . Le produit diagonal est mis à profit afin d’obtenir les séries génératrices de certaines classes de polyominos, dont les polyominos d’aire minimale plus un et plus deux ainsi que pour l’énumération à symétries près. Ce produit permet la construction d’un polyomino d’un index donné à l’aide de polyominos d’index inférieur, car l’index est une fonction additive sous ce produit et la série génératrice est obtenue par le produit des séries des polyominos d’index inférieur moyennant un petit ajustement.

Minimaux plus un

On rappelle que les minimaux plus un sont des polyominos d’aire b + k inscrits dans un k x b, ils ont ainsi une cellule de plus que les polyominos d’aire minimale inscrits dans le même rectangle.

Ces polyominos ont été l’objet d’étude dans le mémoire de L. J. Llerena . Toutefois, les séries génératrices des bancs-coins et des coins d’index 1 ont été obtenues par l’auteur de ce mémoire pour l’énumération des polyominos à symétries près.

Les minimaux plus un sont aussi les polyominos d’index 1 et ils sont caractérisés par la présence d’un banc. En position horizontale, ces bancs sont inscrits dans un rectangle t x 2 et sont d’aire t+2. De plus, t cellules sont alignées avec un côté horizontal du banc, qu’on appelle le dos ou la base du banc, et les deux autres cellules sont dans les deux coins restants du rectangle. Ces deux cellules forment les pattes du banc. Dans le cas particulier où t égale 2, le banc est un carré et doit être traité séparément, puisqu’il possède  plus de symétries. Les autres bancs, soit ceux où t + 3, sont appelés des bancs non dégénérés. Dans le cas vertical, on parlera d’un banc inscrit dans un 2 x t.

Lemme de Burnside

Le miraculeux «lemme de Burnside », tel que présenté par J.-P. Delahaye , est très utile pour dénombrer les objets à symétries près et aussi ceux à rotations près, comme les polyominos. Bien que ce lemme porte le nom de Burnside, celui-ci ne l’aurait pas découvert. En effet, ce résultat semble avoir été connu et utilisé préalablement par Cauchy et Frobenius . Bref, comme l’énonce J.P. Delahaye  :
« En définitive, personne ne sait qui l’a découvert et énoncé pour la première fois ». Pour corriger cette mauvaise attribution, on lui donne parfois le nom de lemme de Cauchy-Frobenius ou encore de lemme «qui n’est pas de Burnside ». Par contre, ces corrections n’ont pas eu particulièrement de succès et l’appellation « lemme de Burnside» semble être la plus couramment utilisée.

Polyominos non-inscrits

D’abord, que signifie le terme polyomino non-inscrit ? De manière générale, on ne s’intéresse plus à la dimension du rectangle circonscrit, mais uniquement à l’aire du polyomino. Dans le cas des polyominos d’index r non-inscrits et d’aire n, cela se traduit par l’ensemble:
{ polyominos d’index r inscrits dans un rectangle k x blb + k + r – 1 = n } .
Dans ce cas, plutôt que de mentionner que les polyominos sont considérés non-inscrits, on peut simplement parler de polyominos d’index r d’aire n. Par conséquent, les polyominos d’index r inscrits dans un b x k et ceux dans un k x b sont dans le même ensemble puisque leur aire· est égale à b + k + r – 1. Donc, contrairement aux inscrits, il n’est pas nécessaire de traiter de manières différentes les carrés et les rectangles.

Ainsi, pour connaître leur nombre à rotations près, le groupe C4 agira sur cet ensemble tandis que, pour obtenir ceux à symétries près, ce sera plutôt le groupe diédral V4 .

Table des matières

1 Introduction
1.1 Géométrie combinatoire
1.2 Polyominos
1.2.1 Définitions
1.2.2 Un peu d’histoire
1.2.3 Le problème et ses difficultés
1.3 Structure du mémoire
2 Séries génératrices ordinaires
2.1 Introduction
2.2 Opérations sur les séries génératrices
2.3 Comment les construire?
2.3.1 Avec une formule exacte
2.3.2 Avec une récurrence
2.3.3 Avec une équation fonctionnelle
2.3.4 Avec la méthode de la matrice de transfert
3 Polyominos particuliers
3.1 Produit diagonal
3.2 Minimaux
3.2.1 Escaliers
3.2.2 Équerres
3.2.3 Coins minimaux
3.2.4 Minimaux généraux
3.3 Minimaux plus un
3.3.1 Bancs non dégénérés
3.3.2 Bancs 2 x 2
3.3.3 Coins minimaux plus un
3.3.4 Bancs-coins
3.3.5 Minimaux plus un généraux
4 Polyominos d’aire minimale plus deux 
4.1 Caractérisation des polyominos d’index r
4.2 Classification des polyominos d’index 2
4.2.1 Banc x Banc
4.2.2 Premiers inscrits dans un t x 2 ou 2 x t
4.2.3 Grands rectangles
4.2.4 Premiers à quatre feuilles
4.2.5 Bols
4.2.6 Minimaux plus deux généraux
4.3 Séries génératrices des polyominos d’index 2
4.3.1 Banc x Banc
4.3.2 Premiers inscrits dans un t x 2 ou 2 x t
4.3.3 Grands rectangles
4.3.4 Premiers à quatre feuilles
4.3.5 Bols
4.3.6 Minimaux plus deux généraux
5 Polyominos d’index 0 à 2 à rotations près et à symétries près 
5.1 Lemme de Burnside
5.2 Définitions et propriétés
5.2.1 Polyominos inscrits
5.2.2 Polyominos non-inscrits
5.2.3 Conditions pour être g-symétrique, 9 E C4
5.3 Minimaux
5.3.1 Invariants sous une rotation donnée
5.3.2 Invariants sous une réflexion donnée.
5.3.3 À rotations près.
5.3.4 À symétries près
5.4 Minimaux plus un
5.4.1 Invariants sous une rotation donnée
5.4.2 Invariants sous une réflexion donnée
5.4.3 À rotations près
5.4.4 À symétries près
5.5 Minimaux plus deux
5.5.1 Invariants sous une rotation donnée
5.5.2 Invariants sous une réflexion donnée.
5.5.3 À rotations près
5.5.4 À symétries près
6 Polycubes
6.1 Introduction
6.2 Contenus ou inscrits dans un prisme 2 x 2 x h
6.2.1 Matrice de transfert des polycubes 2 x 2 x h
6.2.2 Séries génératrices des polycubes 2 x 2 x h
6.2.3 Généraliser pour les polycubes b x k x h ?
7 Conclusion

Télécharger le rapport complet