Akakpo, Yao Ihébami
(2023).
« Énumération de familles de polyominos inscrits dans un rectangle de largeur fixée et de hauteur variable » Mémoire.
Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en mathématiques.
Fichier(s) associé(s) à ce document :
Résumé
Dans ce mémoire, nous nous intéressons à l’énumération des polyominos et forêts de polyominos inscrits dans un rectangle de largeur et de hauteur quelconques selon des paramètres tels que l’aire, le périmètre, le nombre de feuilles et le nombre de composantes connexes. Plus précisément, soit B un entier naturel non nul et RB la famille des rectangles de largeur B et de hauteur entière. Nous construisons des automates AB et AFB dont les chemins sont en bijection respectivement avec les polyominos et les forêts de polyominos contenus dans les rectangles de RB. Nous construisons les matrices de transition relatives à chacun des automates et les théorèmes garantissant l’inscriptibilité d’un polyomino dans un rectangle de RB. Nous énumérons tous les polyominos et les forêts de polyominos inscrits dans ces types de rectangles. Pour arriver à nos fins, nous établissons plusieurs formules fondamentales et exactes relevant de la combinatoire, notamment les formules permettant les déterminations d’aire, de périmètre, du nombre de feuilles et du nombre de composantes connexes échangés lors d’une transition d’un état à un autre. Nous présentons de façon détaillée les cas B = 2 et B = 3 notamment la génération des matrices de transfert ainsi que les fonctions génératrices associées.
RECHERCHER
PARCOURIR
LIBRE ACCÈS
