On a question about pattern avoidance of cyclic permutations

Cet article résout la question ouverte concernant les permutations cycliques évitant le motif décroissant $\delta_k$ et le motif $\tau=1432$ en toutes leurs formes cycliques, en dérivant des formules explicites grâce à une analyse structurelle et au théorème de Dilworth.

L'essentiel

Voici une explication de ce document mathématique, traduite en langage simple et imagé pour un public général.

🎭 Le Grand Jeu des Permutations Cycliques

Imaginez que vous avez un groupe d'amis, numérotés de 1 à $n$. Vous voulez les faire s'asseoir autour d'une table ronde pour former un seul grand cercle (c'est ce qu'on appelle une permutation cyclique).

Dans ce monde mathématique, il y a deux règles du jeu très strictes que ces amis doivent respecter pour ne pas être "interdits" :

1. La Règle de la File d'Attente (Notation linéaire) : Si vous les regardez dans l'ordre où ils sont assis (de gauche à droite), ils ne doivent pas former une file d'attente trop longue et descendante. Par exemple, si vous avez 5 amis, vous ne pouvez pas avoir une séquence où le 5ème ami est plus grand que le 4ème, qui est plus grand que le 3ème, etc., sur une trop grande longueur. C'est ce qu'on appelle éviter le motif "décroissant" ($\delta_k$).
2. La Règle de la Danse (Forme cyclique) : Maintenant, imaginez que vous pouvez faire tourner la table. Peu importe où vous commencez à regarder le cercle, la séquence des amis ne doit jamais former un motif interdit spécifique appelé 1432. C'est comme si une certaine configuration de danse était considérée comme "mauvaise" et qu'elle était interdite sous tous les angles.

🔍 Le Problème Résolu

Des chercheurs précédents (Archer et al.) avaient déjà résolu ce problème pour deux types de danses interdites (1324 et 1342), mais ils étaient bloqués sur le cas 1432. C'était une énigme ouverte : "Combien de façons avons-nous de placer nos amis autour de la table pour respecter les deux règles, si la danse interdite est 1432 ?"

C'est le défi que Zuo-Ru Zhang et Hongkuan Zhao ont relevé dans cet article.

🧩 Les Outils Magiques

Pour résoudre cette énigme, les auteurs ont utilisé deux concepts clés :

• Le Théorème de Dilworth (Le Tri des Cartes) : Imaginez que vous avez un tas de cartes mélangées. Ce théorème dit essentiellement que si vous ne pouvez pas trouver une longue suite de cartes qui descendent (comme 10, 9, 8...), alors vous pouvez organiser tout le tas en un petit nombre de piles où les cartes montent (comme 1, 2, 3...). C'est un outil puissant pour compter les arrangements sans avoir à les lister un par un.
• L'Analyse de Structure (Le Puzzle) : Les auteurs ont découvert que pour éviter la danse interdite "1432", la structure du cercle doit suivre des règles très précises. Par exemple, certains amis doivent être assis dans un ordre strict, comme des pièces d'un puzzle qui ne s'emboîtent que d'une seule façon.

📊 Les Résultats (La Recette Finale)

Après avoir décortiqué la structure de ces cercles, les auteurs ont trouvé des formules mathématiques simples pour compter le nombre de configurations possibles, selon la taille du groupe ($n$) et la longueur de la file d'attente interdite ($k$).

Voici ce qu'ils ont trouvé pour les grands groupes ($n \ge 5$) :

1. Si la file interdite est courte (k=3) : Le nombre de façons possibles suit une courbe qui ressemble à une parabole. C'est un peu comme si le nombre de solutions augmentait avec le carré du nombre d'amis, moins quelques ajustements.
2. Si la file interdite est un peu plus longue (k=4) : Le nombre de solutions suit une formule qui ressemble à une puissance de 2 (comme le nombre de sous-ensembles possibles), moins quelques corrections. C'est beaucoup plus grand que le cas précédent !
3. Si la file interdite est très longue (k=5 ou plus) : La règle de la file d'attente devient presque inutile ! Pourquoi ? Parce que la règle de la danse (éviter 1432) est si stricte qu'elle empêche naturellement de former de longues files descendantes. Dans ce cas, le nombre de solutions est simplement le nombre total de cercles qui respectent la règle de la danse, moins quelques exceptions très rares.

