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

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.[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

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

  1. ^ (EN) Sequenza A180632, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.
  2. ^ (EN) Robin Houston, Tackling the Minimal Superpermutation Problem, 21 agosto 2014.,arΧiv:math.CO/1408.5108
  3. ^ (EN) anonimo, Permutations Thread III, su Warosu, a 4chan archive, 17 settembre 2011. URL consultato il 28 ottobre 2018.
  4. ^ (EN) Mary Beth Griggs, An anonymous 4chan post could help solve a 25-year-old math mystery, su The Verge.
  5. ^ (EN) Robin Houston, A curious situation. The best known lower bound... (1054637891085918209), su Twitter.
  6. ^ (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.
  7. ^ (EN) Aaron Williams, Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by σ = (1 2 ... n) and τ = (1 2).,arΧiv:1307.2549v3
  8. ^ (EN) Greg Egan, Superpermutations, su gregegan.net, 20 ottobre 2018.
  9. ^ Massimo Sandal, 4chan ha risolto un problema matematico e ora è un casino, su Motherboard.

Altri progetti

Collegamenti esterni