Colier (combinator)
În combinatorie , un colier de k margele de lungime n este un cuvânt circular sau chiar o clasă de echivalență a secvențelor de n simboluri pe un alfabet de dimensiunea k , considerând ca echivalente toate schimbările circulare din secvență. Un colier poate fi văzut ca fiind format din n mărgele de k culori strânse în cerc.
O brățară , numită și guler liber sau guler reversibil, este o clasă de echivalență a seriei de simboluri în cadrul celor două operații de deplasare circulară și de reflecție sau inversare.
În exemplul opus, brățara este clasa de echivalență a cuvântului ABCBAAC ; în funcție de citirea în direcție înainte sau inversă, există două coliere, care sunt clasele cuvintelor ABCBAAC și CAABCBA .
În termeni tehnici, un colier este o orbită de acțiune de grup ciclică de ordinul n , în timp ce o brățară este o orbită de acțiune de grup diedrică .
Colierele contează
Numărul de gulere
Există
NUk(nu)=1nu∑d∣nuφ(d)knu/d{\ displaystyle N_ {k} (n) = {\ frac {1} {n}} \ sum _ {d \ mid n} \ varphi (d) k ^ {n / d}}![N_k (n) = \ frac1n \ sum_ {d \ mid n} \ varphi (d) k ^ {n / d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d196a8c31df94e6290adb14659639d8a71007c4)
coliere de lungime pe un alfabet de dimensiuni . Aici este indicatrix Euler . Pentru , este rezultatul A000031 al OEIS și pentru orice A054631 ulterior al OEIS . Pentru n = 3 și n = 4, gulerele sunt 000,001,011,111 și 0000,0001,0011,0101,0111,1111. Există deasemenea
nu{\ displaystyle n}
k{\ displaystyle k}
φ{\ displaystyle \ varphi}
k=2{\ displaystyle k = 2}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Lk(nu)=k!nu∑d∣nuφ(d)S(nud,k){\ displaystyle L_ {k} (n) = {\ frac {k!} {n}} \ sum _ {d \ mid n} \ varphi (d) S ({\ frac {n} {d}}, k )}}![{\ displaystyle L_ {k} (n) = {\ frac {k!} {n}} \ sum _ {d \ mid n} \ varphi (d) S ({\ frac {n} {d}}, k )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2979de144f6a06a54c519da9f0109dbfac98dc46)
coliere de lungime pe un alfabet de dimensiuni în care fiecare literă este prezentă cel puțin o dată. reprezintă numerele Stirling de al doilea fel . este ulterior A087854 al OEIS și este conectat prin coeficienții binomiali:
nu{\ displaystyle n}
k{\ displaystyle k}
S(nu,k){\ displaystyle {\ displaystyle S (n, k)}}
Lk(nu){\ displaystyle {\ displaystyle L_ {k} (n)}}
NUk(nu){\ displaystyle {\ displaystyle N_ {k} (n)}}![{\ displaystyle {\ displaystyle N_ {k} (n)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4b6f0db007f72b7f7d267354e58229ccd4378b2)
NUk(nu)=∑j=1k(kj)Lk(nu){\ displaystyle {\ displaystyle N_ {k} (n) = \ sum _ {j = 1} ^ {k} {\ binom {k} {j}} L_ {k} (n)}}![{\ displaystyle {\ displaystyle N_ {k} (n) = \ sum _ {j = 1} ^ {k} {\ binom {k} {j}} L_ {k} (n)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf1e7889ab9c5f487985807aedd052c32e3bd230)
și
Lk(nu)=∑j=1k(-1)k-j(kj)NUk(nu){\ displaystyle {\ displaystyle L_ {k} (n) = \ sum _ {j = 1} ^ {k} (- 1) ^ {kj} {\ binom {k} {j}} N_ {k} (n )}}![{\ displaystyle {\ displaystyle L_ {k} (n) = \ sum _ {j = 1} ^ {k} (- 1) ^ {kj} {\ binom {k} {j}} N_ {k} (n )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ee4ca3bc651b4dfed0acb4606551343935cbf8f)
Numărul de brățări
Există
Bk(nu)={12NUk(nu)+14(k+1)knu/2dacă nu este chiar,12NUk(nu)+12k(nu+1)/2dacă nu este ciudat.{\ displaystyle B_ {k} (n) = {\ begin {cases} {1 \ over 2} N_ {k} (n) + {1 \ over 4} (k + 1) k ^ {n / 2} și {\ text {si}} n {\ text {este egal,}} \\\\ {1 \ peste 2} N_ {k} (n) + {1 \ peste 2} k ^ {(n + 1) / 2} & {\ text {si}} n {\ text {este ciudat.}} \ End {cases}}}![B_k (n) = \ begin {cases} {1 \ over 2} N_k (n) + {1 \ over 4} (k + 1) k ^ {n / 2} & \ text {si} n \ text {este chiar,} \\ \\ {1 \ peste 2} N_k (n) + {1 \ peste 2} k ^ {(n + 1) / 2} și \ text {dacă} n \ text {este ciudat.} \ sfârșit {cazuri}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da2e93d259f65574640947b8ccf1674bc12f0e1f)
lungime brățări pe un alfabet dimensiune , unde
este numărul de lungime coliere pe un alfabet dimensiune .
nu{\ displaystyle n}
k{\ displaystyle k}
NUk(nu){\ displaystyle N_ {k} (n)}
nu{\ displaystyle n}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Exemple
Exemple de coliere
Dacă mărgelele unui colier lung sunt toate distincte, atunci numărul de coliere este , numărul de permutări circulare de ordine .
nu{\ displaystyle n}
nu{\ displaystyle n}
nu!/nu=(nu-1)!{\ displaystyle n! / n = (n-1)!}
nu{\ displaystyle n}![nu](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Dacă, dimpotrivă, toate perlele sunt identice, există un singur colier de această culoare, deci, în total, atâtea coliere câte simboluri există în alfabet.
Exemple de brățări
Dacă mărgelele unui colier lung sunt toate separate, numărul de brățări este pentru . Nu este , deoarece în acest număr există și brățări ale căror perle nu sunt toate distincte.
nu{\ displaystyle n}
nu{\ displaystyle n}
nu!/(2nu){\ displaystyle n! / (2n)}
nu>1{\ displaystyle n> 1}
Bnu(nu){\ displaystyle B_ {n} (n)}![B_n (n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d038060771e176e072538df7d190cc11b0791b2)
Coliere periodice
Un colier aperiodic este clasa de echivalență a secvențelor din care două rotații non-banale nu sunt niciodată egale. Este echivalent să spunem că un colier aperiodic este clasa unui cuvânt primitiv , adică a unui cuvânt care nu este puterea unui alt cuvânt. Exemplul de început, care corespunde cuvântului ABCBAAC , este un colier primitiv.
Numărul de coliere aperiodice de lungime n pe un alfabet cu k litere este
Mk(nu)=1nu∑d∣nuμ(d)knu/d{\ displaystyle M_ {k} (n) = {1 \ peste n} \ sum _ {d \ mid n} \ mu (d) k ^ {n / d}}![M_k (n) = {1 \ peste n} \ sum_ {d \ mid n} \ mu (d) k ^ {n / d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce1c879709aba5b7b1baa71e9076a868e7f09cbe)
.
Aici este funcția Möbius . Funcțiile sunt numite și polinoame ale gulerelor (în variabilă ), iar formula de mai sus este atribuită colonelului Moreau . De fapt, Moreau nu ia în considerare colierele aperiodice, ci pur și simplu colierele și chiar colierele care conțin o anumită distribuție a numărului de perle de fiecare culoare, ceea ce face formula sa mai puțin clară.
μ{\ displaystyle \ mu}
Mk(nu){\ displaystyle M_ {k} (n)}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Căci , urmează continuarea A001037 a OEIS . Pentru și , gulerele binare aperiodice sunt 001.011 și 0001.0011.0111.
k=2{\ displaystyle k = 2}
Mk(nu){\ displaystyle M_ {k} (n)}
nu=3{\ displaystyle n = 3}
nu=4{\ displaystyle n = 4}![n = 4](https://wikimedia.org/api/rest_v1/media/math/render/svg/d928ec15aeef83aade867992ee473933adb6139d)
Formula de mai sus este derivată din expresie
knu=∑d|nudMk(d){\ displaystyle k ^ {n} = \ sum _ {d \, | \, n} d \, M_ {k} (d)}![k ^ n = \ sum_ {d \, | \, n} d \, M_k (d)](https://wikimedia.org/api/rest_v1/media/math/render/svg/68db60b2b4866ef85825b8c14175820fe1d7fffe)
și se obține prin inversare Möbius .
Pentru a stabili formula, distribuim
cuvintele de lungime : fiecare cuvânt aparține unuia și unui singur colier. Dacă acest colier nu este aperiodic, cuvântul nu este un cuvânt primitiv și este puterea unui singur cuvânt primitiv a cărui lungime se împarte . Acest cuvânt primitiv aparține unui colier lung . Astfel, fiecare cuvânt de lungime se află într-un guler aperiodic care împarte lungimea și fiecare guler conține exact d cuvinte. Aceasta dovedește formula.
knu{\ displaystyle k ^ {n}}
nu{\ displaystyle n}
d{\ displaystyle d}
nu{\ displaystyle n}
d{\ displaystyle d}
k{\ displaystyle k}
nu{\ displaystyle n}![nu](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Colierele periodice apar în următoarele contexte:
- Numărul de cuvinte Lyndon de lungime de litere: Orice guler corespunde aperiodice la un singur cuvânt de Lyndon , astfel încât cuvintele Lyndon formează un sistem de reprezentanții coliere aperiodice.nu{\ displaystyle n}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
-
Mk(nu){\ displaystyle M_ {k} (n)}
este dimensiunea componentei omogene a gradului de algebră Lie liberă pe generatoare. Aceasta este formula lui Wittnu{\ displaystyle n}
k{\ displaystyle k}
-
Mk(nu){\ displaystyle M_ {k} (n)}
este numărul de polinoame unitare ireductibile de grad pe un câmp de element finit atunci când o putere de număr prim.nu{\ displaystyle n}
k{\ displaystyle k}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
- Este, de asemenea, exponentul în identitatea ciclotomică (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)}}![{1 \ over 1-kz} = \ prod_ {j = 1} ^ \ infty \ left ({1 \ over 1-z ^ j} \ right) ^ {M_k (j)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/539f717f64d4634c601f2f8a29f52604702beaf2)
Primele valori
Iată expresiile polinoamelor colierelor pentru valori mici ale lui n :
- Mk(1)=k{\ displaystyle M_ {k} (1) = k}
![M_k (1) = k](https://wikimedia.org/api/rest_v1/media/math/render/svg/91812854c0db9c62d9ed2feac1d52d3126557309)
- Mk(2)=(k2-k)/2{\ displaystyle M_ {k} (2) = (k ^ {2} -k) / 2}
![M_k (2) = (k ^ 2-k) / 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/db36b95e3a5cc5ee05ed2cb7002cebd9b959d7db)
- Mk(3)=(k3-k)/3{\ displaystyle M_ {k} (3) = (k ^ {3} -k) / 3}
![M_k (3) = (k ^ 3-k) / 3](https://wikimedia.org/api/rest_v1/media/math/render/svg/068b56fe1087205ad2d1ef5ba09256fac0d0ad57)
- Mk(4)=(k4-k2)/4{\ displaystyle M_ {k} (4) = (k ^ {4} -k ^ {2}) / 4}
![M_k (4) = (k ^ 4-k ^ 2) / 4](https://wikimedia.org/api/rest_v1/media/math/render/svg/9807938dac030850ac666e1f0430c6e091013f68)
- Mk(5)=(k5-k)/5{\ displaystyle M_ {k} (5) = (k ^ {5} -k) / 5}
![M_k (5) = (k ^ 5-k) / 5](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d40ea2bf4e0a8dc9ea4bab25a0ada986e34badd)
- Mk(6)=(k6-k3+k)/6{\ displaystyle M_ {k} (6) = (k ^ {6} -k ^ {3} + k) / 6}
![M_k (6) = (k ^ 6-k ^ 3 + k) / 6](https://wikimedia.org/api/rest_v1/media/math/render/svg/218b557bb65f1182accaca48fdef06ae3fe9baee)
- Când este un număr prim, avem .p{\ displaystyle p}
Mk(pnu)=(kpnu-kpnu-1)/pnu{\ displaystyle M_ {k} (p ^ {n}) = (k ^ {p ^ {n}} - k ^ {p ^ {n-1}}) / p ^ {n}}![M_k (p ^ n) = (k ^ {p ^ n} -k ^ {p ^ {n-1}}) / p ^ n](https://wikimedia.org/api/rest_v1/media/math/render/svg/81fe56cc4bfbc24047fe41ca12125aa549b8ec2f)
In cele din urma,
Mkr(nu)=∑[eu,j]=nu(eu,j)Mk(eu)Mr(j){\ displaystyle \ displaystyle M_ {kr} (n) = \ sum _ {[i, j] = n} (i, j) M_ {k} (i) M_ {r} (j)}![\ displaystyle M_ {kr} (n) = \ sum _ {[i, j] = n} (i, j) M_k (i) M_r (j)](https://wikimedia.org/api/rest_v1/media/math/render/svg/074b037e627cca0b99a05bb29daa0a5be9831000)
,
unde este mcd și este mcm al și .
(eu,j){\ displaystyle (i, j)}
[eu,j]{\ displaystyle [i, j]}
eu{\ displaystyle i}
j{\ displaystyle j}![j](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f461e54f5c093e92a55547b9764291390f0b5d0)
Coliere Formula produsului
Produsul numărului de coliere de lungime , peste simboluri, admite o limită la creștere și este fixat; aceasta este
NUk(nu){\ displaystyle N_ {k} (n)}
nu{\ displaystyle n}
k{\ displaystyle k}
nu{\ displaystyle n}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
limnu→∞∏m=1nuNUk(m)Xm=limnu→∞knunu!1(1+X)(1+X+X2)⋯(1+X+X2+⋯+Xnu-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}),}![\ 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}),](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0f117d97c9f18a38d88ff6e354bb5bec6e5af03)
.
Coeficientul de la dezvoltarea produsului (la cel mai apropiat factor ) este numărul de permutări de cu inversiuni , de asemenea , numit un MacMahon număr . Este continuarea A008302 a OEIS (Contribuția lui Mihail Gaichenkov).
Xk{\ displaystyle X ^ {k}}
knu/nu!{\ displaystyle k ^ {n} / n!}
nu{\ displaystyle n}
k{\ displaystyle k}
Articole similare
Note și referințe
Note
-
(în) Eric W. Weisstein , „ Colier ” pe MathWorld
-
Lothaire 1997 , p. 79,84
(ro) Acest articol este preluat parțial sau în totalitate din articolele intitulate în
engleză „ Necklace (combinatorics) ” (a se vedea lista autorilor ) și
„ Necklace polynomial ” (a se vedea lista autorilor ) .
Referințe
-
M. Lothaire , Combinatorics on words , Cambridge University Press , col. „Biblioteca matematică Cambridge”,1997, xviii + 238 p. ( ISBN 978-0-521-59924-5 , DOI 10.1017 / CBO9780511566097 , Math Reviews 1475463 , prezentare online )A doua ediție, ușor revizuită, a cărții publicate sub același nume, în 1983, de Addison-Wesley, în seria „Enciclopedia matematicii și aplicația sa”, ( ISBN 978-0-201-13516-9 )
- (ro) Richard P. Stanley , Enumerative Combinatorics [ detaliu ediții ] ( prezentare online )
- C. Moreau , „ On distinct circular permutations ”, Nouvelles annales de mathematique , journal des candidates aux écoles polytechnique and normal , 2 nd series, vol. 11,1872, p. 309–314 ( citește online )
- Nicholas Metropolis și Gian-Carlo Rota , „ Vectorii Witt și algebra colierelor ”, Advances in Mathematics , vol. 50, n o 21983, p. 95–125 ( DOI 10.1016 / 0001-8708 (83) 90035-X , Recenzii matematice 723197 , zbMATH 0545.05009 )
- Gabriele Fici , Antonio Restivo și Laura Rizzo , „ Factori minimi interziși ai cuvintelor circulare ”, Theoretical Computer Science , vol. 792,2019, p. 144–153 ( DOI 10.1016 / j.tcs.2018.05.037 )
Link extern
(ro) Frank Ruskey, „Informații despre coliere, cuvinte Lyndon, de 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;">