Halsband (kombinatorik)

I kombinatorik är ett -färgat längdhalsband en ekvivalensklass av -teckensträngar över ett alfabet av storlek , där strängar som erhålls från varandra genom en rotation eller ett cykliskt skift anses vara ekvivalenta. Till exempel, för , kommer halsbandet att vara uppsättningen . Halsbandet kan visuellt representeras som en struktur av pärlor anslutna i en ring, med möjliga färger (färgerna motsvarar symbolerna i alfabetet): för att göra detta måste du ta ett av orden i denna ekvivalensklass, mentalt tråd en tråd genom dess symboler och förbinder dess början och slut. $k$ $n$ $n$ $k$ $n=5$ $k=3$ ${\displaystyle \{ababc,babca,abcab,bcaba,cabab\))$ $n$ $k$

$k$ Ett färgat armband av längd , som kallas ett vändbart (eller fritt ) halsband , definieras på samma sätt som ekvivalensklassen för längdsträngar i alfabetet - men i detta fall strängar som erhålls från varandra genom rotation, spegelsymmetri , eller en kombination av dessa transformationer anses likvärdiga. Om du tillgriper den visuella representationen av armband i form av pärlor, kommer deras skillnad från halsband att vara att det är förbjudet att vända halsbanden, men armbanden är tillåtna. Av denna anledning kan ett halsband också kallas ett fast halsband . Till exempel är halsbandet som motsvarar strängen annorlunda än halsbandet som motsvarar strängen , men samma armband erhålls från dessa två strängar (dessa två strängar erhålls trots allt från varandra genom spegelsymmetri). $n$ $n$ $k$ $ababc$ $cbaba$

Ur algebras synvinkel kan halsbandet representeras som omloppsbanan för den cykliska aktionsgruppen på teckensträngar, och armbandet som omloppsbanan för den dihedrala gruppen . Man kan räkna dessa banor, och därav antalet sådana halsband och armband, med hjälp av Poyas uppräkningssats . $n$

Ekvivalensklasser

Antal halsband

Tillgängligt

N_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\varphi (d)k^{\frac {n}{d}}

olikfärgade halsband av längd , där är Euler-funktionen [1] [2] . Detta följer direkt av Polya-uppräkningssatsen , tillämpad på verkan av en cyklisk grupp som verkar på mängden av alla funktioner . $k$ $n$ $\varphi$ $C_{n}$ ${\displaystyle f:\{1,\ldots ,n\}\to \{1,\ldots ,k\))$

Antal armband

Ja [3] [4]

B_{k}(n)={\begin{cases}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+1) k^{\frac {n}{2}}&n\equiv 0{\pmod {2}},\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}k^{\frac {n+1}{2}}&n\equiv 1{\pmod {2}}\end{cases}}

olika k -färgade armband med längden n , där är lika med antalet k -färgade halsband med längden n . Detta följer av Poyas metod tillämpad på den dihedriska gruppens verkan . $N_{k}(n)$ $D_{n}$

Fall av olika pärlor

För en given uppsättning av n (olika) pärlor är antalet distinkta halsband gjorda av dessa pärlor, förutsatt att de roterade halsbanden är desamma, n !n= ( n − 1)!. Detta följer av det faktum att pärlor kan arrangeras linjärt n ! sätt och n cykliska förskjutningar av varje sådan linjär ordning ger samma halsband. På samma sätt är antalet olika armband, förutsatt att rotationer och reflektioner är desamma n !2n _ för . $n\geqslant 3$

Om pärlorna inte är olika, det vill säga det finns en upprepning av färger, kommer antalet halsband (och armband) att vara mindre. Ovanstående halsbandsräknande polynom anger antalet halsband gjorda av alla möjliga multiuppsättningar av pärlor. Poya- konfigurationsuppräkningspolynomet förbättrar räknepolynomet med en variabel för varje pärlfärg, så att koefficienten för varje monomial kommer att räkna antalet halsband på en given multiuppsättning av pärlor.

Aperiodiska halsband

Ett aperiodiskt halsband med längd n är en ekvivalensklass av rotationer av storlek n , det vill säga inga två olika rotationer av halsbandet från denna klass är likvärdiga.

Enligt Moro-halsbandsräkningsfunktionen finns det

M_{k}(n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)k^{\frac {n}{d}}

olika k -färgade aperidiska halsband med längden n , där finns Möbius-funktionen . De två halsbandsräknefunktionerna är relaterade till där summan är över alla divisorer av n , vilket är ekvivalent med Möbius-inversionen för $\mu$ $N_{k}(n)\ =\ \sum \nolimits _{d|n}M_{k}(d),$ $M_{k}(n)\ =\ \sum \nolimits _{d|n}N_{k}(d)\,\mu ({\tfrac {n}{d))).$

Varje aperiodiskt halsband innehåller ett Lindon-ord , så Lindons ord bildar representanter för aperiodiska halsband.

Se även

Lindons ord
Inversion (diskret matematik)
Problem med pärlrestaurering
Problem med att klippa halsband
Permutation
Bevis på Fermats lilla sats

Anteckningar

↑ Weisstein, Eric W. Halsband på Wolfram MathWorld- webbplatsen .
↑ Himach, Filipenko, 2016 , sid. 93.
↑ Yakovenko, 1998 .
↑ Himach, Filipenko, 2016 , sid. 94-95.

Litteratur

Khimach R.A., Filipenko A.A. Ungdomsvetenskapligt forum: Tekniska och matematiska vetenskaper: elektr. lö. Konst. av matta. XXXIV Intern. hingst. vetenskapligt-praktiskt. konf. nr 5(34). . - 2016. - S. 90-98 .

Kaluzhin L.A., Sushchansky V.I. 13. Kombinatoriska problem // Transformationer och permutationer. - M . : "Nauka", 1985. - (Problem med vetenskap och tekniska framsteg).
Yakovenko D.I. Problem om halsband // Bulletin of the Omsk University. - 1998. - S. 21-24 .

Länkar

Weisstein, Eric W. Halsband (engelska) på Wolfram MathWorld- webbplatsen .
Info om halsband, Lyndon-ord, De Bruijn-sekvenser