Évitement de motifs consécutifs émergents

Informations de base

• ID de l'article : 2511.02442
• Titre : Évitement de motifs consécutifs émergents
• Auteurs : Nathanaël Hassler, Sergey Kirgizov (Université Bourgogne Europe)
• Classification : math.CO (mathématiques combinatoires), cs.DM (mathématiques discrètes)
• Date de publication : 5 novembre 2025 (prépublication arXiv)
• Lien de l'article : https://arxiv.org/abs/2511.02442

Résumé

Cet article étudie le problème de la popularité asymptotique, c'est-à-dire la probabilité limite de trouver un motif consécutif donné à une position aléatoire dans une permutation aléatoire, parmi 18 classes de permutations évitant au moins deux motifs consécutifs de longueur 3. L'étude montre que pour 10 classes de permutations, cette popularité peut être déduite directement de la structure des permutations. En combinant des méthodes analytiques et bijectives, les auteurs étudient en détail deux cas plus complexes. Le problème reste ouvert pour 5 classes de permutations.

Contexte et motivation de la recherche

Problème de recherche

Cet article étudie le comportement asymptotique de l'évitement de motifs consécutifs dans les permutations. Plus précisément :

• Étant donné une classe de permutations évitant certains motifs consécutifs de longueur 3
• Étudier la popularité asymptotique d'autres motifs non évités dans ces classes
• La popularité asymptotique est définie comme : la limite, lorsque n tend vers l'infini, de la probabilité de trouver un motif spécifique p à une position aléatoire dans une permutation aléatoire de taille n

Importance du problème

1. Signification théorique : Révèle un « fait fascinant » — certains motifs disparaissent au sens asymptotique (la probabilité tend vers 0)
2. Extension de problèmes classiques : Étend les travaux de Bóna et Homberger sur les motifs classiques (non consécutifs) aux motifs consécutifs
3. Connexion entre différents objets combinatoires : Établit via des bijections des liens entre les permutations et d'autres structures combinatoires (chemins de Dyck, involutions)

Limitations des méthodes existantes

• Les travaux de Bóna et Homberger ne concernent que les motifs classiques (non consécutifs)
• Bien que Kitaev et Mansour aient fourni l'énumération des 18 classes de permutations évitantes, ils n'ont pas étudié la popularité asymptotique
• Absence d'approche systématique pour traiter les 18 classes de permutations

Motivation de la recherche

Provient de l'étude de la Classe 7 par Baril, Burstein et Kirgizov dans 4, qui utilisent une bijection entre les permutations et les chemins de Dyck dispersés pour transférer les motifs, ce qui a inspiré le travail présent.

Contributions principales

1. Étude systématique des 18 classes de permutations : Analyse complète des classes de permutations évitant au moins deux motifs consécutifs de longueur 3 proposées par Kitaev-Mansour
2. Résolution de 10 classes simples : Pour 10 classes de permutations (Classes 1,2,3,5,6,8,9,16,18 et la Classe 7 déjà résolue), déduction directe de la popularité asymptotique à partir de la structure
3. Analyse approfondie de 2 classes complexes :
   • Classe 11 (Av(123,132,321)) : Combinaison de méthodes analytiques et combinatoires
   • Classe 17 (Av(123,132)) : Utilisation de la transformation de Foata et des bijections d'involutions
4. Formulation de problèmes ouverts : Identification claire de 5 classes de permutations (Classes 10,12,13,14,15) pour lesquelles le problème reste ouvert
5. Découverte du phénomène de disparition de motifs : Preuve que dans certaines classes, la popularité asymptotique de motifs spécifiques est nulle (disparition de motifs)

Explication détaillée des méthodes

Définition de la tâche

Entrée :

• Classe de permutations $A_n = \text{Av}_n(p_1, \ldots, p_m)$, évitant les motifs consécutifs $p_1, \ldots, p_m$
• Motif consécutif de longueur 3 non évité $p$

Sortie :

• Popularité asymptotique $\text{pop}_A(p) := \lim_{n \to \infty} \frac{p_n^A}{n|A_n|}$

où $p_n^A$ est le nombre total d'occurrences du motif p dans toutes les permutations de $A_n$.

Concepts fondamentaux

Motif consécutif : Une permutation π contient un motif consécutif p s'il existe une sous-séquence consécutive $a_i a_{i+1} \cdots a_{i+r-1}$ qui est isomorphe en ordre à p.

Opérations de symétrie :

• Inversion R(π) : permutation lue en sens inverse
• Complément C(π) : remplacement de chaque élément a par n+1-a
• Ces opérations préservent les occurrences de motifs consécutifs

Classification des méthodes

1. Méthode d'analyse structurelle (classes simples)

Pour les classes de permutations de structure simple, déduction directe :

Classe 1 (Av(123,132,312,321)) :

