Halskjede (kombinatorisk)

I kombinatorikk er et halskjede med k perler med lengde n et sirkulært ord eller til og med en ekvivalensklasse av sekvenser av n symboler på et alfabet med størrelse k , ved å betrakte som likeverdige alle sirkulære skift i sekvensen. Et halskjede kan sees på som dannet av n perler i k farger trukket i en sirkel.

Et armbånd , også kalt gratis krage eller reversibel krage, er en klasse av ekvivalens av symbolserier under de to operasjonene av sirkulær skift og av refleksjon eller reversering.

I eksemplet motsatt er armbåndet ekvivalensklassen til ordet ABCBAAC  ; avhengig av om man leser fremover eller bakover, er det to halskjeder, som er klassene til ordene ABCBAAC og CAABCBA .

I tekniske termer er et halskjede en bane av handlingen til den sykliske gruppen av orden n , mens et armbånd er en bane av handlingen til den tosidige gruppen .

Halskjeder teller

Antall krager

Det er

IKKEk(ikke)=1ikke∑d∣ikkeφ(d)kikke/d{\ displaystyle N_ {k} (n) = {\ frac {1} {n}} \ sum _ {d \ mid n} \ varphi (d) k ^ {n / d}}

lengde halskjeder på størrelse alfabetet . Her er Euler indicatrix . For det er resultatet A000031 av OEIS og for senere A054631 av OEIS . For n = 3 og n = 4 er kragen 000,001,011,111 og 0000,0001,0011,0101,0111,1111. Det er også ikke{\ displaystyle n}k{\ displaystyle k}φ{\ displaystyle \ varphi}k=2{\ displaystyle k = 2}k{\ displaystyle k}

Lk(ikke)=k!ikke∑d∣ikkeφ(d)S(ikked,k){\ displaystyle L_ {k} (n) = {\ frac {k!} {n}} \ sum _ {d \ mid n} \ varphi (d) S ({\ frac {n} {d}}, k )}

lengde halskjeder på størrelse alfabetet der hver bokstav er tilstede minst en gang. representerer Stirling Numbers av den andre typen . blir deretter A087854 av OEIS og er koblet gjennom binomiale koeffisienter: ikke{\ displaystyle n}k{\ displaystyle k}S(ikke,k){\ displaystyle {\ displaystyle S (n, k)}}Lk(ikke){\ displaystyle {\ displaystyle L_ {k} (n)}}IKKEk(ikke){\ displaystyle {\ displaystyle N_ {k} (n)}}

IKKEk(ikke)=∑j=1k(kj)Lk(ikke){\ displaystyle {\ displaystyle N_ {k} (n) = \ sum _ {j = 1} ^ {k} {\ binom {k} {j}} L_ {k} (n)}}

og

Lk(ikke)=∑j=1k(-1)k-j(kj)IKKEk(ikke){\ displaystyle {\ displaystyle L_ {k} (n) = \ sum _ {j = 1} ^ {k} (- 1) ^ {kj} {\ binom {k} {j}} N_ {k} (n )}}

Antall armbånd

Det er

