O‘zbekiston respublikasi oliy va o‘rta maxsus ta’lim vazirligi mirzo ulug‘bek nomidagi o‘zbekiston milliy universiteti

1.2.1-tasdiq. S_n (n ≥ 3) gruppa nokommutativ (kommutativ emas) va |S_n| = n!.
Isbot. Dastlab, ushbu gruppaning nokommutativ ekanligini ko‘rsatamiz.

Buning uchun quyidagi π₁, π₂ ∈ S_n elementlarni qaraymiz

π₁
U holda

₌ 1 2 3 4 . . . n _{, π}
1 3 2 4 . . . n ²
₌ 1 2 3 4 . . . n _.
3 2 1 4 . . . n

π₁ ◦ π₂
va

2

1

π ◦ π
₌ 1 2 3 4 . . . n

2 3 1 4 . . . n

3 1 2 4 . . . n
₌ 1 2 3 4 . . . n _.

Demak, π₁ ◦ π₂ π₂ ◦ π₁, ya’ni S_n gruppa kommutativ emas.

Endi |S_n| = n! ekanligini ko‘rsatamiz. Bu gruppaning elementlari umumiy

ko‘rinishi

_{π =} 1 2 . . . n
π(1) π(2) . . . π(n)

bo‘lib, π(1) ∈ {1, 2, . . . , n}, ya’ni π(1) ning qiymati n ta sondan biriga teng bo‘lishi mumkin. π(2) ∈ {1, 2, . . . , n} \ {π(1)} bo‘lganligi uchun π(2) ning qiymati n − 1 ta sondan biriga va hokazo π(n) ∈ {1, 2, . . . , n} \ {π(1), π(2), . . . , π(n − 1)} ekan- ligidan π(n) ning qiymati faqat bitta songa teng bo‘lishi mumkinligi kelib chiqadi. Natijada, π o‘rin almashtirishni hosil qilish mumkin bo‘lgan barcha imkoniyatlari 1 · 2 · 3 · · · · · n = n! soniga teng, ya’ni |S_n| = n!.

Endi sikl va transpozitsiya deb nomlanuvchi o‘rin almashtirishlarni keltiramiz.

1.2.1-ta’rif. π ∈ S_n o‘rin almashtirish


_{π =} i₁ i₂ . . . i_k−1 i_k i₂ i₃ . . . i_k i₁


ko‘rinishda aniqlangan bo‘lsa, ya’ni π(i₁) = i₂, π(i₂) = i₃, . . . , π(i_k−1) = i_k, π(i_k) = i₁ bo‘lib, a ∈ I_n \ {i₁, i₂, . . . , i_k} elementlar uchun π(a) = a bo‘lsa, u holda bu o‘rin almashtirishga uzunligi k ga teng bo‘lgan sikl yoki k-sikl deb ataladi va (i₁, i₂, . . . , i_k) ko‘rinishida yoziladi. Uzunligi 2 ga teng bo‘lgan sikl esa transpozitsiya deyiladi.
Uzunligi k ga teng bo‘lgan π = (i₁, i₂, . . . , i_k−1, i_k) siklni k xil usulda yozish mumkin, ya’ni quyidagi tengliklar o‘rinli
π = (i₁, i₂, . . . , i_k−1, i_k) = (i₂, i₃, . . . , i_k, i₁) = · · · = (i_k, i₁, . . . , i_k−2, i_k−1).

Sikl ko‘rinishidagi o‘rin almashtirishlarni sonlarning orasiga vergul qo‘ymasdan (i₁i₂ . . . i_k) kabi yozish ham qabul qilingan. Masalan, (S₃, ◦) gruppaning barcha elementlari

1 2 3

2 1 3

3 2 1

1 3 2

2 3 1

3 1 2
1 2 3 _, 1 2 3 _, 1 2 3 _, 1 2 3 _, 1 2 3 _, 1 2 3

bo‘lib, ular sikl ko‘rinishida mos ravishda quyidagicha yoziladi:


