Halsband (kombinatorik)

Inom kombinatoriken är ett k-närt halsband med längden n en ekvivalensklass av strängar med längden n över ett alfabet av storleken k, där alla rotationer (utan carry) är ekvivalenta. Det motsvarar en struktur bestående av n cirkulärt förbundna pärlor av upp till k olika färger.

Ett k-närt armband, även kallat ett vändbart (eller fritt) halsband, är ett halsband sådant att strängarna även är ekvilalenta under reflektion. Det vill säga att om en sträng är identisk med en annan sträng i omvänd ordning, så tillhör de samma ekvivalensklass. Av denna anledning kan man kalla ett halsband för ett fast halsband för att skilja det från ett vändbart.

Tekniskt sett kan man klassificera ett halsband som en bana i den cykliska gruppen av strängar bestående av n tecken och ett armband som en bana i den dihedrala gruppen. Detta gör att man kan tillämpa Polyas enumerationssats på halsband och armband.

Ekvivalensklasser

Antalet halsband 
Det finns

olika k-nära halsband av längden n, där φ betecknar Eulers fi-funktion.

Antalet armband 
Det finns

olika k-nära armband av längden n, där Nk(n) är antalet k-nära halsband av längden n.

Aperiodiska halsband
Ett aperiodiskt halsband är ett halsband som inte kan delas upp i identiska delsträngar (ett halsband som kan delas upp på sådant sätt är givetvis periodiskt). Exempelvis är "ABCABC" och "ABABAB" periodiska, eftersom de kan delas upp i två "ABC" (eller "BCA" eller "CAB") respektive tre "AB" (eller "BA"), medan "AAAAAB" är aperiodiskt eftersom  det inte kan delas upp på detta sätt. Alla halsband med längden ett är såklart aperiodiska eftersom de inte kan delas upp alls. 

Om halsbandets längd är ett primtal p är det enda sätt det kan delas upp i lika långa strängar att dela det i p strängar med längden ett, och sålunda är alla halsband av längd p aperiodiska utom de som består av p identiska pärlor. Der finns kp strängar av längden p (k är antalet olika pärlor) varav k stycken består av identiska pärlor. De halsband som kan bildas av de övriga kp - k = Sk(p) strängarna är således aperiodiska och eftersom ett aperiodiskt halsband av längden p kan "klippas upp" i p olika strängar finns det alltså (kp - k) / p = Ak(p) aperiodiska halsband av längd p.

Om halsbandets längd, n, inte är ett primtal kan detta även delas upp i liklånga strängar av annan längd och i det fall dessa strängar är identiska är halsbandet periodiskt.
Exempel
Ett k-närt halsband av längden 12 kan delas upp i liklånga delsträngar av längderna 1, 2, 3, 4 respektive 6. Det finns k12 olika strängar med längden 12. För att räkna ut hur många av dessa som är aperiodiska (och således ger upphov till aperiodiska halsband om vi "knyter ihop ändarna") måste vi dra bort alla periodiska strängar från k12. Så vi börjar med att stryka de k strängarna som består av tolv identiska pärlor, d.v.s. består av tolv identiska delsträngar av längden ett. Det finns k2 strängar av längden två, men av dessa består k = Sk(1) stycken av identiska delsträngar av längden ett och dessa har vi redan dragit ifrån, så det återstår k2 - k = Sk(2) strängar av längden tolv som består av sex identiska aperiodiska(!) delsträngar av längden två att dra bort. På samma sätt får vi ta bort k3 - k = Sk(3) strängar som består av fyra upprepningar av aperiodiska delsträngar av längden tre. I fallet att vi delar upp halsbandet i tre delsträngar av längden fyra (som ju inte är ett primtal) konstaterar vi att det finns k4 olika strängar av längden fyra, men av dessa har vi redan tidigare dels dragit ifrån de k strängar som består av identiska "pärlor" och dels de Sk(2) strängar som består av två identiska aperiodiska delsträngar av längden två (sex strängar "AB" ger ju upphov till samma sträng av längden tolv som tre strängar "ABAB"), varför det återstår k4 - (k2 - k) - k = Sk(4) strängar av längden tolv som består av tre aperiodiska delsträngar av längden fyra att dra ifrån. För fallet med två delsträngar av längden sex får vi från de Sk(6) strängarna av längden sex ta bort de stängar som kan delas upp i identiska delsträngar av längderna ett, två och tre (och således är periodiska) på samma sätt, det vill säga att det finns k6 -Sk(3) -Sk(2) - Sk(1) = Sk(6) aperiodiska delsträngar av längd sex att dra ifrån. Vi finner alltså att Sk(12) = k12 -Sk(6) -Sk(3) -Sk(2) - Sk(1) och således att Ak(12) = (k12 -Sk(6) -Sk(3) -Sk(2) - Sk(1)) / 12.

Härledningar

Antalet armband
Skillnaden mellan antalet armband och antalet halsband beror på att vissa halsband avbildas på sig själva vid spegling (exempelvis ger ABABAB vid spegling BABABA = ABABAB), medan andra avbildas på ett annat halsband (exempelvis ger AABBAB vid spegling BABBAA = AABABB ≠ AABBAB). Dessa senares "spegelbilder" får alltså dras från antalet halsband, eftersom de motsvarar samma armband. De armband som på detta sätt motsvarar två olika halsband kallas chirala. Om vi betecknar de armband som är chirala med  och de övriga (som avbildas på sig själv vid spegling) med  får vi att det totala antalet armband  är lika med:

Om n är udda innebär en spegling att det finns ett symmetriplan som går genom en pärla och en motstående länk (jämför med ett hörn och en motstående sida hos en udda månghörning). En spegling som avbildar halsbandet på sig själv motsvaras av en sträng som är symmetrisk kring "mittpärlan", exempelvis (det uppklippta) halsbandet "ABCBA" som avbildas på sig själv om det speglas i ett plan (linje) som går genom "C" och mellan de två "A". Armband utan denna egenskap representeras däremot av två olika halsband, det vill säga är chirala (exempelvis "ABCAB" som vid spegling ger "BACBA"). Antalet halsband som avbildas på sig själv är därför lika med  (mittpärlan plus hälften av återstående pärlor - pärlorna på båda sidor om mittpärlan är ju parvis lika - kan vardera vara av k olika typer) och antalet armband med denna egenskap blir därför lika med antalet sådana halsband. Resterande armband mostsvarar vardera två olika halsband, varför dessa återstående halsbands antal måste delas med två, det vill säga  stycken. Det totala antalet k-nära armband av längden n blir därför lika med summan av de halsband som avbildas på sig själv vid spegling och hälften av de som inte gör det:  om n är udda.

Se även
 Lyndonord
 Inversion (kombinatorik)
 Permutation

Referenser och noter

Externa länkar
 
 Info on necklaces, Lyndon words, De Bruijn sequences

Kombinatorik