• Contient seulement 2 permutations alternantes
• La symétrie donne directement pop(213) = pop(231) = 1/2

Classe 18 (Av(132,231)) :

• Forme des permutations : $a_1 \cdots a_k 1 b_1 \cdots b_{n-k-1}$
• où $a_1 \cdots a_k$ est décroissante et $b_1 \cdots b_{n-k-1}$ est croissante
• Comptage : nombre d'occurrences de 321 = $\sum_{k=1}^{n-1} \binom{n-1}{k}(k-1) = (n-1) \cdot 2^{n-2} - 2^{n-1} + 1$
• Conclusion : pop₁₈(321) = pop₁₈(123) = 1/2, pop₁₈(213) = pop₁₈(312) = 0

Classe 16 (Av(123,321)) :

• Utilisation de la symétrie : la classe est stable sous R, C, R∘C
• Les quatre motifs non évités correspondent un à un via ces bijections
• Conclusion : pop₁₆(132) = pop₁₆(231) = pop₁₆(312) = pop₁₆(213) = 1/4

2. Méthode analytique (Classe 11)

Classe 11 (Av(123,132,321)) :

Étape 1 : Analyse structurelle

• Les permutations sont alternantes ou anti-alternantes
• La lecture de droite à gauche en sautant un élément donne une séquence croissante
• Division en deux sous-ensembles : $A_n^r$ (dernier élément égal à 1) et $A_n^l$ (avant-dernier élément égal à 1)
• $|A_n^r| = (n-2)!!$, $|A_n^l| = (n-1)!!$

Étape 2 : Comptage du motif 231 Observation directe de la structure positionnelle : $231_n = (n-1)!! \left\lceil \frac{n-3}{2} \right\rceil + (n-2)!! \left\lceil \frac{n-2}{2} \right\rceil$

Étape 3 : Récurrence du motif 312 Établissement d'une relation de récurrence (Lemme 3.2) :

• $312_n^r = 312_{n-1}^l$
• $312_n^l = (n-1)(312_{n-2}^l + (n-3)!!) - (n-5)!! \frac{(n-3)(n-2)}{2}$

Étape 4 : Résolution par fonction génératrice En posant $u_n := \frac{312_n^l}{(n-1)!!}$, on obtient la fonction génératrice : $f(z) = \frac{z(2(z-1)\ln(1-z) + z^3 + 3z^2 - 2z)}{4(1-z)^2(1+z)}$

Conclusion : $312_n^l = (n-1)!! \left( \frac{(-1)^{n-1} + n - 3}{4} + \frac{1}{2} \sum_{\substack{k=1\\k \neq n \bmod 2}}^{n-1} \frac{1}{k} \right)$

Résultats asymptotiques : pop₁₁(231) = 1/2, pop₁₁(213) = pop₁₁(312) = 1/4

3. Méthode bijective (Classe 17)

Classe 17 (Av(123,132)) :

Outil fondamental : Transformation de Foata Claesson a prouvé que la transformation de Foata établit une bijection entre Av_n(123,132) et l'ensemble des involutions I_n.

Forme standard :

1. Chaque cycle commence par son élément minimal
2. Les cycles sont ordonnés par leurs éléments minimaux en ordre décroissant
3. Suppression des parenthèses donne la permutation

Correspondance des motifs (Tableau 2) :

• 321 dans Av(123,132) ↔ (c)(b)(a) ou formes contenant des points fixes dans I_n
• 231 ↔ (bc)(a⋆) (sans points fixes)
• 213 ↔ (⋆b)(ac) (sans points fixes)
• 312 ↔ (⋆c)(ab) (sans points fixes)

Lemmes clés :

• Lemme 4.2 : Comportement asymptotique du nombre de points fixes $\frac{\text{fp}_n}{|I_n|} \sim_{n \to \infty} \sqrt{n}$ Ceci montre que les points fixes sont rares dans les involutions et peuvent être négligés pour les motifs les contenant.
• Lemme 4.3 : Seul le calcul des motifs sans points fixes est nécessaire

Analyse du motif 231 (Proposition 4.4) :

• Le motif α = (bc)(a⋆) correspond à deux transpositions consécutives
• Chaque paire de transpositions consécutives produit exactement un α et un β ou γ
• Conclusion : pop₁₇(231) = 1/2, pop₁₇(321) = 0

Analyse du motif 213 (la plus complexe) :