e, (12), (13), (23), (123), (132).


1.2.2-ta’rif. Bizga π₁, π₂ ∈ S_n o‘rin almashtirishlar berilgan bo‘lsin. Agar π₁(k) /= k shartni qanoatlantiruvchi barcha k lar uchun π₂(k) = k bo‘lib, va aksin- cha π₂(i) /= i lar uchun π₁(i) = i bo‘lsa, u holda π₁ va π₂ o‘rin almashtirishlar kesishmaydigan o‘rin almashtirishlar deyiladi.
π = va π =
Masalan,

1	2	3	4 5
1	2	3	5 4

1 2 3 4 5

¹ 2 3 1 4 5 ²

o‘rin almashtirishlar kesishmaydigan o‘rin almashtirishlar bo‘lib, ularning sikl ko‘rinishidagi ifodalari esa π₁ = (123) va π₂ = (45) bo‘ladi.

Bunda, π = ^{1 2 3 4 5} o‘rin almashtirish uchun π = π

2 3 1 5 4 ¹

• 
  
  π₂
  

= π₂

• 
  
  π₁
  

tenglik o‘rinli bo‘ladi. Bu esa, π o‘rin almashtirishni kesishmaydigan π₁ va π₂ sikl-

larning ko‘paytmasi shaklida ifodalanishini bildiradi. Bundan tashqari, o‘zaro ke- sishmaydigan o‘rin almashtirishlar uchun kommutativlik xossasi o‘rinli bo‘lib, bir nechta o‘zaro kesishmaydigan o‘rin almashtirishlarni ko‘paytirganda ham ularning joylashish tartibi ahamiyatga ega emas.
Quyidagi teoremada birlik elementdan farqli bo‘lgan ixtiyoriy o‘rin al- mashtirishni kesishmaydigan sikllar ko‘paytmasi ko‘rinishida yozish mumkinligi ko‘rsatiladi.

1.2.1-teorema. Ixtiyoriy π ∈ S_n (n ≥ 2) o‘rin almashtirish o‘zaro kesishmaydi- gan sikllar ko‘paytmasi ko‘rinishida (sikllarning joylashish tartibini hisobga olma- gan holda) yagona tarzda ifodalanadi.


Isbot. Teoremani isbotlash uchun induksiya usulidan foydalanamiz. Agar n = 2 bo‘lsa, u holda S₂ = {e, (12)} bo‘lib, teorema o‘rinli bo‘lishi kelib chiqadi. Teoremani barcha S_k, 2 ≤ k < n gruppalar uchun o‘rinli bo‘lsin deb faraz qilib, uni S_n uchun isbotlaymiz. Ixtiyoriy π ∈ S_n, π =/ e element uchun

p

l m
{π(1), π²(1), π³(1), . . . , π^s(1), . . . } ⊆ I_n to‘plamni qaraymiz. I_n to‘plam chekli bo‘lganligi uchun, π (1) = π (1) tenglikni qanoatlantiradigan l va m natural son- lari mavjud. U holda p = |l − m| uchun π^p(1) = 1. Demak, π^p(1) = 1 tenglikni qanoatlantiruvchi p natural soni mavjud. Bunday sonlarning eng kichigini i deb belgilaymiz, ya’ni i = min{p ∈ N | π^p(1) = 1}. U holda quyidagi
A = {1, π(1), π²(1), . . . , πⁱ⁻¹(1)}.
to‘plamning barcha elementlari turli bo‘lib, quyidagi τ ∈ S_n o‘rin almashtirishni aniqlash mumkin
τ = (1, π(1), π²(1), . . . , πⁱ⁻¹(1)).
Ya’ni biz uzunligi i ga teng bo‘lgan siklni aniqladik.
Endi B = I_n \ A to‘plamni qaraymiz. Agar B = ∅ bo‘lsa, u holda i = n bo‘lib, π = τ, ya’ni π o‘rin almashtirish sikldan iborat bo‘ladi. Agar B /= ∅ bo‘lsa, u holda σ = π|_B o‘rin almashtirishni, ya’ni σ sifatida π o‘rin almashtirishni B to‘plamda aniqlangan qismini qaraymiz.
Agar σ = π|_B o‘rin almashtirish S(B) da birlik element bo‘lsa, u holda π = τ,
ya’ni
π = (1, π(1), π²(1), . . . πⁱ⁻¹(1))

