Battaglino, Daniela
[Verfasser:in]
;
Nice
[Mitwirkende:r];
Università degli studi (Sienne, Italie)
[Mitwirkende:r];
Fédou, Jean-Marc
[Mitwirkende:r];
Rinaldi, Simone
[Mitwirkende:r]
Énumération de polyominos définis en terme d'évitement de motif ou de contraintes de convexité ; Enumeration of polyominoes defined in terms of pattern avoidance or convexity constraints
Titel:
Énumération de polyominos définis en terme d'évitement de motif ou de contraintes de convexité ; Enumeration of polyominoes defined in terms of pattern avoidance or convexity constraints
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Dans cette thèse nous étudions la caractérisation et l'énumération de polyominos définis par des contraintes de convexité et ou d'évitement de motifs. Nous nous intéressons à l'énumération des polyominos k-convexes selon le semi périmètre, qui n'était connue que pour k=1,2. Nous énumérons une sous classe, les polyominos k-parallélogrammes, grâce à une décomposition récursive dont nous déduisons la fonction génératrice qui est rationnelle. Cette fonction génératrice s'exprime à l'aide des polynômes de Fibonacci, ce qui nous permet d'en déduire une bijection avec les arbres planaires ayant une hauteur inférieure ou égale à k+2. Dans la deuxième partie, nous examinons la notion d'évitement de motif, qui a été essentiellement étudiée pour les permutations. Nous introduisons ce concept dans le contexte de matrices de permutations et de polyominos. Nous donnons des définitions analogues à celles données pour les permutations et nous explorons ses propriétés ainsi que celles du poste associé. Ces deux approches peuvent être utilisées pour traiter des problèmes ouverts sur les polyominos ou sur d'autres objets combinatoires. ; In this thesis, we consider the problem of characterising and enumerating sets of polyominoes described in terms of some constraints, defined either by convexity or by pattern containment. We are interested in a well-known subclass of convex polyominoes, the k-convex polyominoes for which the enumeration according to the semi-perimeter is known only for k=1,2. We obtain, from recursive decomposition, the generating function of the class of k-convex parallelogram polyominoes, which turns out to be rational. Noting that this generating function can be expressed in terms of the Fibonacci polynomials, we describe a bijection between the class of k-parallelogram polyominoes and the class of planted planar trees having height less than k+3. In the second part of the thesis we examine the notion of pattern avoidance, which has been extensively studied for permutations. We introduce the concept of pattern ...