Soutenance mémoire
Introduction à des méthodes combinatoires
L’art de la citation est l’art de ceux qui ne savent pas réfléchir par eux-mêmes. – Voltaire.
Dans ce chapitre, nous effleurons le domaine des équations fonctionnelles, présentons les concepts de base des polyominos en commençant par leur définition et partons à la découverte des séries génératrices avec un intérêt particulier porté à leur interprétation.
Les équations fonctionnelles
Les équations fonctionnelles sont fort utilisées en combinatoire. Elles permettent de faciliter d’une façon relativement simple le calcul de séries génératrices.
Une équation fonctionnelle est une équation dont l’inconnue est une fonction.
Lorsque nous sommes confrontés à une équation fonctionnelle, l’exercice consiste à déterminer toutes les fonctions qui en sont solutions. Dans le cadre des polyominos, nous ne faisons pas appel à tous les outils existants pour de telles résolutions car souvent il ne s’agit que d’isoler la fonction dans une équation du premier degré. Par exemple, nous allons rencontrer au chapitre 3 l’équation fonctionnelle
Polyominos et amis
Là où l’humour est partagé, l’amitié n’est pas loin. – Grégoire Lacroix.
Commençons par donner une définition générale de polyomino dans le ‘plan, valide quel que soit le treillis régulier.
Un polyomino à deux dimensions (2D) est un ensemble de carrés unitaires, appelés cellules, connectés par les côtés dans un treillis régulier (figure 1.1).
Ils sont considérés à translation près. L’aire d’un polyomino est le nombre de cellules le constituant.
Nous ne nous intéressons qu’aux amalgames de cellules carrées dont les côtés sont de longueur unitaire. Un polyomino peut être vu comme un graphe avec ses cellules carrées tenant le rôle des sommets et les connexions par les arêtes celui des arêtes du graphe (figure 1.2). Nous empruntons donc du vocabulaire de la théorie des graphes lorsque cela s’avère pertinent
Polyominos serpents
Compter le nombre de polyominos d’aire n se révèle très difficile et est encore un problème ouvert exploré par divers groupes de recherche en combinatoire. Plutôt que de rester coincés et de maugréer dans notre coin, décidons d’un plan d’action et utilisons une technique bien connue des militaires et des informaticiens, « Divide ut regnes ». Dans notre contexte, cela signifie partitionner l’ensemble des polyominos en classes dont nous espérons pouvoir calculer la cardinalité. Si c’est le cas, il ne reste alors qu’à additionner tous ces résultats afin de déterminer la taille de l’ensemble de départ. Ceci nous mène vers les polyominos serpents dont la définition requiert la notion de degré d’une cellule.
Le degré d’une cellule d’un polyomino est son nombre de connexions par les côtés avec les autres cellules du polyomino.
Exemple. À la figure 1.1, le premier polyomino possède deux cellules de degré 1, quatre cellules de degré 2 et deux cellules de degré 3. Le deuxième contient une cellule de degré 1, sept cellules de degré 2 et une de degré 3. Le troisième a deux cellules de degré 1, les autres sont de degré 2. Le polyomino à droite, Dave de son petit nom, possède quatre cellules de degré’I, dix cellules de degré 2, beaucoup de cellules de degré 3 et encore plus de degré 4, qui est le degré maximal qu’une cellule admet.
Un polyomino serpent de longueur n, appelé un serpent, est un polyomino possédant n cellules, sans cycle et dont toutes les cellules sont au plus de degré 2.
Un serpent orienté de longueur n 2: 2 est un serpent avec une queue et une tête, identifiées parmi les deux seules cellules de degré 1, dont l’orientation est celle de la queue vers la tête. Sinon, il est dit non orienté.
Partons du principe que tout serpent est non orienté tant que nous ne le précisons pas.
Les serpents orientés sont des objets similaires aux chemins auto-évitants (Bousquet-Mélou [6]) mais, à notre connaissance il n’existe pas à ce jour de bijection entre ces deux ensembles.
Un chemin auto-évitant, abrévié SAW pour self-avoiding walk, est un chemin dans un treillis ne passant pas deux fois par le même sommet.
Cette correspondance n’est pas inversible car le nombre minimum de cellules requises pour former un U dans un serpent est supérieur de un au nombre minimum de sommets dans un U d’un chemin auto-évitant (figure 1.4). Par un U nous entendons un serpent, ou un chemin auto-évitant, allant dans une certaine direction, disons l’est, puis tournant dans une direction= perpendiculaire, disons le nord, et retournant vers l’ouest, la direction opposée à la direction initiale. Bien sûr, la direction de départ du U est arbitraire.
Notre classification des serpents suit de très près celle des chemins auto-évitants présentée dans [6]. Néanmoins, les serpents possèdent une propriété géométrique que les chemins autoévitants ne peuvent avoir: deux cellules d’un serpent séparées par au moins deux cellules peuvent se toucher en un coin.
Lorsqu’un serpent ne possède pas de paire de cellules se touchant par les coins, nous disons qu’il est kiss-free (figure 1.5)
Polyominos serpents partiellement dirigés
Et si nous continuons de diviser pour régner mais cette fois en partant de l’ensemble des serpents? Nous trouvons les serpents partiellement dirigés.
Un polyomino serpent est un serpent partiellement dirigé (SPD) vers le nord lorsque, en démarrant de la queue, chaque nouvelle cellule est ajoutée dans une des trois directions nord (N), est (E) ou ouest (0) avec la contrainte nécessaire qu’un pas E ne peut suivre immédiatemment un pas 0 et vice-versa.
Polyominos ensemblistes versus polyominos dynamiques
Nous avons défini ce qu’est un polyomino (page 2) . Il s’agit d’une description ensembliste, de même pour la définition d’un serpent (page 4). Par contre, la définition d’un SPD (page 5) est une description dynamique. Clarifions ces deux points de vue. La description ensembliste dit que le polyomino est un ensemble connexe de cellules respectant certaines contraintes comme l’acyclicité et le degré des cellules pour le serpent. La description dynamique, quant à elle, voit le SPD comme un chemi~ acyclique de cellules qui se construit en ajoutant une cellule à la fois selon des contraintes de direction. Dans cette vision, le SPD est nécessairement orienté. Pour nous, si le sens de lecture n’est pas précisé, il est de bas en haut. Cette dernière description se généralise mal aux polyominos car il n’est pas toujours possible de le construire cellule après cellule en suivant un chemin auto-évitant – qui ne s’intersecte pas avec lui-même (comme la pioche de la figure 1.7).
Le point de vue des polyominos
Nous utilisons beaucoup les séries génératrices pour l’énumération des polyominos. En vertu de quoi, voici un petit aperçu de ce qui nous attend. Nous allons déterminer les séries génératrices des piliers verticaux et horizontaux, des serpents sans paire de pas N (nord) consécutifs, des SPD et des serpents minimaux dans un rectangle b x h. Tout ce beau monde permet d’introduire diverses opérations sur les séries génératrices.
SPD sans paire de pas N consécutifs
Intéressons-nous aux SPD vers le nord sans paire de pas N consécutifs (figure 1.11). Il est clair qu’ils n’admettent soit que des pas N et E soit que des pas N et O. En effet, pour avoir des pas E et 0, il faut deux pas N consécutifs. Les SPD sans paire de pas N consécutifs et avec des pas E sont notés SNEE – serpents Nord-Est-Est – et ceux avec des pas 0 , SNOO – serpents Nord-Ouest-Ouest.
Nous désirons déterminer le nombre de SNEE de longueur n. Plaçons une première cellule.
Pour placer la deuxième, nous avons deux directions possibles, au nord ou à l’est de la première. Si elle est placée au nord (à gauche figure 1.12 où le rectangle symbolise n’importe quel SNEE) , nous n’avons de choix pour placer la troisième cellule que d’aller vers l’est car nous ne pouvons faire deux pas N consécutifs. Si elle est placée à l’est (à droite figure 1.12), de nouveau s’offrent deux possibilités, au nord et à l’est de la deuxième cellule. Donc, si nous voulons construire un SNEE de longueur n, nous avons deux choix au départ de la première cellule, aller vers le nord ou aller vers l’est. Le premier nous amène, après les deux premières cellules, à un SNEE de longueur n – 2 commençant à l’est de la deuxième cellule. Il y a snee (n – 2) choix de serpents Nord-Est-Est. Au second choix, la seconde cellule placée à l’est de la première démarre un SNEE de longueur n – 1. Nous avons snee(n – 1) choix de serpents Nord-Est-Est. Ainsi il y a autant de SNEE de longueur n que la somme du nombre de SNEE de longueur n – 2 et de longueur n – 1 :
SPD de longueur n
La prochaine étape est la construction de la série génératrice des SPD de longueur n. Pour faire un lien avec les serpents Nord-Est-Est, nous pouvons dire qu’un SPD possède soit au moins une paire de pas N consécutifs, soit aucune paire de pas N consécutifs, auquel cas il est un SNEE ou un SNOO. Si un SPD admet au moins une paire de pas N consécutifs, en particulier il y en a une dernière lorsque nous le parcourons. Après celle-ci, il n’yen a plus, nous avons donc un SNEE ou un SNOO. Un SPD ayant deux pas N consécutifs est ainsi constitué d’un SPD quelconque suivi d’une dernière paire de pas N consécutifs et d’un SNEE ou d’un SNOO (figure 1.16 où le SPD quelconque est en rouge, la dernière paire de pas N consécutifs est en bleu et le SNEE est en vert).
|
Table des matières
Table des figures
Liste des tableaux
1 Introduction à des méthodes combinatoires
1.1 Les équations fonctionnelles
1.2 Polyominos et amis
1.3 Les séries génératrices
1.4 Le point de vue des polyominos
2 Combinatoire des polyominos serpents partiellement dirigés
2.1 Serpents partiellement dirigés
2.2 Les serpents partiellement dirigés inscrits
2.3 Une bijection
3 Des serpents un peu plus que minimaux
3.1 Serpents d’index 1
3.2 Serpents d’index 2
3.3 Serpents d’index 3
4 Les serpents partiellement dirigés d’index r
4.1 Construction d’un codage des SPD d’index r
4.2 Présentation de l’algorithme
5 Combinatoire des chemins auto-évitants
5.1 Les chemins partiellement dirigés
5.2 Serpents et chemins auto-évitants d’index 0
5.3 Serpents et chemins auto-évitants d’index 1
5.4 Serpents et chemins auto-évitants d’index 2
5.5 SPD et CPD d’index 3
5.6 SPD et CPD d’index r
6 Serpents inscrits et serpents maximaux
6.1 Serpents inscrits dans un 2 x h
6.2 Serpents inscrits dans un 3 x h
6.3 Serpents inscrits de longueur maximale
Bibliographie
Télécharger le rapport complet
