Accueil🇫🇷Chercher

Superpermutation

En mathématiques, et plus précisément en combinatoire, une superpermutation de n caractères est une chaîne qui contient chaque permutation de n caractères comme sous-chaîne.

Il a été démontré que pour 1 ≤ n ≤ 5, la plus petite superpermutation de n caractères a pour longueur 1! + 2! + … + n! (suite A180632 de l'OEIS). Les cinq premières superpermutations ont pour longueurs respectives 1, 3, 9, 33 et 153, formant les chaînes 1, 121, 123121321, 123412314231243121342132413214321 et la chaîne :

123451234152341253412354123145231425314235142315423124531243
512431524312543121345213425134215342135421324513241532413524
132541321453214352143251432154321

Bornes inférieure et supérieure

Borne inférieure

En , un message anonyme sur le forum internet 4chan a montré que la plus petite superpermutation de n caractères (n ≥ 2) est au moins de longueur n! + (n−1)! + (n−2)! + n − 3[1]. La preuve de cette borne inférieure fut mise en lumière en , après que le mathématicien et informaticien Robin Houston ait tweeté à ce sujet[2] - [3]. Le , Robin Houston, Jay Pantone et Vince Vatter ont publié une version améliorée de cette preuve sur OEIS[4].

Borne supérieure

Le , en adaptant un travail de Aaron Williams pour construire des chemins hamiltoniens dans le graphe de Cayley du groupe symétrique[5], Greg Egan a établi un algorithme pour produire des superpermutations de longueur n! + (n−1)! + (n−2)! + (n−3)! + n − 3[6]. Fin 2018, il s'agit des plus petites superpermutations connues pour n ≥ 7.

Références

  1. (en) Anonymous, « Permutations Thread III », sur Warosu, a 4chan archive, (consulté le )
  2. (en) Mary Beth Griggs, « An anonymous 4chan post could help solve a 25-year-old math mystery », sur The Verge,
  3. (en) Robin Houston, « A curious situation. The best known lower bound... (1054637891085918209) », sur Twitter (consulté le )
  4. (en) Anonymous 4chan poster, Robin Houston, Jay Pantone et Vince Vatter, « A lower bound on the length of the shortest superpattern », sur OEIS, (consulté le )
  5. (en) Aaron Williams, « Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2) », .
  6. (en) Greg Egan, « Superpermutations », (consulté le )

Voir aussi

Bibliographie

Articles connexes

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.