Colier (combinatoric)

În combinatorică , un colier cu lungime de culoare este o clasă de echivalență de șiruri de caractere peste un alfabet de dimensiune , unde șirurile obținute unul de la celălalt printr-o rotație sau o schimbare ciclică sunt considerate echivalente. De exemplu, pentru , colierul va fi setul . Colierul poate fi reprezentat vizual ca o structură de margele conectate într-un inel, având culori posibile (culorile corespund simbolurilor din alfabet): pentru a face acest lucru, trebuie să luați unul dintre cuvintele acestei clase de echivalență, fir mental. un fir prin simbolurile sale și leagă începutul și sfârșitul. $k$ $n$ $n$ $k$ $n=5$ $k=3$ $\{ababc,babca,abcab,bcaba,cabab\}$ $n$ $k$

$k$ O brățară colorată de lungime , care este denumită colier reversibil (sau liber ) , este definită în mod similar ca clasa de echivalență a șirurilor de lungime în alfabetul cu caractere, cu toate acestea, în acest caz, șirurile obținute unul de la celălalt prin rotație, simetria în oglindă sau o combinație a acestor transformări sunt considerate echivalente. Dacă recurgeți la reprezentarea vizuală a brățărilor sub formă de mărgele, diferența lor față de coliere va fi că este interzisă răsturnarea colierelor, dar brățările sunt permise. Din acest motiv, un colier poate fi numit și colier fix . De exemplu, colierul corespunzător șnurului este diferit de colierul corespunzător șnurului , dar din aceste două șiruri se obține aceeași brățară (la urma urmei, aceste două șiruri sunt obținute unul de la celălalt prin simetrie în oglindă). $n$ $n$ $k$ $ababc$ $cbaba$

Din punctul de vedere al algebrei, colierul poate fi reprezentat ca orbita grupului ciclic de acțiune pe șiruri de caractere, iar brățara ca orbita grupului diedric . Se pot număra aceste orbite și, prin urmare, numărul de astfel de coliere și brățări, folosind teorema de enumerare Poya . $n$

Clasele de echivalență

Numărul de coliere

Disponibil

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

coliere de diferite culori de lungime , unde este funcția Euler [1] [2] . Aceasta rezultă direct din teorema de enumerare a lui Polya , aplicată la acţiunea unui grup ciclic care acţionează asupra mulţimii tuturor funcţiilor . $k$ $n$ $\varphi$ $C_{n}$ $f:\{1,\ldots,n\}\la \{1,\ldots,k\)$

Numărul de brățări

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

brățări diferite de culoare k de lungime n , unde este egal cu numărul de coliere de culoare k de lungime n . Aceasta rezultă din metoda lui Poya aplicată la acțiunea grupului diedric . $N_{k}(n)$ $D_{n}$

Carcasă de mărgele diferite

Pentru un set dat de n margele (diferite), numărul de coliere distincte realizate din aceste margele, presupunând că colierele rotite sunt aceleași, este n !n= ( n − 1)!. Acest lucru rezultă din faptul că margelele pot fi aranjate liniar n ! moduri și n deplasări ciclice ale fiecărui astfel de ordin liniar dă același colier. În mod similar, numărul de brățări diferite, presupunând că rotațiile și reflexiile sunt aceleași, este n !2n _ pentru . $n\geqslant 3$

Dacă margelele nu sunt diferite, adică există o repetare a culorilor, atunci numărul de coliere (și brățări) va fi mai mic. Polinoamele de numărare a colierelor de mai sus oferă numărul de coliere realizate din toate seturile posibile de margele. Polinomul de enumerare a configurației Poya îmbunătățește polinomul de numărare cu o variabilă pentru fiecare culoare de mărgele, astfel încât coeficientul fiecărui monom va număra numărul de coliere dintr-un set multiplu dat de margele.

Coliere aperiodice

Un colier aperiodic de lungime n este o clasă de echivalență de rotații de dimensiune n , adică nu sunt echivalente două rotații diferite ale colierului din această clasă.

Conform funcției de numărare a colierului Moro , există

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

coliere aperidice diferite de culoare k de lungime n , unde este funcția Möbius . Cele două funcții de numărare a colierului sunt legate de unde însumarea este peste toți divizorii lui n , ceea ce este echivalent cu inversiunea Möbius pentru $\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))).$

Orice colier aperiodic conține un cuvânt Lindon , astfel încât cuvintele lui Lindon formează reprezentanți ai colierelor aperiodice.

Vezi și

Cuvântul lui Lindon
Inversie (matematică discretă)
Problemă de restaurare a mărgelelor
Problemă de tăiere a colierului
Permutare
Dovada Micii Teoreme a lui Fermat

Note

^ Weisstein , Eric W. Necklace pe site- ul Wolfram MathWorld .
↑ Himach, Filipenko, 2016 , p. 93.
↑ Yakovenko, 1998 .
↑ Himach, Filipenko, 2016 , p. 94-95.

Literatură

Khimach R.A., Filipenko A.A. Forum științific pentru tineret: Științe tehnice și matematice: electr. sat. Artă. prin mat. XXXIV Intern. stud. științific-practic. conf. nr. 5(34). . - 2016. - S. 90-98 .

Kaluzhin L.A., Sushchansky V.I. 13. Probleme combinatorii // Transformări și permutări. - M . : „Nauka”, 1985. - (Probleme ale științei și progresului tehnic).
Yakovenko D.I. Problemă despre coliere // Buletinul Universității din Omsk. - 1998. - S. 21-24 .

Link -uri

Weisstein, Eric W. Necklace (engleză) pe site-ul Wolfram MathWorld .
Informații despre coliere, cuvinte Lyndon, secvențe De Bruijn