💡 En Résumé

Ce papier est comme la solution d'un casse-tête complexe. Les auteurs ont prouvé que même si les règles semblent arbitraires (éviter une file descendante et une danse spécifique), elles créent une structure très rigide.

Grâce à leur analyse, nous savons maintenant exactement combien de façons il existe d'organiser un groupe d'amis autour d'une table ronde pour qu'ils respectent ces deux règles bizarres. C'est une victoire pour la théorie des nombres et la combinatoire, transformant une question ouverte ("Combien y a-t-il ?") en une réponse précise et calculable.

L'analogie finale : C'est comme si vous aviez un jeu de Lego avec des règles de construction très strictes. Avant, on ne savait pas combien de châteaux différents on pouvait construire. Maintenant, grâce à cette étude, on a la formule exacte pour le nombre de châteaux possibles, peu importe la taille de votre boîte de Lego !

Résumé technique

Voici un résumé technique détaillé du papier de recherche intitulé « On a question about pattern avoidance of cyclic permutations » par Zuo-Ru Zhang et Hongkuan Zhao, rédigé en français.

1. Problématique et Contexte

L'article s'inscrit dans le domaine de la combinatoire des permutations, plus spécifiquement dans l'étude de l'évitement de motifs (pattern avoidance) au sein des permutations cycliques.

