Kaulakoru (kombinatorio)

Kombinatoriikassa värillinen pituinen kaulakoru on -merkkijonojen ekvivalenssiluokka koon aakkoston yli , jossa toisistaan pyörittämällä tai syklisellä siirrolla saatuja merkkijonoja pidetään vastaavina. Esimerkiksi kaulakoru on sarja . Kaulakoru voidaan esittää visuaalisesti renkaaseen yhdistetyistä helmistä koostuvana rakenteena, jolla on mahdolliset värit (värit vastaavat aakkosten symboleja): tätä varten sinun on otettava yksi tämän vastaavuusluokan sanoista, henkisesti lanka kierre symbolien läpi ja yhdistä sen alku ja loppu. $k$ $n$ $n$ $k$ $n = 5$ $k = 3$ $\{ababc,babca,abcab,bcaba,cabab\}$ $n$ $k$

$k$ Pituuksinen -värinen rannekoru , jota kutsutaan käännettäväksi (tai vapaaksi ) kaulakoruksi , määritellään samalla tavalla merkkiaakkoston pituusmerkkijonojen vastaavuusluokiksi, mutta tässä tapauksessa toisistaan kiertämällä saadut kielet, peilisymmetriaa tai näiden muunnosten yhdistelmää pidetään vastaavina. Jos turvaudut rannekorujen visuaaliseen esitykseen helmien muodossa, niiden ero kaulakoruihin on se, että kaulakoruja ei saa kääntää, mutta rannekorut ovat sallittuja. Tästä syystä kaulakorua voidaan kutsua myös kiinteäksi kaulakoruksi . Esimerkiksi merkkijonoa vastaava kaulakoru on erilainen kuin merkkijonoa vastaava kaulakoru , mutta näistä kahdesta nauhasta saadaan sama rannekoru (nämä kaksi nauhaa on loppujen lopuksi saatu toisistaan peilisymmetrian avulla). $n$ $n$ $k$ $ababc$ $cbaba$

Algebran näkökulmasta kaulakoru voidaan esittää -merkkijonojen syklisen toimintaryhmän kiertoradana ja rannekoru dihedraalisen ryhmän kiertoradana . Nämä kiertoradat ja siten tällaisten kaulakorujen ja rannekorujen lukumäärä voidaan laskea käyttämällä Poyan numeraatiolausetta . $n$

Ekvivalenssiluokat

Kaulakorujen lukumäärä

Saatavilla

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

pituiset eriväriset kaulakorut , jossa on Euler-funktio [1] [2] . Tämä seuraa suoraan Polya-laskentalauseesta , jota sovelletaan syklisen ryhmän toimintaan, joka vaikuttaa kaikkien funktioiden joukkoon . $k$ $n$ $\varphi$ $C_{n}$ ${\displaystyle f:\{1,\ldots ,n\}\to \{1,\ldots ,k\))$

Rannekorujen määrä

Kyllä [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}}

erilaisia k -värisiä rannekoruja, joiden pituus on n , missä on yhtä suuri kuin k - väristen kaulakorujen lukumäärä, joiden pituus on n . Tämä seuraa Poyan menetelmästä , jota sovellettiin dihedraaliryhmän toimintaan . $N_{k}(n)$ $D_{n}$

Eri helmien kotelo

Tietylle n (erilaisen) helmen sarjalle näistä helmistä valmistettujen erillisten kaulakorujen määrä, olettaen, että kierretyt kaulakorut ovat samat, on n !n= ( n − 1)!. Tämä johtuu siitä, että helmet voidaan järjestää lineaarisesti n ! Jokaisen tällaisen lineaarisen järjestyksen tapa ja n syklistä siirtymää antaa saman kaulakorun. Samoin eri rannekorujen määrä, jos pyörähdysten ja heijastusten olevan sama, on n !2n _ varten . $n\geqslant 3$

Jos helmet eivät ole erilaisia, toisin sanoen värit toistuvat, kaulakorujen (ja rannekorujen) määrä on pienempi. Yllä olevat kaulakorujen laskentapolynomit antavat kaikista mahdollisista helmisarjoista valmistettujen kaulakorujen lukumäärän . Poya- konfiguraatiolaskentapolynomi parantaa laskentapolynomia muuttujalla jokaiselle helmen värille, niin että kunkin monomin kerroin laskee kaulakorujen lukumäärän tietyssä helmisarjassa.

Ajanjaksoiset kaulakorut

Ajoittainen kaulakoru , jonka pituus on n , on koon n kiertojen ekvivalenssiluokka , eli kaksi erilaista kaulakorun kiertoa tästä luokasta eivät ole ekvivalentteja.

Moro kaulakorun laskentatoiminnon mukaan on

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

erilaiset k -väriset apperidic-kaulakorut, joiden pituus on n , missä on Möbius-funktio . Nämä kaksi kaulakorun laskentafunktiota liittyvät siihen , missä summa on yli kaikkien n:n jakajien , mikä vastaa Möbiuksen inversiota $\mu$ $N_{k}(n)\ =\ \sum \nlimits _{d|n}M_{k}(d),$ $M_{k}(n)\ =\ \sum \nlimits _{d|n}N_{k}(d)\,\mu ({\tfrac {n}{d))).$

Mikä tahansa jaksollinen kaulakoru sisältää yhden Lindon-sanan , joten Lindonin sanat muodostavat edustajia jaksollisista kaulakoruista.

Katso myös

Lindonin sana
Inversio (diskreetti matematiikka)
Helmien kunnostusongelma
Kaulakorun leikkaus ongelma
permutaatio
Todiste Fermatin pienestä lauseesta

Muistiinpanot

↑ Weisstein, Eric W. Kaulakoru Wolfram MathWorld -verkkosivustolla .
↑ Himach, Filipenko, 2016 , s. 93.
↑ Yakovenko, 1998 .
↑ Himach, Filipenko, 2016 , s. 94-95.

Kirjallisuus

Khimach R.A., Filipenko A.A. Nuorten tieteellinen foorumi: Tekniset ja matemaattiset tieteet: sähkö. la Taide. maton mukaan. XXXIV Harjoittelija. nasta. tieteellis-käytännöllinen. konf. nro 5(34). . - 2016. - S. 90-98 .

Kaluzhin L.A., Sushchansky V.I. 13. Kombinatoriset ongelmat // Transformaatiot ja permutaatiot. - M . : "Nauka", 1985. - (Tieteen ja teknisen kehityksen ongelmat).
Yakovenko D.I. Ongelma kaulakoruista // Omskin yliopiston tiedote. - 1998. - S. 21-24 .

Linkit

Weisstein, Eric W. Necklace (englanniksi) Wolfram MathWorld -verkkosivustolla .
Tietoja kaulakoruista, Lyndon-sanoista, De Bruijn-sekvensseistä