Bk(ikke)={12IKKEk(ikke)+14(k+1)kikke/2hvis ikke er jevn,12IKKEk(ikke)+12k(ikke+1)/2hvis ikke er rart.{\ displaystyle B_ {k} (n) = {\ begin {cases} {1 \ over 2} N_ {k} (n) + {1 \ over 4} (k + 1) k ^ {n / 2} & {\ text {si}} n {\ text {er jevn,}} \\\\ {1 \ over 2} N_ {k} (n) + {1 \ over 2} k ^ {(n + 1) / 2} og {\ text {si}} n {\ text {er merkelig.}} \ Slutt {saker}}}

lengde armbånd på et størrelse alfabet , hvor er antall lengde halskjeder på et størrelse alfabet . ikke{\ displaystyle n}k{\ displaystyle k}IKKEk(ikke){\ displaystyle N_ {k} (n)}ikke{\ displaystyle n}k{\ displaystyle k}

Eksempler

Eksempler på halskjeder

Hvis perlene i et lengdekjede er forskjellige, er antallet halskjeder antallet sirkulære permutasjoner av orden . ikke{\ displaystyle n}ikke{\ displaystyle n}ikke!/ikke=(ikke-1)!{\ displaystyle n! / n = (n-1)!}ikke{\ displaystyle n}

Hvis tvert imot alle perlene er identiske, er det bare ett halskjede av denne fargen, så totalt så mange halskjeder som det er symboler i alfabetet.

Eksempler på armbånd

Hvis perlene i et lengdekjede er separate, er antall armbånd for . Det er det ikke , siden det i dette nummeret også er armbånd hvis perler ikke alle er forskjellige. ikke{\ displaystyle n}ikke{\ displaystyle n}ikke!/(2ikke){\ displaystyle n! / (2n)}ikke>1{\ displaystyle n> 1}Bikke(ikke){\ displaystyle B_ {n} (n)}

Aperiodiske halskjeder

Et aperiodisk halskjede er ekvivalensklassen av sekvenser der to ikke-trivielle rotasjoner aldri er like. Det tilsvarer å si at et aperiodisk halskjede er klassen til et primitivt ord , det vil si et ord som ikke er kraften til et annet ord. Starteksemplet , som tilsvarer ordet ABCBAAC , er et primitivt halskjede.

Antall aperiodiske halskjeder med lengde n på et alfabet med k bokstaver er

Mk(ikke)=1ikke∑d∣ikkeμ(d)kikke/d{\ displaystyle M_ {k} (n) = {1 \ over n} \ sum _ {d \ mid n} \ mu (d) k ^ {n / d}}.

Her er Möbius-funksjonen . Funksjonene kalles også polynomene til krage (i variabelen ), og formelen ovenfor tilskrives oberst Moreau . Faktisk teller Moreau ikke aperiodiske halskjeder, men ganske enkelt halskjeder, og til og med halskjeder som inneholder en viss fordeling av antall perler i hver farge, noe som gjør formelen hans mindre tydelig. μ{\ displaystyle \ mu}Mk(ikke){\ displaystyle M_ {k} (n)}k{\ displaystyle k}

For følgende er oppfølgeren A001037 til OEIS . For og er de aperiodiske binære krager 001,011 og 0001,0011,0111. k=2{\ displaystyle k = 2}Mk(ikke){\ displaystyle M_ {k} (n)}ikke=3{\ displaystyle n = 3}ikke=4{\ displaystyle n = 4}

Ovenstående formel er avledet fra uttrykket

kikke=∑d|ikkedMk(d){\ displaystyle k ^ {n} = \ sum _ {d \, | \, n} d \, M_ {k} (d)}

og oppnås ved Möbius inversjon .

For å etablere formelen distribuerer vi ordene med lengde  : hvert ord tilhører ett og bare ett halskjede. Hvis dette halskjedet ikke er aperiodisk, er ordet ikke et primitivt ord , og det er kraften til et enkelt primitivt ord hvis lengde deler seg . Dette primitive ordet tilhører et lengde halskjede . Dermed er hvert lengdeord i en aperiodisk lengdedelende krage, og hver krage inneholder nøyaktig d ord. Dette beviser formelen. kikke{\ displaystyle k ^ {n}}ikke{\ displaystyle n}d{\ displaystyle d}ikke{\ displaystyle n}d{\ displaystyle d}k{\ displaystyle k}ikke{\ displaystyle n}

Aperiodiske halskjeder vises i følgende sammenhenger:

• Antallet Lyndon ord av lengde av bokstaver: Enhver krage aperiodiske svarer til et enkelt ord av Lyndon , slik at ordene fra Lyndon utgjør en aperiodisk hals representanter system.ikke{\ displaystyle n}k{\ displaystyle k}
• Mk(ikke){\ displaystyle M_ {k} (n)}er dimensjonen til den homogene gradskomponenten til Lie algebra gratis på generatorer. Dette er Witt's formelikke{\ displaystyle n}k{\ displaystyle k}
• Mk(ikke){\ displaystyle M_ {k} (n)}er antall irredusible enhetspolynomer av grad over et endelig elementfelt når en styrke av et primtall.ikke{\ displaystyle n}k{\ displaystyle k}k{\ displaystyle k}
• Det er også eksponenten i den cyklotomiske identiteten  (en)  :

11-kz=∏j=1∞(11-zj)Mk(j){\ displaystyle {1 \ over 1-kz} = \ prod _ {j = 1} ^ {\ infty} \ left ({1 \ over 1-z ^ {j}} \ right) ^ {M_ {k} ( j)}}

Første verdier

Her er uttrykk for polynomier av krage for små verdier av n  :

• Mk(1)=k{\ displaystyle M_ {k} (1) = k}
• Mk(2)=(k2-k)/2{\ displaystyle M_ {k} (2) = (k ^ {2} -k) / 2}
• Mk(3)=(k3-k)/3{\ displaystyle M_ {k} (3) = (k ^ {3} -k) / 3}
• Mk(4)=(k4-k2)/4{\ displaystyle M_ {k} (4) = (k ^ {4} -k ^ {2}) / 4}
• Mk(5)=(k5-k)/5{\ displaystyle M_ {k} (5) = (k ^ {5} -k) / 5}
• Mk(6)=(k6-k3+k)/6{\ displaystyle M_ {k} (6) = (k ^ {6} -k ^ {3} + k) / 6}
• Når er et primtall, har vi det .s{\ displaystyle p}Mk(sikke)=(ksikke-ksikke-1)/sikke{\ displaystyle M_ {k} (p ^ {n}) = (k ^ {p ^ {n}} - k ^ {p ^ {n-1}}) / p ^ {n}}

Endelig,

Mkr(ikke)=∑[Jeg,j]=ikke(Jeg,j)Mk(Jeg)Mr(j){\ displaystyle \ displaystyle M_ {kr} (n) = \ sum _ {[i, j] = n} (i, j) M_ {k} (i) M_ {r} (j)},

hvor er gcd og er lcm av og . (Jeg,j){\ displaystyle (i, j)}[Jeg,j]{\ displaystyle [i, j]}Jeg{\ displaystyle i}j{\ displaystyle j}

Halskjeder Produktformel

Produktet av antall halskjeder i lengde , over symboler, innrømmer en grense når det øker og er løst; dette er IKKEk(ikke){\ displaystyle N_ {k} (n)}ikke{\ displaystyle n}k{\ displaystyle k}ikke{\ displaystyle n}k{\ displaystyle k}

limikke→∞∏m=1ikkeIKKEk(m)Xm=limikke→∞kikkeikke!1(1+X)(1+X+X2)⋯(1+X+X2+⋯+Xikke-1),{\ displaystyle \ lim _ {n \ to \ infty} \ prod _ {m = 1} ^ {n} N_ {k} (m) X ^ {m} = \ lim _ {n \ to \ infty} {\ frac {k ^ {n}} {n!}} 1 (1 + X) (1 + X + X ^ {2}) \ cdots (1 + X + X ^ {2} + \ cdots + X ^ {n -1}),}.

Koeffisienten i utviklingen av produktet (til nærmeste faktor ) er antall permutasjoner av med inversjoner , også kalt et MacMahon- nummer . Det er fortsettelsen A008302 av OEIS (Bidrag fra Mikhail Gaichenkov). Xk{\ displaystyle X ^ {k}}kikke/ikke!{\ displaystyle k ^ {n} / n!}ikke{\ displaystyle n}k{\ displaystyle k}

Relaterte artikler

• Ord fra Lyndon
• Problem med å dele en krage
• Permutasjon
• Bevis ved å dobbelttelle # Fermats lille setning
• Sterke mange  (i) brukt i atonal musikk . Forte-tall tilsvarer binære armbånd med lengde 12.
• Halskjederring  (tommer)

Merknader og referanser

Merknader

1. (i) Eric W. Weisstein , "  Halskjede  " på MathWorld
2. Lothaire 1997 , s.  79,84

(en) Denne artikkelen er helt eller delvis hentet fra artiklene rett i engelsk "  halskjede (kombinatorikk)  " ( se listen over forfattere ) og "  Necklace polynom  " ( se listen over forfattere ) .

Referanser

• M. Lothaire , kombinatorikk på ord , Cambridge University Press , koll.  "Cambridge Mathematical Library",1997, xviii + 238  s. ( ISBN  978-0-521-59924-5 , DOI  10.1017 / CBO9780511566097 , Math Reviews  1475463 , online presentasjon )Andre utgave, litt revidert, av boka utgitt under samme navn, i 1983, av Addison-Wesley, i serien "Encyclopedia of Mathematics and its Application", ( ISBN  978-0-201-13516-9 )
• (no) Richard P. Stanley , Enumerative Combinatorics [ detalj av utgaver ] ( online presentasjon )
• C. Moreau , “  On distinkte sirkulære permutasjoner  ”, Nouvelles Annales de mathematique , journal des Ecoles kandidater aux polytechnique et normale , 2 nd serie, vol.  11,1872, s.  309–314 ( les online )
• Nicholas Metropolis og Gian-Carlo Rota , "  Witt-vektorer og algebraen til halskjeder  ", Advances in Mathematics , vol.  50, n o  to1983, s.  95–125 ( DOI  10.1016 / 0001-8708 (83) 90035-X , Matematikkanmeldelser  723197 , zbMATH  0545.05009 )
• Gabriele Fici , Antonio Restivo og Laura Rizzo , “  Minimal forbudte faktorer av sirkulære ord  ”, Theoretical Computer Science , vol.  792,2019, s.  144–153 ( DOI  10.1016 / j.tcs.2018.05.037 )

Ekstern lenke

(en) Frank Ruskey, “Informasjon om halskjeder, Lyndon Words, av Bruijn Sequences” .

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">