• Définitions clés :

  • Une permutation $\pi \in S_n$ est dite cyclique si elle est constituée d'un unique cycle de longueur $n$.
  • L'auteur considère deux représentations : la notation linéaire (une ligne) et la forme cyclique standard $C(\pi)$, qui est la représentation cyclique commençant par 1.
  • Le problème porte sur les permutations qui évitent simultanément :
    1. Le motif décroissant $\delta_k = k(k-1)\dots 21$ dans la notation linéaire.
    2. Un motif $\tau$ de longueur 4 dans toutes les formes cycliques (c'est-à-dire toutes les rotations cycliques de $C(\pi)$).

• Contexte antérieur : Archer et al. avaient déjà résolu le cas où $\tau = 1324$ et $\tau = 1342$. Ils avaient laissé ouvert le cas où $\tau = 1432$.

• Objectif de l'article : Résoudre le cas ouvert $\tau = 1432$ en déterminant une formule explicite pour le nombre de telles permutations, noté $a^\circ_n(\delta_k; 1432)$, pour $k \ge 3$ et $n \ge 5$.

2. Méthodologie

Les auteurs utilisent une approche structurale combinant l'analyse des formes cycliques et des résultats de théorie des ordres.

A. Caractérisation structurelle (Proposition 2.1)

Le point de départ crucial est la Proposition 2.1, qui établit une équivalence fondamentale :

Toutes les formes cycliques d'une permutation $\pi$ évitent le motif $1432$**si et seulement si** sa forme cyclique standard$C(\pi)$ évite les motifs 321 et 2143.

Cette réduction transforme le problème d'évitement de $1432$ dans toutes les rotations en un problème d'évitement de deux motifs spécifiques dans une seule représentation standard, ce qui simplifie considérablement l'analyse structurelle.

B. Analyse des conditions d'ordre (Lemme 2.2)

En combinant l'évitement de $321$et$2143$dans$C(\pi)$, les auteurs déduisent des contraintes strictes sur l'ordre relatif des éléments dans la forme cyclique standard. Si$C(\pi) = (1, j, c_3, \dots, c_n)$, alors :

1. Les éléments $2, 3, \dots, j-1$ doivent apparaître dans l'ordre croissant.
2. Les éléments supérieurs à $j$ situés entre $j$ et $j-1$ doivent être croissants.
3. Les éléments supérieurs à $j$ situés après $2$ doivent être croissants.

C. Application du Théorème de Dilworth

Pour traiter la condition d'évitement du motif décroissant $\delta_k$ dans la notation linéaire, les auteurs utilisent le Théorème de Dilworth.

• Ils définissent un ordre partiel $S_\pi$ sur l'ensemble $\{1, \dots, n\}$ où $i \le_\pi j$ si $i \le j$ et $\pi(i) \le \pi(j)$.
• Une chaîne dans ce poset correspond à une sous-suite croissante, et une antichaîne correspond à une sous-suite décroissante.
• Selon Dilworth, si le poset peut être couvert par $k-1$ chaînes, alors la longueur maximale d'une antichaîne (sous-suite décroissante) est au plus $k-1$. Ainsi, $\pi$ évite $\delta_k$.
• Cette méthode permet de prouver que pour $k \ge 5$, la contrainte d'évitement de $\delta_k$ devient redondante (automatiquement satisfaite) si les conditions cycliques sont remplies.

D. Dénombrement par récurrence et bijection

Les auteurs décomposent le problème en fonction de la valeur du deuxième élément de la forme cyclique standard, $j = c_2$. Ils établissent des bijections (Lemme 2.3, Lemme 3.1) pour réduire les cas $n$ à $n-1$ et calculent les termes restants par analyse directe des structures permises.

3. Résultats Principaux

Les auteurs dérivent des formules explicites pour $a^\circ_n(\delta_k; 1432)$ pour $n \ge 5$, distinguant trois cas selon la valeur de $k$ :

Cas 1 : $k = 3$ (Évitement de $\delta_3 = 321$)

La formule obtenue est :
$$a^\circ_n(\delta_3; 1432) = \left\lfloor \frac{n^2 + 7}{2} \right\rfloor - 2n$$
Ce résultat correspond à la suite OEIS A061925. La preuve implique une somme de termes calculés séparément pour $j=2$, $j=3$ et $j \ge 4$.

Cas 2 : $k = 4$ (Évitement de $\delta_4 = 4321$)

La formule obtenue est :
$$a^\circ_n(\delta_4; 1432) = 2^{n-1} - \left\lfloor \frac{3n - 5}{2} \right\rfloor$$
La preuve est plus complexe, nécessitant une analyse détaillée des positions de $n$ et des relations entre les éléments pour éviter les sous-suites décroissantes de longueur 4.

Cas 3 : $k \ge 5$

Pour $k \ge 5$, la contrainte sur la notation linéaire devient automatique dès que les conditions cycliques sont satisfaites. La formule est :
$$a^\circ_n(\delta_k; 1432) = 2^n + 1 - 2n - \binom{n}{3}$$
Ce résultat correspond à la suite OEIS A088921.

• Preuve clé (Lemme 4.1) : Les auteurs démontrent que toute permutation cyclique dont la forme standard évite $321$et$2143$évite automatiquement$\delta_5$(et donc tout$\delta_k$pour$k \ge 5$) dans sa notation linéaire. La preuve repose sur le théorème d'Erdős–Szekeres et l'analyse des permutations de$S_5$qui évitent à la fois$321$et$123$.

4. Contributions et Signification

• Résolution d'un problème ouvert : L'article clôt définitivement la question laissée ouverte par Archer et al. concernant le motif $\tau = 1432$, complétant ainsi la classification pour les motifs de longueur 4 dans ce contexte spécifique.
• Méthodologie innovante : L'application du théorème de Dilworth pour relier les contraintes cycliques aux contraintes linéaires offre un outil puissant pour l'analyse de l'évitement de motifs dans les permutations cycliques.
• Liens avec les suites connues : Les résultats connectent ce problème de combinatoire à des suites entières déjà répertoriées dans l'OEIS, facilitant leur intégration dans le corpus mathématique existant.
• Structure fine des permutations : L'analyse détaillée des formes cycliques standard évitant $321$et$2143$ révèle une structure rigide (croissance de sous-séquences spécifiques) qui permet un dénombrement exact.

En conclusion, Zhang et Zhao fournissent une solution complète et élégante pour l'évitement simultané du motif décroissant $\delta_k$ et du motif $1432$dans les permutations cycliques, en établissant des formules fermées pour toutes les valeurs pertinentes de$k$et$n$.