Nyaklánc (kombinatorika)

A kombinatorikában a színezett hosszúságú nyaklánc egy méretű ábécé feletti -karakterláncok ekvivalencia osztálya , ahol az egymástól elforgatással vagy ciklikus eltolással kapott karakterláncokat egyenértékűnek tekintjük. Például a számára a nyaklánc a készlet lesz . A nyaklánc vizuálisan ábrázolható, mint egy gyűrűben összekapcsolt gyöngyök szerkezete, lehetséges színekkel (a színek az ábécé szimbólumainak felelnek meg): ehhez ki kell venni az ekvivalencia osztály egyik szavát, mentálisan befűzni egy szálat a szimbólumain keresztül, és kapcsolja össze annak elejét és végét. $k$ $n$ $n$ $k$ $n=5$ $k=3$ ${\displaystyle \{ababc,babca,abcab,bcaba,cabab\))$ $n$ $k$

$k$ A hosszúságú színes karkötőt , amelyet megfordítható (vagy szabad ) nyakláncnak nevezünk, hasonlóképpen a -karakteres ábécé hosszúságú húrjainak ekvivalenciaosztályaként határozzuk meg , azonban ebben az esetben az egymásból forgatással kapott húrok, tükörszimmetria , vagy ezen transzformációk kombinációja egyenértékűnek tekinthető. Ha a karkötők gyöngyök formájában történő vizuális megjelenítéséhez folyamodsz, akkor a nyakláncokhoz képest az lesz a különbség, hogy a nyakláncokat tilos megfordítani, de a karkötőket megengedett. Emiatt a nyakláncot fix nyakláncnak is nevezhetjük . Például a zsinórnak megfelelő nyaklánc különbözik a zsinórnak megfelelő nyaklánctól , de ebből a két zsinórból ugyanazt a karkötőt kapjuk (elvégre ezt a két zsinórt tükörszimmetria alapján kapjuk egymásból). $n$ $n$ $k$ $ababc$ $cbaba$

Az algebra szempontjából a nyaklánc a -karakterfüzérek ciklikus hatáscsoportjának pályájaként , a karkötő pedig a diédercsoport pályájaként ábrázolható . Megszámolhatjuk ezeket a pályákat, és ebből következően az ilyen nyakláncok és karkötők számát a Poya felsorolási tétel segítségével . $n$

Egyenértékűségi osztályok

Nyakláncok száma

Elérhető

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

különböző színű hosszúságú nyakláncok , ahol az Euler függvény [1] [2] . Ez közvetlenül következik a Polya felsorolási tételből , amelyet egy ciklikus csoport működésére alkalmazunk, amely az összes függvény halmazára hat . $k$ $n$ $\varphi$ $C_{n}$ ${\displaystyle f:\{1,\ldots ,n\}\to \{1,\ldots ,k\))$

Karkötők száma

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

különböző k színű n hosszúságú karkötők , ahol egyenlő az n hosszúságú k színű nyakláncok számával . Ez Poya módszeréből következik, amelyet a diédercsoport működésére alkalmaztak . $N_{k}(n)$ $D_{n}$

Különböző gyöngyök tokja

Egy adott n (különböző) gyöngyből álló készlet esetén az ezekből a gyöngyökből készült különálló nyakláncok száma, feltételezve, hogy az elforgatott nyakláncok azonosak, n !n= ( n − 1)!. Ez abból következik, hogy a gyöngyök lineárisan n ! módok és n ciklikus eltolódás minden ilyen lineáris sorrendben ugyanazt a nyakláncot adja. Hasonlóképpen, a különböző karkötők száma, feltételezve, hogy az elforgatások és a tükröződések azonosak n !2n _ számára . $n\geqslant 3$

Ha a gyöngyök nem különböznek egymástól, vagyis a színek ismétlődnek, akkor a nyakláncok (és karkötők) száma kevesebb lesz. A fenti nyakláncszámláló polinomok megadják az összes lehetséges gyöngysorból készült nyakláncok számát . A Poya konfigurációs felsorolási polinom minden egyes gyöngyszínhez változóval javítja a számlálási polinomot, így az egyes monomok együtthatója számolja a nyakláncok számát egy adott gyöngyhalmazon.

Időszakos nyakláncok

Az n hosszúságú aperiodikus nyaklánc az n méretű forgások ekvivalenciaosztálya , vagyis ebből az osztályból nincs két különböző elforgatás egyenértékű.

A Moro nyaklánc-számláló függvény szerint létezik

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

különböző k színű, n hosszúságú aperidik nyakláncok , ahol a Möbius-függvény . A két nyaklánc-számláló függvény összefügg azzal, hogy hol az összegzés az n összes osztójára vonatkozik , ami ekvivalens a Möbius - inverzióval $\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))).$

Bármely időszakos nyaklánc tartalmaz egy Lindon szót , így Lindon szavai az időszakos nyakláncok képviselői .

Lásd még

Lindon szava
Inverzió (diszkrét matematika)
Gyöngy helyreállítási probléma
Nyaklánc vágási probléma
Permutáció
Fermat kis tételének bizonyítása

Jegyzetek

↑ Weisstein, Eric W. Nyaklánc a Wolfram MathWorld weboldalán .
↑ Himach, Filipenko, 2016 , p. 93.
↑ Jakovenko, 1998 .
↑ Himach, Filipenko, 2016 , p. 94-95.

Irodalom

Khimach R.A., Filipenko A.A. Ifjúsági tudományos fórum: Műszaki és matematikai tudományok: elektr. Ült. Művészet. szőnyeg által. XXXIV Gyakornok. ménes. tudományos-gyakorlati. konf. 5. (34) bekezdése alapján. . - 2016. - S. 90-98 .

Kaluzhin L.A., Sushchansky V.I. 13. Kombinatorikai problémák // Transzformációk és permutációk. - M . : "Nauka", 1985. - (A tudomány és a műszaki haladás problémái).
Yakovenko D.I. Probléma a nyakláncokkal kapcsolatban // Az Omszki Egyetem közleménye. - 1998. - S. 21-24 .

Linkek

Weisstein, Eric W. Necklace (angol) a Wolfram MathWorld weboldalán .
Információ a nyakláncokról, Lyndon szavakról, De Bruijn sorozatokról