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
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
[modifier | modifier le code]Borne inférieure
[modifier | modifier le code]En septembre 2011, 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] ; voir la suite A376269 de l'OEIS.
La preuve de cette borne inférieure fut mise en lumière en octobre 2018, après que le mathématicien et informaticien Robin Houston ait tweeté à ce sujet[2],[3]. Le 25 octobre 2018, Robin Houston, Jay Pantone et Vince Vatter ont publié une version améliorée de cette preuve sur OEIS[4].
Borne supérieure
[modifier | modifier le code]Le 20 octobre 2018, 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] ; voir la suite A341300 de l'OEIS. Fin 2018, il s'agit des plus petites superpermutations connues pour n ≥ 7.
Références
[modifier | modifier le code]- ↑ (en) Anonymous, « Permutations Thread III », sur Warosu, a 4chan archive, 17 septembre 2011 (consulté le 27 octobre 2018)
- ↑ (en) Mary Beth Griggs, « An anonymous 4chan post could help solve a 25-year-old math mystery », sur The Verge, 24 octobre 2018
- ↑ (en) Robin Houston, « A curious situation. The best known lower bound... (1054637891085918209) », sur Twitter (consulté le 27 octobre 2018)
- ↑ (en) Anonymous 4chan poster, Robin Houston, Jay Pantone et Vince Vatter, « A lower bound on the length of the shortest superpattern », sur OEIS, 25 octobre 2018 (consulté le 27 octobre 2018)
- ↑ (en) Aaron Williams, « Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2) », 2018.
- ↑ (en) Greg Egan, « Superpermutations », 20 octobre 2018 (consulté le 27 octobre 2018)
Voir aussi
[modifier | modifier le code]Bibliographie
[modifier | modifier le code]- Daniel A. Ashlock et Jenett Tillotson, « Construction of small superpermutations and minimal injective superstrings », Congressus Numerantium, vol. 93, 1993, p. 91–98 (zbMATH 0801.05004)
- Nathaniel Johnston, « Non-uniqueness of minimal superpermutations », Discrete Mathematics, vol. 313, no 14, 28 juillet 2013, p. 1553–1557 (DOI 10.1016/j.disc.2013.03.024, zbMATH 1368.05004, arXiv 1303.4150, lire en ligne, consulté le 16 mars 2014)
- (en) Houston Robin, « Tackling the Minimal Superpermutation Problem », 21 août 2014.
- Jean-Paul Delahaye, « Le secret d'Arsène Lupin : les superpermutations », Pour la science, no 513, 22 juin 2020, p. 82-87 (lire en ligne, consulté le 25 juillet 2020)
Articles connexes
[modifier | modifier le code]- Supermotif (en), une permutation qui contient toutes les sous-permutations de longueur n.
Liens externes
[modifier | modifier le code]- The Minimal Superpermutation Problem - Nathaniel Johnston's blog
- James Grime, « Superpermutations - Numberphile » [vidéo], sur YouTube, Brady Haran (consulté le 1er février 2018)
