Visa källa för Halsband (kombinatorik)

[[File:Partition necklaces by integer partition.svg|thumb|400px|Möjliga armband av längden ''n''<br>motsvarande den ''k'':te [[heltalspartition]]en<br> ([[partition av en mängd]] frånsett rotation och spegling)]]
[[File:Bracelets33.svg|thumb|300px|De tre armbanden bestående av tre röda och tre gröna pärlor. Armbandet i mitten är [[chiral]]t, så det finns fyra halsband.<br>Jämför med ruta (6,9) i triangeln ovan.]]
[[File:Bracelets222.svg|thumb|300px|De elva armbanden med två röda, två gula och två gröna pärlor. Det längst till vänster och de fyra längst till höger är chirala, så det finns 16 halsband.<br>Jämför ruta (6,7) i triangeln.]]
[[File:Tantrix tiles ryg.svg|thumb|300px|De 16 ''möjliga'' [[Tantrix]]-brickorna, motsvarande de 16 halsbanden med två röda, två gula och två gröna pärlor. (De två brickorna med tre korsande linjer längst till höger ingår inte i spelet Tantrix.)]]
Inom [[kombinatorik]]en är ett ''k''-närt '''halsband''' med längden ''n'' en [[ekvivalensklass]] av [[Sträng (data)|strängar]] med längden ''n'' över ett [[Alfabet (matematik)|alfabet]] av storleken ''k'', där alla [[Bitvis operation#Rotation utan carry|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 [[gruppverkan|bana]] i den [[cyklisk grupp|cykliska gruppen]] av strängar bestående av ''n'' tecken och ett armband som en bana i den [[dihedral grupp|dihedrala gruppen]]. Detta gör att man kan tillämpa [[Polyas enumerationssats]] på halsband och armband.

== Ekvivalensklasser ==
=== Antalet halsband ===
Det finns

:<math>N_k(n)={1\over n}\sum_{d\mid n}\varphi(d)k^{n/d}</math>

olika ''k''-nära halsband av längden ''n'', där φ betecknar [[Eulers fi-funktion]].<ref>http://mathworld.wolfram.com/Necklace.html</ref>

=== Antalet armband ===
Det finns
:<math>
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}
</math>
olika ''k''-nära armband av längden ''n'', där ''N''<sub>''k''</sub>(''n'') är antalet ''k''-nära halsband av längden&nbsp;''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<sup>p</sup>'' 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<sup>p</sup>&nbsp;-&nbsp;k&nbsp;=&nbsp;S<sub>k</sub>(p)'' strängarna är således aperiodiska och eftersom ett aperiodiskt halsband av längden ''p'' kan "klippas upp" i ''p'' <u>olika</u> strängar finns det alltså ''(k<sup>p</sup>&nbsp;-&nbsp;k)&nbsp;/&nbsp;p&nbsp;=&nbsp;A<sub>k</sub>(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<sup>12</sup>'' 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<sup>12</sup>''. 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<sup>2</sup>'' strängar av längden två, men av dessa består ''k&nbsp;=&nbsp;S<sub>k</sub>(1)'' stycken av identiska delsträngar av längden ett och dessa har vi redan dragit ifrån, så det återstår ''k<sup>2</sup>&nbsp;-&nbsp;k&nbsp;=&nbsp;S<sub>k</sub>(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<sup>3</sup>&nbsp;-&nbsp;k&nbsp;=&nbsp;S<sub>k</sub>(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<sup>4</sup>'' 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<sub>k</sub>(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<sup>4</sup>&nbsp;-&nbsp;(k<sup>2</sup>&nbsp;-&nbsp;k)&nbsp;-&nbsp;k&nbsp;=&nbsp;S<sub>k</sub>(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<sub>k</sub>(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<sup>6</sup>&nbsp;-S<sub>k</sub>(3)&nbsp;-S<sub>k</sub>(2)&nbsp;-&nbsp;S<sub>k</sub>(1)&nbsp;=&nbsp;S<sub>k</sub>(6)'' aperiodiska delsträngar av längd sex att dra ifrån. Vi finner alltså att ''S<sub>k</sub>(12)&nbsp;=&nbsp;k<sup>12</sup>&nbsp;-S<sub>k</sub>(6)&nbsp;-S<sub>k</sub>(3)&nbsp;-S<sub>k</sub>(2)&nbsp;-&nbsp;S<sub>k</sub>(1)'' och således att ''A<sub>k</sub>(12)&nbsp;=&nbsp;(k<sup>12</sup>&nbsp;-S<sub>k</sub>(6)&nbsp;-S<sub>k</sub>(3)&nbsp;-S<sub>k</sub>(2)&nbsp;-&nbsp;S<sub>k</sub>(1))&nbsp;/&nbsp;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 [[chiralitet|chirala]]. Om vi betecknar de armband som är chirala med <math>C_k(n)</math> och de övriga (som avbildas på sig själv vid spegling) med <math>S_k(n)</math> får vi att det totala antalet armband <math>B_k(n)</math> är lika med:

<math>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)</math>

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".<ref>Notera att den typ av pärla som "mittpärlan" tillhör måste förekomma ett udda antal gånger i armbandet, medan alla andra typer måste förekomma ett jämnt antal gånger. Armband med ett udda antal pärlor kan därför ha högst ''ett'' symmetriplan om det består av mer än en typ av pärlor. Så enkelt är det inte om armbandet består av ett jämnt antal pärlor!</ref> 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 <math>k^{(n+1)/2}</math> (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 <math>(N_k(n) - k^{(n+1)/2})/2</math> 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: <math>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}</math> om ''n'' är udda.

==Se även==
* [[Lyndonord]]
* [[Inversion (kombinatorik)]]
* [[Permutation]]

==Referenser och noter==
<references/>

==Externa länkar==
* {{MathWorld|Necklace|Necklace}}
* [https://web.archive.org/web/20061002130346/http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html Info on necklaces, Lyndon words, De Bruijn sequences]

[[Kategori:Kombinatorik]]