Tsiklik permutatsiya - Cyclic permutation

Yilda matematika va xususan guruh nazariyasi, a tsiklik almashtirish (yoki tsikl) a almashtirish ba'zi elementlarning o'rnatilgan X ba'zilarining elementlarini xaritada aks ettiradi kichik to'plam S ning X ning boshqa barcha elementlarini mahkamlashda (ya'ni o'zlarini xaritalashda) bir-biriga tsiklik usulda X. Agar S bor k elementlar, tsikl a deb nomlanadi k- velosiped. Tsikllar ko'pincha qavs ichida joylashgan elementlari ro'yxati bilan belgilanadi, ularning joylashish tartibi bo'yicha.

Masalan, berilgan X = {1, 2, 3, 4}, 1 dan 3 gacha, 3 dan 2 gacha, 2 dan 4 gacha va 4 dan 1 gacha yuboradigan almashtirish (1, 3, 2, 4) (shuning uchun S = X) - bu 4 tsikldir va 1 dan 3 gacha, 3 dan 2 gacha, 2 dan 1 gacha va 4 dan 4 gacha yuboradigan (1, 3, 2) almashtirish (shunday qilib) S = {1, 2, 3} va 4 sobit element) bu 3 tsikl. Boshqa tomondan, 1 dan 3 gacha, 3 dan 1 gacha, 2 dan 4 gacha va 4 dan 2 gacha bo'lgan almashinish tsiklik almashtirish emas, chunki u {1, 3} va {2, 4} juftliklarini alohida ravishda almashtiradi.

To'plam S deyiladi orbitada tsikl. Cheklangan ko'plab elementlarning har bir almashinuvi ajratilgan orbitalardagi tsikllarga ajralishi mumkin.

O'rnini almashtirishning tsiklik qismlari tsikllar, shuning uchun ikkinchi misol 3 tsikl va 1 tsikldan iborat (yoki sobit nuqta) va uchinchisi ikkita 2 tsikldan iborat va (1, 3) (2, 4) bilan belgilanadi.

Ta'rif

Ikkita sobit nuqtaga ega tsiklik permutatsiya diagrammasi; 6 tsikl va ikkita 1 tsikl.

A almashtirish tsiklik permutatsiya deyiladi agar va faqat agar u bitta nodavlat tsiklga ega (uzunlik tsikli> 1).^[1]

