Nyaklánc (kombinatorikus)
A kombinatorikai , a nyaklánc a k gyöngyök hosszúságú n egy kör alakú szó , vagy akár egy ekvivalencia osztálya szekvenciák n szimbólum egy abc méret k , figyelembe véve egyenértékűnek összes körkörös eltolódások a szekvenciában. Egy nyaklánc úgy tekinthető, mintha n körből körbefűzött k színű gyöngyből állna.
A karkötő , amelyet szabad gallérnak vagy megfordítható gallérnak is neveznek, a szimbólumok sorozatának egyenértékűségi osztálya a körkörös eltolás és a visszaverődés vagy a megfordítás két művelete alatt.
A szemközti példában a karkötő az ABCBAAC szó egyenértékűségi osztálya ; attól függően, hogy az ember előre vagy hátra olvas-e, két nyaklánc van, amelyek az ABCBAAC és a CAABCBA szavak osztályai .
Műszaki szempontból a nyaklánc az n rendű ciklikus csoport működésének pályája , míg a karkötő a kétdimenziós csoport pályájának pályája .
A nyakláncok számítanak
Gallérok száma
Van
NEMk(nem)=1nem∑d∣nemφ(d)knem/d{\ displaystyle N_ {k} (n) = {\ frac {1} {n}} \ sum _ {d \ mid n} \ varphi (d) k ^ {n / d}}![N_k (n) = \ frac1n \ sum_ {d \ n közepe} \ varphi (d) k ^ {n / d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d196a8c31df94e6290adb14659639d8a71007c4)
hosszúságú nyakláncok nagyságú ábécén . Itt van az Euler indicatrix . Mert , ez az eredmény A000031 a OEIS-ben és bármilyen későbbi A054631 a OEIS-ben . N = 3 és n = 4 esetén a gallérok 000,001,011,111 és 0000,0001,0011,0101,0111,1111. Van még
nem{\ 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(nem)=k!nem∑d∣nemφ(d)S(nemd,k){\ displaystyle L_ {k} (n) = {\ frac {k!} {n}} \ sum _ {d \ n n közepe} \ varphi (d) S ({\ frac {n} {d}}, k )}![{\ displaystyle L_ {k} (n) = {\ frac {k!} {n}} \ sum _ {d \ n n közepe} \ varphi (d) S ({\ frac {n} {d}}, k )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2979de144f6a06a54c519da9f0109dbfac98dc46)
hosszúságú nyakláncok olyan méretű ábécén, ahol minden betű legalább egyszer szerepel. képviseli a Stirling számok a második fajta . ezután az OEIS A087854 kódja és a binomiális együtthatókon keresztül kapcsolódik :
nem{\ displaystyle n}
k{\ displaystyle k}
S(nem,k){\ displaystyle {\ displaystyle S (n, k)}}
Lk(nem){\ displaystyle {\ displaystyle L_ {k} (n)}}
NEMk(nem){\ displaystyle {\ displaystyle N_ {k} (n)}}![{\ displaystyle {\ displaystyle N_ {k} (n)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4b6f0db007f72b7f7d267354e58229ccd4378b2)
NEMk(nem)=∑j=1k(kj)Lk(nem){\ 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)
és
Lk(nem)=∑j=1k(-1)k-j(kj)NEMk(nem){\ 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)
Karkötők száma
Van
Bk(nem)={12NEMk(nem)+14(k+1)knem/2ha nem egyenlő,12NEMk(nem)+12k(nem+1)/2ha nem furcsa.{\ displaystyle B_ {k} (n) = {\ kezdődik {esetek} {1 \ több mint 2} N_ {k} (n) + {1 \ több mint 4} (k + 1) k ^ {n / 2} & {\ text {si}} n {\ text {egyenletes,}} \\\\ {1 \ 2 felett} N_ {k} (n) + {1 \ felett 2} k ^ {(n + 1) / 2} és a {\ text {si}} n {\ text {páratlan.}} \ End {esetek}}}![B_k (n) = \ kezdődik {esetek} {1 \ több mint 2} N_k (n) + {1 \ több mint 4} (k + 1) k ^ {n / 2} és \ szöveg {si} n \ szöveg { páros,} \\ \\ {1 \ over 2} N_k (n) + {1 \ over 2} k ^ {(n + 1) / 2} & \ text {if} n \ text {páratlan.} \ {esetek} vége](https://wikimedia.org/api/rest_v1/media/math/render/svg/da2e93d259f65574640947b8ccf1674bc12f0e1f)
hosszúságú karkötők méret ábécén , ahol
a hosszúságú nyakláncok száma egy méret ábécén .
nem{\ displaystyle n}
k{\ displaystyle k}
NEMk(nem){\ displaystyle N_ {k} (n)}
nem{\ displaystyle n}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Példák
Példák nyakláncokra
Ha a hosszúságú nyaklánc gyöngyei mind megkülönböztethetők, akkor a nyakláncok száma a kör alakú permutációk száma .
nem{\ displaystyle n}
nem{\ displaystyle n}
nem!/nem=(nem-1)!{\ displaystyle n! / n = (n-1)!}
nem{\ displaystyle n}![nem](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Ha éppen ellenkezőleg, az összes gyöngy azonos, csak egy ilyen színű nyaklánc van, tehát összesen annyi nyaklánc, ahány szimbólum van az ábécében.
Példák karkötőkre
Ha a hosszúságú nyaklánc gyöngyei mind külön vannak, akkor a karkötők száma az . Nem , mivel ebben a számban vannak olyan karkötők is, amelyek gyöngyszeme nem mindegyik különbözik egymástól.
nem{\ displaystyle n}
nem{\ displaystyle n}
nem!/(2nem){\ displaystyle n! / (2n)}
nem>1{\ displaystyle n> 1}
Bnem(nem){\ displaystyle B_ {n} (n)}![B_n (n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d038060771e176e072538df7d190cc11b0791b2)
Aperiodikus nyakláncok
Az aperiodikus nyaklánc a szekvenciák ekvivalenciaosztálya, amelyeknek két nem triviális forgatása soha nem egyenlő. Ez egyenértékű azzal, ha azt mondjuk, hogy az aperiodikus nyaklánc egy primitív szó osztálya , vagyis olyan szó, amely nem egy másik szó ereje. A kezdő példa, amely megfelel az ABCBAAC szónak , egy primitív nyaklánc.
Az n hosszúságú aperiodikus nyakláncok száma egy k betűs ábécén :
Mk(nem)=1nem∑d∣nemμ(d)knem/d{\ displaystyle M_ {k} (n) = {1 \ felett n} \ sum _ {d \ n közepén \ mu (d) k ^ {n / d}}![M_k (n) = {1 \ felett n} \ sum_ {d \ n közepén} \ mu (d) k ^ {n / d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce1c879709aba5b7b1baa71e9076a868e7f09cbe)
.
Itt van a Möbius függvény . A függvényeket gallérok polinomjainak is nevezik (a változóban ), és a fenti képletet Moreau ezredesnek tulajdonítják . Valójában Moreau nem aperiodikus nyakláncokat, hanem egyszerűen nyakláncokat, sőt nyakláncokat is számlál, amelyek az egyes színű gyöngyök számának bizonyos eloszlását tartalmazzák, ami kevésbé egyértelművé teszi képletét.
μ{\ displaystyle \ mu}
Mk(nem){\ displaystyle M_ {k} (n)}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Mert , a következő a folytatást A001037 az OEIS-ben . Mert valamint az aperiodikus bináris nyakörvek 001.011 és 0001,0011,0111.
k=2{\ displaystyle k = 2}
Mk(nem){\ displaystyle M_ {k} (n)}
nem=3{\ displaystyle n = 3}
nem=4{\ displaystyle n = 4}![n = 4](https://wikimedia.org/api/rest_v1/media/math/render/svg/d928ec15aeef83aade867992ee473933adb6139d)
A fenti képlet a kifejezésből származik
knem=∑d|nemdMk(d){\ displaystyle k ^ {n} = \ sum _ {d \, | \, n} d \, M_ {k} (d)}![k ^ n = \ összeg_ {d \, | \, n} d \, M_k (d)](https://wikimedia.org/api/rest_v1/media/math/render/svg/68db60b2b4866ef85825b8c14175820fe1d7fffe)
és Möbius inverzióval nyerik .
A képlet megállapításához elosztjuk a
hosszúság szavakat : minden szó egy és csak egy nyaklánchoz tartozik. Ha ez a nyaklánc nem aperiodikus, akkor a szó nem primitív szó , és egyetlen primitív szó ereje, amelynek hossza megoszlik . Ez a primitív szó egy hosszúságú nyaklánchoz tartozik . Így minden hosszúságú szó aperiódikus hosszúságot osztó gallérban van, és minden gallér pontosan d szót tartalmaz. Ez bizonyítja a képletet.
knem{\ displaystyle k ^ {n}}
nem{\ displaystyle n}
d{\ displaystyle d}
nem{\ displaystyle n}
d{\ displaystyle d}
k{\ displaystyle k}
nem{\ displaystyle n}![nem](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Az aperiódikus nyakláncok a következő összefüggésekben jelennek meg:
- Száma Lyndon szavak hossza a betűk: Bármely gallér aperiodikus megfelel egyetlen szót Lyndon úgy, hogy a szavak Lyndon alkotnak aperiodikus nyakláncok képviselői rendszert.nem{\ displaystyle n}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
-
Mk(nem){\ displaystyle M_ {k} (n)}
a Lie algebra homogén komponensének dimenziója a generátorokon kívül. Ez Witt képletenem{\ displaystyle n}
k{\ displaystyle k}
-
Mk(nem){\ displaystyle M_ {k} (n)}
a végtelen elemű mező fölötti fokú irreducibilis egységpolinomok száma, ha egy prímszám hatványa.nem{\ displaystyle n}
k{\ displaystyle k}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
- A ciklotomikus azonosság (en) kitevője is :
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)
Első értékek
Az alábbiakban a gallérok polinomjainak kifejezései n kis értéke eseté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)
- Mikor van prímszám, megvan .o{\ displaystyle p}
Mk(onem)=(konem-konem-1)/onem{\ 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)
Végül,
Mkr(nem)=∑[én,j]=nem(én,j)Mk(én)Mr(j){\ displaystyle \ displaystyle M_ {kr} (n) = \ összeg _ {[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)
,
ahol a GCD és az LCM a és .
(én,j){\ displaystyle (i, j)}
[én,j]{\ displaystyle [i, j]}
én{\ displaystyle i}
j{\ displaystyle j}![j](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f461e54f5c093e92a55547b9764291390f0b5d0)
Nyakláncok termékképlete
A hosszúságú nyakláncok számának szorzata, a szimbólumok fölött , megengedi a korlátot, ha növekszik és rögzített; ez
NEMk(nem){\ displaystyle N_ {k} (n)}
nem{\ displaystyle n}
k{\ displaystyle k}
nem{\ displaystyle n}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
limnem→∞∏m=1nemNEMk(m)xm=limnem→∞knemnem!1(1+x)(1+x+x2)⋯(1+x+x2+⋯+xnem-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)
.
A relatív a termék fejlesztése (a legközelebbi tényező ) az a szám, permutációk az a inverzió , más néven MacMahon számot . Ez a folytatása A008302 A OEIS-ben (Hozzájárulás Mihail Gaichenkov).
xk{\ displaystyle X ^ {k}}
knem/nem!{\ displaystyle k ^ {n} / n!}
nem{\ displaystyle n}
k{\ displaystyle k}
Kapcsolódó cikkek
Megjegyzések és hivatkozások
Megjegyzések
-
(in) Eric W. Weisstein , " Nyaklánc " a MathWorld- on
-
Lothaire 1997 , p. 79.84
(en) Ez a cikk részben vagy egészben az
angol „ Necklace (combinatorics) ” ( lásd a szerzők listáját ) és a
„ Necklace polynomial ” ( lásd a szerzők felsorolását ) című cikkekből származik .
Hivatkozások
-
M. Lothaire , a szavak kombinatorikája , Cambridge University Press , koll. "Cambridge Mathematical Library",1997, xviii + 238 o. ( ISBN 978-0-521-59924-5 , DOI 10.1017 / CBO9780511566097 , Math Reviews 1475463 , online előadás )Az azonos nevű, 1983-ban Addison-Wesley által kiadott könyv második kiadása, kissé átdolgozva, a "Matematika enciklopédiája és alkalmazása" sorozatban ( ISBN 978-0-201-13516-9 )
- (en) Richard P. Stanley , Enumeratív kombinatorika [ a kiadások részlete ] ( online bemutató )
- C. Moreau , „ On különálló körkörös permutációk ”, Nouvelles Annales de mathématique , Journal des jelöltek aux Écoles polytechnique et normale , 2 ND sorozat, vol. 11,1872, P. 309–314 ( online olvasás )
- Nicholas Metropolis és Gian-Carlo Rota , „ Witt vektorok és a nyakláncok algebra ”, Advances in Mathematics , vol. 50, n o 21983, P. 95–125 ( DOI 10.1016 / 0001-8708 (83) 90035-X , Math Reviews 723197 , zbMATH 0545.05009 )
- Gabriele Fici , Antonio Restivo és Laura Rizzo , „ A körkörös szavak minimálisan tiltott tényezői ”, Theoretical Computer Science , vol. 792,2019, P. 144–153 ( DOI 10.1016 / j.tcs.2018.05.037 )
Külső hivatkozás
(en) Frank Ruskey, „Információ a nyakláncokról, Lyndon szavakról, 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;">