vignette|Diagramme montrant le processus de génération d'une superpermutation de 3 symboles à partir d'une superpermutation de 2 symboles. 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! (). 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 ; voir la .
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. Le , Robin Houston, Jay Pantone et Vince Vatter ont publié une version améliorée de cette preuve sur OEIS.
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, Greg Egan a établi un algorithme pour produire des superpermutations de longueur n! + (n−1)! + (n−2)! + (n−3)! + n − 3 ; voir la . Fin 2018, il s'agit des plus petites superpermutations connues pour n ≥ 7.
Références
Voir aussi Bibliographie
Articles connexes , une permutation qui contient toutes les sous-permutations de longueur n.
Liens externes The Minimal Superpermutation Problem - Nathaniel Johnston's blog
Catégorie:Combinatoire des mots Catégorie:Permutation