Masalan, ichida yozilgan almashtirish ikki qatorli (ikki yo'l bilan) va shuningdek tsikl yozuvlari,

{ displaystyle { begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 4 & 2 & 7 & 6 & 5 & 8 & 1 & 3 end {pmatrix}} = { begin {pmatrix} 1 & 4 & 6 & 8 & 3 & 7 & 2 & 5 4 & 6 & 8 & 3 & 7 & 1 & 2 & 5 3 p = (pmatrix) (2) (5),}

olti tsikl; uning tsikli diagrammasi o'ng tomonda ko'rsatilgan.

Ba'zi mualliflar ta'rifni faqat bitta noan'anaviy tsikldan iborat bo'lgan almashtirishlar bilan cheklashadi (ya'ni qat'iy nuqtalarga yo'l qo'yilmaydi).^[2]

Arzimas tsikllarsiz tsiklik permutatsiya; 8 tsikl.

Masalan, almashtirish

{ displaystyle { begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 4 & 5 & 7 & 6 & 8 & 2 & 1 & 3 end {pmatrix}} = { begin {pmatrix} 1 & 4 & 6 & 2 & 5 & 8 & 3 & 7 4 & 6 & 2 & 5 & 8 & 3 & 7 & 1 6 5 2 p n ({pmatrix) 3 7)}

oldingi cheklangan ta'rifi ostida, bu cheklangan ta'rif ostida tsiklik permutatsiya.

Rasmiy ravishda, almashtirish ${ displaystyle sigma}$ to'plamning Xdeb qaraldi biektiv funktsiya ${ displaystyle sigma: X dan X} gacha$ , agar harakat bo'lsa, tsikl deb ataladi X tomonidan yaratilgan kichik guruhning ${ displaystyle sigma}$ eng ko'p bitta elementga ega bo'lgan orbitaga ega.^[3] Ushbu tushuncha ko'pincha qachon ishlatiladi X cheklangan to'plam; u holda, albatta, eng katta orbitadir, S, shuningdek, cheklangan. Ruxsat bering ${ displaystyle s_ {0}}$ ning har qanday elementi bo'lishi Sva qo'ying ${ displaystyle s_ {i} = sigma ^ {i} (s_ {0})}$ har qanday kishi uchun ${ displaystyle i in mathbf {Z}}$ . Agar S sonli, minimal son mavjud ${ displaystyle k geq 1}$ buning uchun ${ displaystyle s_ {k} = s_ {0}}$ . Keyin ${ displaystyle S = {s_ {0}, s_ {1}, ldots, s_ {k-1} }}$ va ${ displaystyle sigma}$ tomonidan belgilanadigan almashtirish

{ displaystyle sigma (s_ {i}) = s_ {i + 1}}

0 for uchun men < k

va ${ displaystyle sigma (x) = x}$ ning har qanday elementi uchun ${ displaystyle X setminus S}$ . Elementlar tomonidan o'rnatilmagan ${ displaystyle sigma}$ sifatida tasvirlanishi mumkin

{ displaystyle s_ {0} mapsto s_ {1} mapsto s_ {2} mapsto cdots mapsto s_ {k-1} mapsto s_ {k} = s_ {0}}

.

Kompakt yordamida tsiklni yozish mumkin tsikl belgisi ${ displaystyle sigma = (s_ {0} ~ s_ {1} ~ dots ~ s_ {k-1})}$ (bu yozuvda elementlar orasida vergul mavjud emas, a bilan chalkashmaslik uchun k-panjara ). The uzunlik tsikl - bu eng katta orbitaning elementlari soni. Uzunlik tsikli k deb ham ataladi k- velosiped.

1 tsikl orbitasi a deb ataladi sobit nuqta permutation, lekin permutation sifatida har 1 tsikl shaxsni almashtirish.^[4] Tsikl yozuvidan foydalanilganda, chalkashliklarga olib kelmasa, 1-tsikllar tez-tez bostiriladi.^[5]

Asosiy xususiyatlar

Asosiy natijalardan biri nosimmetrik guruhlar har qanday almashtirishni hosilasi sifatida ifodalash mumkin ajratish tsikllar (aniqrog'i: ajratilgan orbitali tsikllar); bunday tsikllar bir-biri bilan qatnaydi va almashtirishning ifodasi tsikllar tartibiga qadar noyobdir.^[a] The multiset ushbu ifodadagi tsikllarning uzunligi ( tsikl turi ) shuning uchun almashtirish va imzo bilan ham aniq belgilanadi konjuge sinf nosimmetrik guruhdagi almashtirishning o'zi u bilan belgilanadi.^[6]

Soni k- nosimmetrik guruhdagi velosipedlar S_n uchun berilgan ${ displaystyle 1 leq k leq n}$ , quyidagi ekvivalent formulalar bo'yicha

{ displaystyle { binom {n} {k}} (k-1)! = { frac {n (n-1) cdots (n-k + 1)} {k}} = { frac {n !} {(nk)! k}}}

A k- velosipedda bor imzo (−1)^k − 1.

The teskari tsikl ${ displaystyle sigma = (s_ {0} ~ s_ {1} ~ dots ~ s_ {k-1})}$ yozuvlarning tartibini o'zgartirish orqali beriladi: ${ displaystyle sigma ^ {- 1} = (s_ {k-1} ~ dots ~ s_ {1} ~ s_ {0})}$ . Xususan, beri ${ displaystyle (a ~ b) = (b ~ a)}$ , har ikki tsikl o'z teskari. Disjunik tsikllar almashinuvi sababli, disjoint tsikllar mahsulotining teskari tomoni tsikllarning har birini alohida-alohida qaytarish natijasidir.

Transpozitsiyalar

Matritsa ning

{ displaystyle pi}

Faqat ikkita elementdan iborat tsikl a deb nomlanadi transpozitsiya. Masalan, almashtirish ${ displaystyle pi = { begin {pmatrix} 1 & 2 & 3 & 4 & 1 & 4 & 3 & 2 & end {pmatrix}}}$ bu 2 va 4 ni almashtiradi.

Xususiyatlari

Har qanday almashtirishni quyidagicha ifodalash mumkin tarkibi transpozitsiyalar (mahsulot) - rasmiy ravishda, ular generatorlar uchun guruh.^[7] Aslida, to'siq qo'yilganda ${1, 2, ..., n}$ butun son uchun $n$ , keyin har qanday almashtirishni hosilasi sifatida ifodalash mumkin qo'shni transpozitsiyalar ${ displaystyle (1 ~ 2), (2 ~ 3), (3 ~ 4),}$ va hokazo. Buning sababi shundaki, o'zboshimchalik bilan transpozitsiyani qo'shni transpozitsiyalarning hosilasi sifatida ifodalash mumkin. Aniq qilib, transpozitsiyani ifodalash mumkin ${ displaystyle (k ~~ l)}$ qayerda ${ displaystyle k$ harakatlanish orqali $k$ ga $l$ birma-bir qadam, keyin harakatlanmoqda $l$ qayerga $k$ edi, bu ikkalasini almashtiradi va boshqa o'zgarishlarni qilmaydi:

{ displaystyle (k ~~ l) = (k ~~ k + 1) cdot (k + 1 ~~ k + 2) cdots (l-1 ~~ l) cdot (l-2 ~~ l- 1) cdots (k ~~ k + 1).}

Permutatsiyani transpozitsiyalar mahsulotiga parchalanishi, masalan, permutatsiyani ajratilgan tsikllarning mahsuloti sifatida yozish, so'ngra 3 va undan uzun uzunlikdagi tsikllarning har birini takroriy ravishda transpozitsiya va uzunlik tsikli mahsulotiga bo'lish orqali olinadi. Kamroq:

{ displaystyle (a ~ b ~ c ~ d ~ ldots ~ y ~ z) = (a ~ b) cdot (b ~ c ~ d ~ ldots ~ y ~ z).}

Bu shuni anglatadiki, dastlabki so'rov ko'chirishdir ${ displaystyle a}$ ga ${ displaystyle b,}$ ${ displaystyle b}$ ga ${ displaystyle c,}$ ${ displaystyle y}$ ga ${ displaystyle z,}$ va nihoyat ${ displaystyle z}$ ga ${ displaystyle a.}$ Buning o'rniga elementlarni saqlash mumkin ${ displaystyle a}$ bu erda birinchi navbatda to'g'ri omilni bajarish (odatdagidek operator notation-da va maqoladagi konventsiyaga rioya qilish) Permutatsiyalar ). Bu ko'chib o'tdi ${ displaystyle z}$ holatiga ${ displaystyle b,}$ shuning uchun birinchi almashtirishdan keyin elementlar ${ displaystyle a}$ va ${ displaystyle z}$ hali yakuniy pozitsiyalarida emas. Transpozitsiya ${ displaystyle (a ~ b),}$ keyin amalga oshiriladi, keyin manzillar ${ displaystyle z}$ indekslari bo'yicha ${ displaystyle b}$ dastlab nima bo'lganligini almashtirish uchun ${ displaystyle a}$ va ${ displaystyle z.}$

Aslida nosimmetrik guruh a Kokseter guruhi, bu 2-tartib elementlari (qo'shni transpozitsiyalar) tomonidan hosil bo'lishini va barcha munosabatlar ma'lum shaklda bo'lishini anglatadi.

Nosimmetrik guruhlar bo'yicha asosiy natijalardan biri ma'lumki, transpozitsiyalarga berilgan permütatsiyaning barcha parchalanishlari juft sonli transpozitsiyalarga ega yoki ularning hammasi toq sonli transpozitsiyalarga ega.^[8] Bu ruxsat beradi almashtirishning tengligi bo'lish a aniq belgilangan kontseptsiya.

Shuningdek qarang

Velosiped saralash - saralash algoritmi, saralanadigan almashtirishni tsikllarga ajratish mumkin, bu alohida-alohida aylantirilib, tartiblangan natijani beradi.
Velosipedlar va belgilangan punktlar
Butun sonning tsiklik permutatsiyasi
Velosiped belgisi
Oqsillarda dumaloq permutatsiya

Izohlar

^ E'tibor bering, tsikl yozuvlari noyob emas: har biri k- velosipedning o'zi yozilishi mumkin k tanloviga qarab turli xil yo'llar ${ displaystyle s_ {0}}$ uning orbitasida.

Adabiyotlar

^ Bogart, Kennet P. (1990), Kirish kombinatorikasi (2-nashr), Harcourt, Brace, Jovanovich, p. 486, ISBN 0-15-541576-X
^ Gross, Jonathan L. (2008), Kompyuter dasturlari bilan kombinatoriya usullari, Chapman & Hall / CRC, p. 29, ISBN 978-1-58488-743-0
^ Fraleigh 1993 yil, p. 103
^ Rotman 2006 yil, p. 108
^ Sagan 1991 yil, p. 2018-04-02 121 2
^ Rotman 2006 yil, p. 117, 121
^ Rotman 2006 yil, p. 118, Prop.335
^ Rotman 2006 yil, p. 122

Manbalar

Anderson, Marlow va Feyl, Todd (2005), Abstrakt algebra bo'yicha birinchi kurs, Chapman & Hall / CRC; 2-nashr. ISBN 1-58488-515-7.
Fraley, Jon (1993), Abstrakt algebra bo'yicha birinchi kurs (5-nashr), Addison Uesli, ISBN 978-0-201-53467-2
Rotman, Jozef J. (2006), Ilovalar bilan mavhum algebra bo'yicha birinchi kurs (3-nashr), Prentice-Hall, ISBN 978-0-13-186267-8
Sagan, Bryus E. (1991), Simmetrik guruh / vakolatxonalar, kombinatorial algoritmlar va simmetrik funktsiyalar, Wadsworth & Brooks / Cole, ISBN 978-0-534-15540-7

Tashqi havolalar

Ushbu maqola tsikldan boshlab materiallarni o'z ichiga oladi PlanetMath, ostida litsenziyalangan Creative Commons Attribution / Share-Alike litsenziyasi.

[6] E'tibor bering, tsikl yozuvlari noyob emas: har biri k- velosipedning o'zi yozilishi mumkin k tanloviga qarab turli xil yo'llar ${ displaystyle s_ {0}}$ uning orbitasida.

[1] Bogart, Kennet P. (1990), Kirish kombinatorikasi (2-nashr), Harcourt, Brace, Jovanovich, p. 486, ISBN 0-15-541576-X

[2] Gross, Jonathan L. (2008), Kompyuter dasturlari bilan kombinatoriya usullari, Chapman & Hall / CRC, p. 29, ISBN 978-1-58488-743-0

[3] Fraleigh 1993 yil, p. 103

[4] Rotman 2006 yil, p. 108

[5] Sagan 1991 yil, p. 2018-04-02 121 2

[7] Rotman 2006 yil, p. 117, 121

[8] Rotman 2006 yil, p. 118, Prop.335

[9] Rotman 2006 yil, p. 122

[1]

[2]

[3]

[4]

[5]

[a]

[6]

[7]

[8]