• Correspond au motif 2314 dans Av(123,132)
• Établissement d'une relation de récurrence (Lemme 4.5) : $2314_n = 2314_{n-1} + (n-1) \cdot 2314_{n-2} + \binom{n-2}{2}|I_{n-4}|$
• Fonction génératrice exponentielle (Proposition 4.6) : $G(z) = \frac{e^{\frac{(1+z)^2}{2}}}{2} \int_0^z e^{-\frac{(1+t)^2}{2}} dt + \frac{z(z-2)e^{z+\frac{z^2}{2}}}{4}$
• Analyse asymptotique :
  • Premier terme : $[z^n]z(z-2)e^{z+\frac{z^2}{2}} \sim \frac{n|I_n|}{n!}$
  • Deuxième terme : utilisation de la méthode du col pour prouver $[z^n]F(z) = o(\frac{n|I_n|}{n!})$
  • Choix du point col $\zeta = \sqrt{n}$ pour obtenir une borne suffisante

Conclusion : pop₁₇(312) = pop₁₇(213) = 1/4

Points d'innovation technique

1. Approche mixte : Première étude systématique combinant analyse structurelle, fonctions génératrices et méthodes bijectives pour la popularité asymptotique des motifs consécutifs
2. Application innovante de la méthode du col : Dans la Classe 17, simplification de l'analyse en choisissant un point col approché $\zeta = \sqrt{n}$ plutôt qu'un point col exact
3. Transfert de motifs : Utilisation de la transformation de Foata pour convertir les problèmes de motifs dans les permutations en problèmes de structure de cycles dans les involutions
4. Rareté des points fixes : Preuve que la croissance $O(\sqrt{n})$ du nombre de points fixes les rend négligeables dans l'analyse asymptotique

Configuration expérimentale

Sources de données

Cet article est un travail purement théorique, basé principalement sur :

• Les résultats d'énumération de Kitaev et Mansour pour les 18 classes de permutations
• Les formules de fonctions génératrices et d'asymptotique connues

Méthodes de vérification

Bien qu'il n'y ait pas d'expériences au sens traditionnel, les auteurs mentionnent :

• Des expériences numériques sur les Classes 10,12,13,14,15
• Une vitesse de convergence très faible, rendant difficile la formation de conjectures fiables

Résultats expérimentaux

Résultats principaux (résumés dans le Tableau 1)

Découvertes clés

1. Phénomène de disparition de motifs :
   • Dans plusieurs classes, la popularité asymptotique de certains motifs est nulle (par ex., 231 dans la Classe 2, 321 dans la Classe 17)
   • C'est un « fait plutôt fascinant »
2. Résultats de symétrie :
   • La Classe 16 exhibe une symétrie quadruple parfaite (tous les quatre motifs ont une popularité de 1/4)
   • De nombreuses classes exhibent une distribution symétrique de 1/2
3. Popularité rationnelle :
   • Dans tous les cas résolus, la popularité est un nombre rationnel (0, 1/4, 1/2, 1)
   • Question ouverte : existe-t-il une popularité irrationnelle ?

Travaux connexes

Évitement de motifs classiques

• Bóna & Homberger 1,2,3 : Étude des classes de permutations évitant un motif classique de longueur 3
  • Preuve que dans Av(123) et Av(132), la popularité asymptotique de 321 est 1
• Janson 15,16 : Étude de la distribution limite des motifs classiques de longueur 3 dans Av(132) et Av(321)

Recherche sur les motifs consécutifs

• Kitaev & Mansour 17,18,19 : Énumération des 18 classes de permutations évitantes (fondation de cet article)
• Elizalde & Noy 9,10 :
  • Méthodes basées sur les arbres croissants et les produits en boîte
  • Adaptation de la méthode des clusters de Goulden-Jackson

Bijections et transfert de motifs

• Barnabei, Bonetti, Silimbani 5 :
  • Étude de la distribution conjointe des motifs consécutifs de taille 3 dans Av(312)
  • Utilisation de la bijection de Krattenthaler et de l'involution de Deutsch
• Baril, Burstein, Kirgizov 4 :
  • Étude des mots faro et des statistiques de motifs dans les permutations
  • Prédécesseur direct et source de motivation de cet article

Normalité asymptotique

• Borga 6 : Étude basée sur les arbres générateurs de la normalité asymptotique de l'apparition de motifs consécutifs dans les permutations évitant certains motifs

Conclusion et discussion

Conclusions principales

1. Complétude : Résolution systématique de 13 des 18 classes (10 simples + 2 complexes + 1 existant)
2. Méthodologie : Démonstration de la combinaison efficace des méthodes d'analyse structurelle, de fonctions génératrices et de bijections
3. Intuitions théoriques : Révélation de phénomènes intéressants comme la disparition de motifs et la symétrie

Limitations

1. Travail inachevé : 5 classes de permutations (Classes 10,12,13,14,15) restent ouvertes
2. Difficultés numériques : Ces classes ouvertes ont une vitesse de convergence très faible, rendant difficile la formulation de conjectures par expérience numérique
3. Limitations méthodologiques : Les méthodes existantes semblent insuffisantes pour traiter les cas complexes restants

