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

${\displaystyle N_{k}(n)={1 \over n}\sum _{d\mid n}\varphi (d)k^{n/d}}$

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

Antalet armband

Det finns

${\displaystyle B_{k}(n)={\begin{cases}{1 \over 2}N_{k}(n)+{1 \over 4}(k+1)k^{n/2}&{\text{om }}n{\text{ är jämnt}}\\\\{1 \over 2}N_{k}(n)+{1 \over 2}k^{(n+1)/2}&{\text{om }}n{\text{ är udda}}\end{cases}}}$

olika k-nära armband av längden n, där N_k(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 k^p 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 k^p - k = S_k(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å (k^p - k) / p = A_k(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 k¹² 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 k¹². 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 k² strängar av längden två, men av dessa består k = S_k(1) stycken av identiska delsträngar av längden ett och dessa har vi redan dragit ifrån, så det återstår k² - k = S_k(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 k³ - k = S_k(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 k⁴ 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 S_k(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 k⁴ - (k² - k) - k = S_k(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 S_k(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 k⁶ -S_k(3) -S_k(2) - S_k(1) = S_k(6) aperiodiska delsträngar av längd sex att dra ifrån. Vi finner alltså att S_k(12) = k¹² -S_k(6) -S_k(3) -S_k(2) - S_k(1) och således att A_k(12) = (k¹² -S_k(6) -S_k(3) -S_k(2) - S_k(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 ${\displaystyle C_{k}(n)}$ och de övriga (som avbildas på sig själv vid spegling) med ${\displaystyle S_{k}(n)}$ får vi att det totala antalet armband ${\displaystyle B_{k}(n)}$ är lika med:

${\displaystyle B_{k}(n)=S_{k}(n)+C_{k}(n)=S_{k}(n)+(N_{k}(n)-S_{k}(n))/2={1 \over 2}N_{k}(n)+{1 \over 2}S_{k}(n)}$

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".^[2] 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 ${\displaystyle k^{(n+1)/2}}$ (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 ${\displaystyle (N_{k}(n)-k^{(n+1)/2})/2}$ 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: ${\displaystyle B_{k}(n)=k^{(n+1)/2}+(N_{k}(n)-k^{(n+1)/2})/2={1 \over 2}N_{k}(n)-{1 \over 2}k^{(n+1)/2}+k^{(n+1)/2})={1 \over 2}N_{k}(n)+{1 \over 2}k^{(n+1)/2}}$ om n är udda.

Se även

• Lyndonord
• Inversion (kombinatorik)
• Permutation

Referenser och noter

Externa länkar

• Weisstein, Eric W., "Necklace", MathWorld. (engelska)
• Info on necklaces, Lyndon words, De Bruijn sequences