bo‘lib, π o‘rin almashtirish uzunligi i ga teng bo‘lgan sikldan iborat bo‘ladi. Agar σ o‘rin almashtirish S(B) da birlik element bo‘lmasa, |B| < n ekanligidan in- duksiya faraziga ko‘ra, σ o‘rin almashtirishni B to‘plamda o‘zaro kesishmaydigan sikllarning ko‘paytmasi ko‘rinishida yozish mumkin, ya’ni σ = σ₁ ◦ σ₂ ◦ · · · ◦ σ_r.

Endi, 1 ≤ i ≤ r soni uchun, π_i o‘rin almashtirishni quyidagicha aniqlaymiz:

i
_{π (a) =} σ_i(a), agar a ∈ B,
a, agar a ∈/ B.
U holda, π₁, π₂, . . . , π_r va τ o‘rin almashtirishlar S_n to‘plamda o‘zaro kesishmay- digan sikllar bo‘lib, π = π₁ ◦ π₂ ◦ · · · ◦ π_r ◦ τ tenglik o‘rinli bo‘ladi, ya’ni π o‘rin almashtirish o‘zaro kesishmaydigan sikllar ko‘paytmasi ko‘rinishida ifodalanadi.

Demak, ixtiyoriy o‘rin almashtirishni o‘zaro kesishmaydigan sikllar ko‘paytmasi ko‘rinishida ifodalash mumkinligi ko‘rsatildi. Endi, bunday ifoda sikllarning joylashish tartibini hisobga olmagan holda yagona ekanlig- ini ko‘rsatamiz. Teskarisini faraz qilaylik, ya‘ni π o‘rin almashtirish r va s ta o‘zaro kesishmaydigan sikllarning ko‘paytmasi ko‘rinishida ifodalansin. U holda

π = π₁ ◦ π₂ ◦ · · · ◦ π_r = µ₁ ◦ µ₂ ◦ · · · ◦ µ_s.
Ixtiyoriy π_i, 1 ≤ i ≤ r siklni qaraylik. Agar π_i = (i₁ i₂ . . . i_l) bo‘lsa, u holda
π(i₁) i₁ bo‘lganligi uchun, i₁ soni qaysidir µ_j siklda ham qatnashadi. Sikllar
o‘zaro kesishmasligini hisobga olsak, bunday µ_j siklning yagona ekanligiga ega bo‘lamiz. Ushbu µ_j siklni esa µ_j = (i₁ c₂ . . . c_m) ko‘rinishida yozib olish mumkin. U holda
i₂ = π_i(i₁) = π(i₁) = µ_j(i₁) = c₂,
i₃ = π_i(i₂) = π(i₂) = π(c₂) = µ_j(c₂) = c₃,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i_l = π_i(i_l−1) = π(i_l−1) = π(c_l−1) = µ_j(c_l−1) = c_l
tengliklardan l = m, hamda π_i = µ_j ekanligini hosil qilamiz. Demak, ixtiyoriy π_i
sikl uchun shunday µ_j sikl topilib, π_i = µ_j tenglik bajarilar ekan.

Ushbu mulohazani ixtiyoriy µ_k sikl uchun yuritib, unga mos µ_k = π_t shartni qanoatlantiruvchi π_t siklning mavjudligini keltirib chiqazish mumkin. Demak, ixtiyoriy π_i sikl uchun π_i = µ_j shartni qanoatlantiruvchi yagona µ_j sikl topiladi.

Yuqoridagi teoremadan quyidagi natijaga ega bo‘lamiz.