Directions futures

Les auteurs proposent plusieurs problèmes ouverts dans la Section 5 :

1. Conjecture 5.1 : Si popₐ(p) = 0, alors pour toute sous-classe B évitant p, on a popB(q) = popₐ(q)
   • Ceci est vrai dans les cas résolus
2. Problèmes d'extension :
   • Que se passe-t-il en évitant seulement un motif consécutif de longueur 3 ?
   • Peut-on trouver des ensembles de motifs produisant une popularité asymptotique irrationnelle ?
   • La limite (1.1) existe-t-elle toujours ? Comment caractériser son existence ?
3. Problèmes méthodologiques :
   • Comment résoudre les 5 classes restantes par des méthodes énumératives ou probabilistes ?
   • Existe-t-il un cadre unifié traitant tous les cas ?

Évaluation approfondie

Forces

1. Force systématique :
   • Première étude systématique de la popularité asymptotique pour les 18 classes de permutations
   • Classification claire et méthodologie bien organisée (simple vs complexe)
2. Diversité méthodologique :
   • Application flexible de l'analyse structurelle, des fonctions génératrices, des bijections et de la méthode du col
   • L'analyse de la Classe 17 est particulièrement ingénieuse, montrant l'intégration organique de plusieurs techniques
3. Profondeur théorique :
   • La preuve du Lemme 4.2 sur la rareté des points fixes est élégante
   • La dérivation des fonctions génératrices est rigoureuse (en particulier l'équation différentielle pour la Classe 11)
4. Clarté de la rédaction :
   • Structure bien organisée, progression du simple au complexe
   • Le Tableau 1 fournit un aperçu clair
   • Les figures (Figures 1-2) aident à la compréhension

Faiblesses

1. Complétude :
   • 5 classes non résolues (28% du total)
   • Pas d'analyse approfondie ou de résultats partiels pour ces cas difficiles
2. Support numérique :
   • Bien que des expériences numériques soient mentionnées, aucune donnée concrète n'est présentée
   • Absence d'analyse quantifiée de la vitesse de convergence
3. Vérification de conjectures :
   • La Conjecture 5.1 n'est vérifiée que dans les cas résolus, manquant de preuves plus larges
4. Détails techniques :
   • Le choix du point col $\zeta = \sqrt{n}$ dans la Classe 17 pourrait être mieux motivé
   • Certaines étapes de calcul ont des sauts importants

Influence

1. Contribution théorique :
   • Inaugure l'étude systématique de la popularité asymptotique des motifs consécutifs
   • Fournit une nouvelle perspective à la théorie de l'évitement de motifs
2. Valeur méthodologique :
   • Démontre l'efficacité de la combinaison de plusieurs techniques
   • L'idée de transfert de motifs peut s'appliquer à d'autres structures combinatoires
3. Caractère inspirant :
   • Les problèmes ouverts sont clairs et intéressants
   • Susceptible de stimuler de nouvelles directions de recherche
4. Limitations :
   • Les résultats sont principalement théoriques, sans applications pratiques évidentes
   • La difficulté des problèmes restants peut limiter l'impact à court terme

Scénarios d'application

1. Recherche en mathématiques combinatoires :
   • Théorie des motifs dans les permutations
   • Énumération asymptotique
   • Méthodes des fonctions génératrices
2. Conception d'algorithmes :
   • Génération de permutations avec restrictions
   • Algorithmes de correspondance de motifs
3. Domaines connexes :
   • Peut avoir des implications pour les modèles restreints en physique statistique
   • Connexion aux problèmes d'évitement de motifs en génomique

Références

Références clés :

1. 4 Baril, Burstein, Kirgizov (2021) : Source directe de motivation de cet article
2. 17 Kitaev (2003) : Fondation de l'énumération des 18 classes de permutations
3. 7 Claesson (2001) : Bijection de transformation de Foata (clé pour la Classe 17)
4. 1-3 Bóna & Homberger (2010-2012) : Travaux pionniers sur les motifs classiques
5. 11 Flajolet & Sedgewick (2005) : Référence standard en combinatoire analytique

Évaluation globale : Ceci est un article solide de mathématiques combinatoires qui étudie systématiquement un problème naturel et intéressant. Sur le plan méthodologique, il démontre la combinaison efficace de plusieurs techniques, en particulier l'analyse des Classes 11 et 17 reflète une profonde maîtrise technique. Bien que 5 classes restent non résolues, le travail achevé établit une base solide pour ce domaine. L'article est bien rédigé, les résultats sont intéressants (en particulier le phénomène de disparition de motifs), et les problèmes ouverts proposés sont clairs et stimulants. Pour les chercheurs en mathématiques combinatoires, en particulier ceux travaillant sur la théorie des motifs dans les permutations, c'est un article qui mérite une lecture approfondie.