Permutatie: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
Geen bewerkingssamenvatting |
Geen bewerkingssamenvatting |
||
Regel 128:
== Superpermutatie ==
Een superpermutatie van ''n'' tekens is een [[tekenreeks]] die alle permutaties (in de hierboven eerstgenoemde notatie, maar dan zonder haakjes en komma's) als substring bevat (''n'' opeenvolgende tekens in de reeks).<ref>
Voor 1 ≤ ''n'' ≤ 5 hebben de kortste van deze reeksen een lengte 1! + 2! + … + ''n''!, dus 1, 3, 9, 33 en 153:
Regel 138:
In de eerste vier gevallen is de kortste reeks, afgezien van vernummering, uniek, en een [[palindroom]]. Bij 5 tekens zijn er afgezien van vernummering 8 kortste reeksen.
Voor algemene ''n''≥ 2 is de kortste lengte minstens ''n''! + (''n''−1)! + (''n''−2)! + ''n'' − 3 en hoogstens ''n''! + (''n''−1)! + (''n''−2)! + (''n''−3)! + ''n'' − 3. Bijvoorbeeld voor ''n'' = 6 is de korste lengte dus minstens 870 en hoogstens 873. Er is echter een reeks gevonden van lengte 872, de kortste lengte is dus hoogstens dat aantal.
==Zie ook==
| |||