Halskæde (kombinatorisk)

I kombinatorik er en -farvet længde halskæde en ækvivalensklasse af -karakterstrenge over et alfabet af størrelse , hvor strenge opnået fra hinanden ved en rotation eller et cyklisk skift betragtes som ækvivalente. For eksempel, for , vil halskæden være sættet . Halskæden kan visuelt repræsenteres som en struktur af perler forbundet i en ring, der har mulige farver (farverne svarer til symbolerne i alfabetet): for at gøre dette skal du tage et af ordene fra denne ækvivalensklasse, mentalt tråd en tråd gennem dens symboler og forbinder dens begyndelse og slutning. $k$ $n$ $n$ $k$ $n=5$ $k=3$ ${\displaystyle \{ababc,babca,abcab,bcaba,cabab\))$ $n$ $k$

$k$ Et farvet armbånd af længde , som omtales som en vendbar (eller fri ) halskæde , defineres på samme måde som ækvivalensklassen af længdestrenge i alfabetet med tegn, men i dette tilfælde er strenge opnået fra hinanden ved rotation, spejlsymmetri , eller en kombination af disse transformationer betragtes som ækvivalente. Hvis du tyer til den visuelle repræsentation af armbånd i form af perler, vil deres forskel fra halskæder være, at det er forbudt at vende halskæderne, men armbåndene er tilladt. Af denne grund kan en halskæde også kaldes en fast halskæde . For eksempel er halskæden, der svarer til snoren , forskellig fra halskæden, der svarer til strengen , men det samme armbånd fås fra disse to strenge (disse to strenge er trods alt opnået fra hinanden ved spejlsymmetri). $n$ $n$ $k$ $ababc$ $cbaba$

Fra et algebrasynspunkt kan halskæden repræsenteres som kredsløbet for den cykliske gruppe af handling på -karakterstrenge, og armbåndet som kredsløbet for den dihedrale gruppe . Man kan tælle disse baner, og dermed antallet af sådanne halskæder og armbånd, ved at bruge Poya-opregningssætningen . $n$

Ækvivalensklasser

Antal halskæder

Ledig

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

forskellige farvede halskæder af længde , hvor er Euler-funktionen [1] [2] . Dette følger direkte af Polya-optællingssætningen , anvendt på handlingen af en cyklisk gruppe, der virker på mængden af alle funktioner . $k$ $n$ $\varphi$ $C_{n}$ ${\displaystyle f:\{1,\ldots ,n\}\to \{1,\ldots ,k\))$

Antal armbånd

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}}

forskellige k -farvede armbånd af længden n , hvor er lig med antallet af k -farvede halskæder af længden n . Dette følger af Poyas metode anvendt på den dihedrale gruppes handling . $N_{k}(n)$ $D_{n}$

Etui af forskellige perler

For et givet sæt af n (forskellige) perler er antallet af forskellige halskæder lavet af disse perler, forudsat at de roterede halskæder er de samme, n !n= ( n − 1)!. Dette følger af, at perlerne kan arrangeres lineært n ! måder og n cykliske skift af hver sådan lineær rækkefølge giver den samme halskæde. Tilsvarende er antallet af forskellige armbånd, forudsat at rotationer og refleksioner er det samme n !2n _ for . $n\geqslant 3$

Hvis perlerne ikke er forskellige, det vil sige, at der er en gentagelse af farver, så vil antallet af halskæder (og armbånd) være mindre. Ovenstående halskædetællende polynomier angiver antallet af halskæder lavet af alle mulige multisæt af perler. Poya- konfigurationenumerationspolynomiet forbedrer tællepolynomiet med en variabel for hver perlefarve, så koefficienten for hver monomial vil tælle antallet af halskæder på et givet multisæt af perler.

Aperiodiske halskæder

En aperiodisk halskæde af længden n er en ækvivalensklasse af rotationer af størrelse n , det vil sige, at der ikke er to forskellige rotationer af halskæden fra denne klasse, der er ækvivalente.

Ifølge Moro-halskædetællefunktionen , er der

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

forskellige k -farvede aperidiske halskæder af længden n , hvor er Möbius-funktionen . De to halskædetællefunktioner er relateret til, hvor summeringen er over alle divisorer af n , hvilket svarer til Möbius-inversionen for $\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))).$

Enhver aperiodisk halskæde indeholder et Lindon-ord , så Lindons ord danner repræsentanter for aperiodiske halskæder.

Se også

Lindons ord
Inversion (diskret matematik)
Perle restaurering problem
Problem med at klippe halskæde
Permutation
Bevis for Fermats lille sætning

Noter

↑ Weisstein, Eric W. Halskæde på Wolfram MathWorld- webstedet .
↑ Himach, Filipenko, 2016 , s. 93.
↑ Yakovenko, 1998 .
↑ Himach, Filipenko, 2016 , s. 94-95.

Litteratur

Khimach R.A., Filipenko A.A. Ungdomsvidenskabeligt forum: Tekniske og matematiske videnskaber: elektr. Lør. Kunst. ved mat. XXXIV Intern. stud. videnskabeligt-praktisk. konf. nr. 5(34). . - 2016. - S. 90-98 .

Kaluzhin L.A., Sushchansky V.I. 13. Kombinatoriske problemer // Transformationer og permutationer. - M . : "Nauka", 1985. - (Videnskabelige og tekniske fremskridts problemer).
Yakovenko D.I. Problem om halskæder // Bulletin fra Omsk University. - 1998. - S. 21-24 .