Télécharger le fichier original (Mémoire de fin d’études)

Involutions 321 et 312-Interdites

Notons que dans cette section les involutions dans In(321) et dans In(312) ont des simples caract´erisations en terme de chemins de Motzkin etiquet´es. De plus les r´esultats de ces caract´erisations seront utilis´es dans certaines d´emonstrations ult´erieures. Proposition 3.5. Soit σ ∈ In (n ≥ 2) et σ connexe. Si σ ∈ In(321), alors σ est sans point fixe. Preuve. Soit σ ∈ In(321) (n ≥ 2). Supposons qu’il existe i ∈ [n] tel que σ(i) = i. Comme σ connexe, alors pour tout 1 ≤ i < n, il existe j ≤ i tel que σ(j) > i. Par suite, σ contient une sous-suite σ(j) i j qui est de type 321.
Proposition 3.6. Soit σ = σ0 ⊕ σ00 ∈ In. Alors σ est 321-interdite si et seulement si σ0 et σ00 sont 321-interdites.
Preuve. Si σ est 321-interdite, il est imm´ediat que σ0 et σ00 sont 321-interdites. R´eciproquement, soit i1 < i2 < i3 et |σ0| = j. Si i1 > j (resp. i3 ≤ j), alors σ(i1) σ(i2) σ(i3) est une sous-suite de σ00 (resp. σ0). Elle n’est donc pas de type 321. Supposons que i1 ≤ j et i3 > j. Par hypoth`ese, on a σ(i1) ≤ j et σ(i3) > j. Il s’ensuit que σ(i1) σ(i2) σ(i3) n’est pas de type 321 Par cons´equent, σ est 321-interdite. Proposition 3.7. Soit σ ∈ In (n ≥ 2), σ connexe et Φ(σ) = (M, λ). Alors M est irr´eductible et σ ∈ In(321) si et seulement si λ est unitaire et M sans pas horizontal.
Preuve. Supposons que σ ∈ In(321). La proposition 3.5 signifie que M est sans pas horizontal.
D’autre part, comme In(321) ⊂ In(4321), alors le th´eor`eme 3.4 implique que λ est unitaire.
R´eciproquement, supposons que λ unitaire et M sans pas horizontal, σ n’a donc pas de point fixe.
Supposons que σ ∈/ In(321), ∃i1 < i2 < i3 tels que σ(i1) > σ(i2) > σ(i3).
Le th´eor`eme 3.4 implique que σ ∈ In(4321) et par suite, d’apr`es la proposition 3.3,∀i ≤ n, σ(i) < i ⇒ ∀j ≤ σ(i), σ(j) ≤ i .
En faisant la mˆeme d´emonstration que le th´eor`eme 3.4, on a σ(i2) = i2 en contra-diction avec σ sans point fixe.  Corollaire 3.8. Soient σ ∈ In et Φ(σ) = (M, λ). Alors σ est 321-interdite si et seulement si λ est une ´etiquette unitaire et tous les pas horizontaux de M sont de hauteur nulle.
Preuve. On suppose que σ non connexe, alors elle admet une d´ecomposition unique σ = α1 ⊕ α2 ⊕ . . . ⊕ αk o`u les αi sont connexes.
D’apr`es la proposition 3.6, σ est 321-interdite si et seulement si les αi sont 321-interdites. Alors
Si |αi| ≥ 2, on a trouv´e dans la proposition 3.7 que si Φ(αi) = (M(i), λ(i)), alors αi est 321-interdite si et seulement si λ(i) est une ´etiquette unitaire et M(i) est un chemin de Dyck. Si |αi| = 1, il est ´evident que Φ(αi) = (H, λ1), o`u H est un chemin de Motzkin form´e par un pas horizontal et λ1 = 0 une ´etiquette unitaire.
Dans tout le cas, M a deux types de composantes irr´eductibles, a` savoir, sous-chemin de Dyck ou sous-chemin de Motzkin form´e par un pas horizontal. D’o`u le r´esultat. Proposition 3.9. Soit σ = σ0 ⊕ σ00 ∈ In. Alors σ est 312-interdite si et seulement si σ0 et σ00 sont 312-interdites. Preuve. Si σ est 312-interdite, il est imm´ediat que σ0 et σ00 sont 312-interdites. R´eciproquement, soit i1 < i2 < i3 et |σ0| = j. Si i1 > j (resp. i3 ≤ j), alors σ(i1) σ(i2) σ(i3) est une sous-suite de σ00 (resp. σ0).
Elle n’est donc pas de type 312. Supposons que i1 ≤ j et i3 > j. Par hypoth`ese, on a σ(i1) ≤ j et σ(i3) > j.
Il s’ensuit que σ(i1) σ(i2) σ(i3) n’est pas de type 312
Par cons´equent, σ est 312-interdite.
Proposition 3.10. Soit σ ∈ In(312) (n ≥ 2) et σ connexe et i < n. Alors (i.) σ(1) = n
(ii.) Si i < j, alors σ(i) > σ(j).
Preuve. (i.) Soit j > 1 tel que σ(j) = n. Comme j > 1, alors j − 1 ≤ 1. De plus σ connexe, alors il existe i ≤ j − 1, σ(i) > j − 1. Donc σ(i) ≥ j comme σ(j) = n, alors σ(i) > j et σ(i) 6= n.
On a j < σ(i) < n et n = σ(j) > σ(σ(i)) = i < σ(n) = j, n i j est donc une sous-suite de σ de type 312. Donc j = 1.
(ii.) Si σ(i) ≤ σ(j), alors σ(i) < σ(j) car i < j, c’est impossible si i = 1 car σ(1) = n. Donc i ≥ 2 et par suite σ(1) σ(i) σ(j) est de type 312. On a n´ec´essairement σ(i) > σ(j).
Corollaire 3.11. Si σ ∈ In(312) et σ connexe, alors σ(i) = n − i + 1 et r´eciproque-ment. En effet, on a σ(1) > σ(2) > σ(3) > . . . > σ(n).
Proposition 3.12. Soient σ ∈ In (n ≥ 2), σ connexe et Φ(σ) = (M, λ). Si σ est 312-interdite, alors M est de type UaHDa ou UaDa.
Preuve. Soit M = m1m2 . . . mn, mi = H si et seulement si n − i + 1 = i.
Ainsi, si n pair, il n’y a pas de pas horizontal et M est donc de la forme M = UaDa. Si n est impaire, posons io = n+12 . Alors mio = H et
– ∀ i < io, σ(i) > σ(io) = io > i. Donc mi = U ∀ i < io
– ∀ i > io, σ(i) < σ(io) = io < i. Donc mi = D ∀ i > io
M est donc du type UaHDa.
Proposition 3.13. Soit σ ∈ In(312) et σ connexe. Si σ(i) < j < i, alors σ(j) < i.
Preuve. Cette proposition r´esulte du corollaire 3.11.
Proposition 3.14. Soient σ ∈ In (n ≥ 2), σ connexe et Φ(σ) = (M, λ). Alors σ est 312-interdite si et seulement si λ est maximale et M est de type UaHDa ou UaDa.
Preuve. Supposons d’abord que σ ∈ In(312). D’apr`es la proposition 3.12, M est de type UaHDa ou UaDa. De plus, la proposition 3.13 implique que λi = |{j < i/σ(j) ≥ i}| = hi(M). R´eciproquement, supposons que M soit du type UaHDa ou UaDa et λ maximale (i) M = UaHDa : on a
– ∀ j ≤ a, σ(j) > j,
– ∀ j > a + 1, σ(j) < j,
– σ(a + 1) = a + 1.
Par it´eration, ∀ j ≤ a, σ(j) > a + 1 (et par suite ∀ j > a + 1, σ(j) ≤ a) Ainsi σ(a + 2) ≤ a Or λ maximale, alors λa+2 = |{j ≤ σ(a + 2)/σ(j) ≥ a + 2}| = ha+2 = a.
Donc σ(a + 2) = a.
De mˆeme, λa+3 = |{j ≤ σ(a + 3)/σ(j) ≥ a + 3}| = ha+3 = a − 1, alors σ(a + 3) = a − 1 et ainsi de suite.
Il en r´esulte que ∀ j ≥ 2, σ(a + j) = a + 2 − j
comme σ(a + 1) = a + 1, alors ∀ i ∈ [n] , σ(i) = n + 1 − i (n = 2a + 1). (ii) M = UaDa : on a
– σ(j) > j pour tout j ≤ a,
– σ(j) < j pour tout j > a
Comme pr´ec´edemment, on a σ(a + 1) = a, σ(a + 2) = a − 1 et ainsi de suite, on obtient : ∀ i ∈ [n] (n = 2a), σ(i) = n + 1 − i.
D’apr`es le corollaire 3.11, σ ∈ In(312).
Corollaire 3.15. Soient σ ∈ In et Φ(σ) = (M, λ). Alors σ est 312-interdite si et seulement si λ est maximale et chaque composante irr´eductible de M est de type H, UaHDa ou UaDa.
Preuve. On consid`ere que σ non connexe, alors elle admet une d´ecomposition unique σ = α1 ⊕ α2 ⊕ . . . ⊕ αk o`u les αi sont connexes.
D’apr`es la proposition 3.9, σ est 312-interdite si et seulement si les αi sont 312-interdites. Alors
Si |αi| ≥ 2, on a trouv´e dans la preuve de la proposition 3.7 que si Φ(αi) = (M(i), λ(i)), alors αi est 312-interdite si et seulement si λ(i) est une ´etiquette maxi-male et M(i) est de type UaHDa ou UaDa.
Si |αi| = 1, il est ´evident que Φ(αi) = (H, λ1), o`u H est un chemin de Motzkin form´e par un pas horizontal et λ1 = 0 une ´etiquette maximale. Dans tous les cas, on a le r´esultat.

Table des matières

Remerciements
Introduction
1. Rappels et pr´eliminaires
1.1 Permutations
1.2 Permutations `a motifs interdits
1.3 Chemins de Motzkin
1.3.1 Nombres de Motzkin
1.3.2 Chemins de Dyck et nombres de Catalan
2. Involutions et chemins de Motzkin ´etiquet´es
2.1 Chemins de Motzkin ´etiquet´es
2.2 Bijection entre Involutions et les chemins de Motzkin ´etiquet´es
2.3 Correspondance
3. Involutions 4321-Interdites et Chemins de Motzkin
3.1 Involutions 321 et 312-Interdites
3.2 Involutions excluant 4321 et un autre motif dans S3
4. Involutions 3412-Interdites et Chemins de Motzkin
4.1 Involutions 3412-Interdites
4.2 Bijection entre In(3412) et les chemins de Motzkin
4.3 Fractions continues
4.3.1 Involutions excluant 3412 et un autre motif dans S3
4.4 Fonctions g´en´eratrices
5. D’autres restrictions sur les involutions
5.1 Involutions sans point fixe
5.2 Involutions centrosym´etriques
5.3 Quelques r´esultats d’´enum´erations sur CIn
Annexe
Conclusion
Bibliographie

Télécharger le rapport complet