Náhrdelník (kombinatorika)

V kombinatorice je náhrdelník s barevnou délkou třídou ekvivalence řetězců znaků přes abecedu velikosti , kde řetězce získané od sebe navzájem rotací nebo cyklickým posunem jsou považovány za ekvivalentní. Například pro , náhrdelník bude sada . Náhrdelník může být vizuálně reprezentován jako struktura korálků spojených do prstence, které mají možné barvy (barvy odpovídají symbolům v abecedě): k tomu musíte vzít jedno ze slov této třídy ekvivalence, mentálně provázet protáhněte jejími symboly a spojte její začátek a konec. $k$ $n$ $n$ $k$ $n=5$ $k=3$ $\{ababc,babca,abcab,bcaba,cabab\}$ $n$ $k$

$k$ Barevný náramek délky , který je označován jako reverzibilní (neboli volný ) náhrdelník , je definován obdobně jako třída ekvivalence délkových šňůrek v abecedě -znaků, v tomto případě však šňůrky získané jedna od druhé rotací, zrcadlová symetrie nebo kombinace těchto transformací jsou považovány za ekvivalentní. Pokud se uchýlíte k vizuálnímu znázornění náramků ve formě korálků, jejich rozdíl od náhrdelníků bude v tom, že náhrdelníky je zakázáno převracet, ale náramky jsou povoleny. Z tohoto důvodu může být náhrdelník také nazýván pevným náhrdelníkem . Například náhrdelník odpovídající provázku se liší od náhrdelníku odpovídajícímu provázku , ale z těchto dvou provázků je získán stejný náramek (koneckonců, tyto dva provázky jsou od sebe získány zrcadlovou symetrií). $n$ $n$ $k$ $ababc$ $cbaba$

Z hlediska algebry lze náhrdelník znázornit jako dráhu cyklické skupiny působení na strunách znaků a náramek jako dráhu dihedrální skupiny . Tyto oběžné dráhy, a tedy i počet takových náhrdelníků a náramků, lze spočítat pomocí Poyovy věty o výčtu . $n$

Třídy ekvivalence

Počet náhrdelníků

Dostupný

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

různě barevné náhrdelníky délky , kde je Eulerova funkce [1] [2] . Toto vyplývá přímo z Polya výčtového teorému , aplikovaný na akci cyklické grupy jednat na soubor všech funkcí . $k$ $n$ $\varphi$ $C_{n}$ ${\displaystyle f:\{1,\ldots ,n\}\to \{1,\ldots ,k\))$

Počet náramků

Ano [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\ekviv 1{\pmod {2}}\end{cases}}

různé k -barevné náramky délky n , kde se rovná počtu k -barevných náhrdelníků délky n . Vyplývá to z Poyovy metody aplikované na působení dihedrální skupiny . $N_{k}(n)$ $D_{n}$

Pouzdro různých korálků

Pro danou sadu n (různých) korálků je počet odlišných náhrdelníků vyrobených z těchto korálků, za předpokladu, že otočené náhrdelníky jsou stejné, n !n= ( n − 1)!. To vyplývá ze skutečnosti, že korálky mohou být uspořádány lineárně n ! způsoby a n cyklických posunů každého takového lineárního řádu dává stejný náhrdelník. Podobně je na tom i počet různých náramků, za předpokladu, že rotace a odrazy jsou stejné n !2n _ pro . $n\geqslant 3$

Pokud se korálky neliší, to znamená, že se barvy opakují, bude počet náhrdelníků (a náramků) menší. Výše uvedené polynomy pro počítání náhrdelníků udávají počet náhrdelníků vyrobených ze všech možných více sad korálků. Výčtový polynom konfigurace Poya zlepšuje polynom počítání s proměnnou pro každou barvu korálků, takže koeficient každého monomiu bude počítat počet náhrdelníků na dané multisadě korálků.

Aperiodické náhrdelníky

Aperiodický náhrdelník délky n je třída ekvivalence rotací velikosti n , to znamená, že žádné dvě různé rotace náhrdelníku z této třídy nejsou ekvivalentní.

Podle funkce počítání náhrdelníku Moro existuje

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

různé k -barevné aperidické náhrdelníky délky n , kde je Möbiova funkce . Tyto dvě funkce počítání náhrdelníků souvisejí podle toho, kde je sumace nad všemi děliteli n , což je ekvivalentní Möbiově inverzi pro $\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))).$

Jakýkoli aperiodický náhrdelník obsahuje jedno lindonské slovo , takže Lindonova slova tvoří zástupce neperiodických náhrdelníků.

Viz také

Lindonovo slovo
Inverze (diskrétní matematika)
Problém s obnovou korálků
Problém se stříháním náhrdelníku
Permutace
Důkaz Fermatovy malé věty

Poznámky

↑ Weisstein, Eric W. Necklace na webu Wolfram MathWorld .
↑ Himach, Filipenko, 2016 , str. 93.
↑ Jakovenko, 1998 .
↑ Himach, Filipenko, 2016 , str. 94-95.

Literatura

Khimach R.A., Filipenko A.A. Vědecké fórum mládeže: Technické a matematické vědy: elektr. So. Umění. podle mat. XXXIV Stážista. stud. vědecko-praktické. conf. č. 5(34). . - 2016. - S. 90-98 .

Kaluzhin L.A., Sushchansky V.I. 13. Kombinatorické úlohy // Transformace a permutace. - M. : "Nauka", 1985. - (Problémy vědy a technického pokroku).
Jakovenko D.I. Problém s náhrdelníky // Bulletin univerzity v Omsku. - 1998. - S. 21-24 .

Odkazy

Weisstein, Eric W. Necklace (anglicky) na webových stránkách Wolfram MathWorld .
Informace o náhrdelníkech, slovech Lyndon, sekvencích De Bruijn