Superpermutazione
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! [1]. 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[2].
Limiti superiori e inferiori[modifica | modifica wikitesto]
Limite inferiore[modifica | modifica wikitesto]
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.[3] A ottobre 2018 Houston ha riportato in auge il problema[4][5]. Il 25 ottobre 2018 Houston, insieme a Jay Pantone e Vince Vatter, hanno pubblicato una nuova versione della dimostrazione su OEIS.[6]
Limite superiore[modifica | modifica wikitesto]
Il 20 ottobre 2018, adattando una procedura di Aaron Williams per costruire un cammino hamiltoniano sul grafo di Cayley di un gruppo simmetrico,[7] lo scrittore di fantascienza Greg Egan ha sviluppato un algoritmo che produce superpermutazioni di lunghezza n! + (n-1)! + (n-2)! + (n-3)! + n - 3.[8][9] Al momento questi sono i migliori risultati noti per n ≥ 7.
Note[modifica | modifica wikitesto]
- ^ (EN) Sequenza A180632, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
- ^ (EN) Robin Houston, Tackling the Minimal Superpermutation Problem, 21 agosto 2014.,arΧiv:math.CO/1408.5108
- ^ (EN) anonimo, Permutations Thread III, su Warosu, a 4chan archive, 17 settembre 2011. URL consultato il 28 ottobre 2018.
- ^ (EN) Mary Beth Griggs, An anonymous 4chan post could help solve a 25-year-old math mystery, su The Verge.
- ^ (EN) Robin Houston, A curious situation. The best known lower bound... (1054637891085918209), su Twitter.
- ^ (EN) Anomymous 4chan poster, Robin Houston, Jay Pantone e Vince Vatter, A lower bound on the length of the shortest superpattern (PDF), su OEIS, 25 ottobre 2018. URL consultato il 28 ottobre 2018.
- ^ (EN) Aaron Williams, Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2).,arΧiv:1307.2549v3
- ^ (EN) Greg Egan, Superpermutations, su gregegan.net, 20 ottobre 2018.
- ^ Massimo Sandal, 4chan ha risolto un problema matematico e ora è un casino, su Motherboard.
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su Superpermutazione
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) The Minimal Superpermutation Problem - Nathaniel Johnston's blog
- (EN) James Grime, Superpermutations - Numberphile, su YouTube. URL consultato il 28 ottobre 2018.