n ta sondan iborat barcha o‘rin almashtirishlar to‘plami Sn kabi belgilanadi.
tasdiq. n ta sondan iborat barcha o‘rin almashtirishlar soni n! ga teng, ya’ni |Sn| = n!.
Isbot. Ushbu tasdiqni isbotlashda matematik induksiya usulidan foydalanamiz. Ravshanki, n = 1 da o‘rin almashtirish soni bitta bo‘ladi, ya’ni 1! = 1. Shuningdek, n = 2 bo‘lgan holda o‘rin almashtirishlar soni ikkita bo‘ladi, ya’ni (1,2) va (2,1).
Tasdiqni n -1 ta sonli o‘rin almashtirishlar uchun o‘rinli deb faraz qilib, n ta sonli o‘rin almashtirish uchun ko‘rsatamiz.
n -1 ta sondan iborat barcha o‘rin almashtirishlarning har biriga unga kirmagan n sonini joylashtirib chiqish natijasida barcha n ta sondan tuzilgan o‘rin almashtirish hosil qilamiz. Xar bir o‘rin almashtirishda n soni n hil usulda joylashadi.
n -1 ta sondan iborat barcha o‘rin almashtirishlar (n -1)! ta ekanligidan, n ta sondan tuzilgan o‘rin almashtirishlar soni (n -1)! - n = n! ekanligi kelib chiqadi. □
ta’rif. O‘rin almashtirishning ixtiyoriy ikkita elementini o‘rnini almashtirishga transpozitsiya deyiladi.
Misol 7.1. (1,2,3,4) o‘rin almashtirishni 2 va 4-o‘rinlarini almashtirishdan quyidagi (1,4,3,2) o‘rin almashtirish hosil bo‘ladi.
teorema. n ta elementdan iborat barcha n! ta o‘rin almashtirishlarni shunday tartibda joylashtirish mumkinki, bunda xar bir keyingi o‘rin almashtirish oldingisidan birgina transpozitsiya yordamida hosil qilinadi. Shuningdek, transpozitsiyalashni ixtiyoriy o‘rin almashtirishdan boshlash mumkin.
Isbot. Teoremani isbotlashda induksiya metodidan foyda- lanamiz. Ravshanki, n = 2 bo‘lganda teorema o‘rinli. Teoremani n -j uchun o‘rinli deb faraz qilib, n uchun isbotlaymiz. Bizga
(ij, i'2,..., in ) (7.1)
o‘rin almashtirish berilgan bo‘lsin. Birinchi o‘rinda i turgan n ta elementdan iborat barcha o‘rin almashtirishlarni qarab chiqamiz. Bunday o‘rin almashtirishlar (n - j)! ta va ularni teoremaning talablariga moslab tartiblash mumkin.
Bu tartiblashni induktiv farazga muvofiq ixtiyoriy o‘rin almashtirishdan, xususan, (z2,...,in) o‘rin almashtirishdan boshlash mumkin, n ta simvoldan ana shunday yo‘l bilan hosil qilingan o‘rin almashtirishlarning oxirgisida i simvolni ixtiyoriy boshqa bir simvol bilan, masalan, i bilan transpozitsiyalaymiz va yangi hosil qilingan o‘rin almashtirishdan boshlab, birinchi o‘rinda i2 turgan barcha o‘rin almashtirishlarni keraklicha tartiblashtiramiz va hokazo. Bunday yo‘l bilan, n ta simvoldan iborat barcha o‘rin almashtirishlarni saralab chiqish mumkin.
Misol 7.2. S3 to‘plamning elementlarini quyidagi tartibda joylashtirib chiqamiz:
3; 13 2; 3 12; 3 2 1; 2 3 1; 2 13;
Bundan tashqari biz o‘rin almashtirishda bir nechta transpozitsiyalar bajarib, boshqa o‘rin almashtirishga o‘tishimiz mumkin. O‘rin almashtirishda ikki elementni transpozitsiyalash quyidagicha ko‘rinishda ham tasvirlashimiz mumkin:
j)
..., i,..., j,—^..., j,..., i,...
33
ta’rif. Agar berilgan o‘rin almashtirishda i > j bo‘lib, o‘rin almashtirishda i soni j dan oldin turgan bo‘lsa, i va j sonlar inversiya tashkil etadi deyiladi va inv(i, j) shaklda belgilanadi.
O‘rin almashtirishdagi inversiya tashkil etuvchi juftliklar soniga o‘rin almashtirishning inversiyasi deyiladi va inv(ix,i2,...,in) kabi belgilanadi. Inversiyasi toq va juft son bo‘lgan o‘rin almashtirishlar mos ravishda toq va juft o‘rin almashtirishlar deb ataladi. Berilgan (ix,i2,...,in) o‘rin almashtirishning signaturasi deb,
Do'stlaringiz bilan baham: |