In matematica combinatoria, una superpermutazione di n simboli è una stringa che contiene tutte le permutazioni dei suoi simboli come sottostringa.
Si sa che per 1 ≤ n ≤ 5 le superpermutazioni minimali di n simboli, cioè quelle di lunghezza minore possibile, hanno lunghezza 1! + 2! + ... + n! . Le prime cinque superpermutazioni minimali hanno pertanto lunghezza rispettiva 1, 3, 9, 33, e 153, e sono date dalle stringhe 1, 121, 123121321, 123412314231243121342132413214321, e:
123451234152341253412354123145231425314235142315423124531243 512431524312543121345213425134215342135421324513241532413524 132541321453214352143251432154321
Per n ≥ 6 non è nota qual è la lunghezza minima: è possibile scendere sotto il valore dato dalla formula suindicata, come mostrato per la prima volta nel 2014 da Robin Houston,.
Limiti superiori e inferiori Limite inferiore Nel settembre 2011 un utente anonimo del sito di immagini 4chan dimostrò che la superpermutazione minimale di n simboli (per n ≥ 2) ha lunghezza almeno n! + (n-1)! + (n-2)! + n - 3. A ottobre 2018 Houston ha riportato in auge il problema. Il 25 ottobre 2018 Houston, insieme a Jay Pantone e Vince Vatter, hanno pubblicato una nuova versione della dimostrazione su OEIS.
Limite superiore Il 20 ottobre 2018, adattando una procedura di Aaron Williams per costruire un cammino hamiltoniano sul grafo di Cayley di un gruppo simmetrico,, lo scrittore di fantascienza Greg Egan ha sviluppato un algoritmo che produce superpermutazioni di lunghezza n! + (n-1)! + (n-2)! + (n-3)! + n - 3. Al momento questi sono i migliori risultati noti per n ≥ 7.
Note
Altri progetti
Collegamenti esterni
Categoria:Combinatoria