Guruh talabasi Nomonov Abbosbek Mavzu : O’rin almashtirishning hosil qiluvchi funksiyasi, guruhlashni hosil qiluvchi funksiyasi

1-misol. x dan ikkita , y va z dan bitta elementlardan tashkil topgan kortesh uchun barcha takrorli o’rin almashtirishni tuzing .

Bu misolni yechish uchun yuqoridagi 1- teoremadagi formuladan foydalanamiz.

B0unda n barcha elemenlar soni n=4 , x elementdan ikkita bo’lgani uchun n1=2,
y va z uchun n2 = n3 = 1 bo’ladi. Fo’rmulaga qo’ysak :

bo’ladi. Bu o’rin almashtirishda quidagilarni hammasi keltirilgan :
xxyz , xxzy , xyxz , xyzx
xzxy , xzyx , yxxz , yxzx
yzxx , zxxy , zxyx , zyxx

2-misol. Uchta elementdan iborat A={a, b, c} to‘plamning elementlaridan
tuzilgan o‘rin almashtirishlar soni 6 ga teng:
(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a).

Teorema. n elementga ega bo`lgan S to`plamning barcha o`rin almashtirishlari soni ga teng.

3-misol. Javonga 6 ta kitobni necha usulda joylashtirish mumkin .
P7 =6 ! =720
4-misol. 8 ta ladyani shaxmat doskasida bir-birini urmaydigan qilib necha usul bilan joylashtirish mumkin?
Yechish. Ladyalar soni 8 ta.

5-misol. 30 ta detalni 5 ta har xil qutiga 6 tadan necha xil usul bilan joylashtirish mumkin ?
Yechish:
Masalaning shartiga ko’ra k=30, k₁ =k₂ =…=k₅ =6, m=5. 1 formula bo’yicha usullar soni: P6,6,6,6,6=30/ 6*6*6*6*6.
6-misol . 6 raqamli barcha telefon nomerlari sonini toping.

Yechish. Telefon nomerlari 0 dan 9 gacha bo’lgan 10 ta raqamdan tuzilgani uchun 10 elementdan tuzilgan barcha tartiblangan 6 o’rinli kortejlar sonini topamiz:

Javob:  = 10⁶ = 1000000. 6 raqamli telefon nomerlari soni 10⁶ ga teng.

7-misol. n ta elementdan berilgan ikkita elementi yonma - yon turmaydigan nechta o‘rin almashtirish bajarish mumkin.

Yechilishi:
a va b elementlar berilgan bo‘lsin. Bu elementlar yonma-yon turgan o‘rinalmashtirishlar sonini aniqlaymiz.Birinchi hol a element b elementdan oldin kelishi mumkin, bunda a birinchi o‘rinda, ikkinchi o‘rinda, va hokazo (n-1)- o‘rinda turishi mumkin. Ikkinchi hol b element a elementdan oldin kelishi mumkin, bunday holatlar ham (n-1) ta bo‘ladi. Shunday qilib, a va b elementlar yonma-yon keladigan holatlar soni ta bo‘ladi. Bu usullarning har biriga qolgan (n-2) ta elementning (n-2)! ta o‘rin almashtirishi mos keladi. Demak, a va b elementlar yonma - yon keladigan barcha o‘rin almashtirishlar soni ta bo‘ladi. Shuning uchun ham yonma-yon turmaydigan o‘rin almashtirishlar soni ga teng bo`ladi.

Takrorli o‘rinlashtirishlar. n ta elementlardan tashkil topgan to’plam berilgan bo’lsin. Bu elementlardan foydalanib, m ta elementdan tashkil topgan kortejlarni shunday tuzamizki, bu kortejlarga har bir element hohlagancha marta (albatta m dan oshmagan miqdorda) kirishi mumkin bo’lsin va bu kortejlar bir-biridan ularni tashkil etuvchi elementlar turlari bilan yoki bu elementlarning joylashishlari bilan farq qilishsin. Shunday usul bilan tuzilgan kortejlarning har biri n ta turli elementlardan takrorlanuvchi elementlar qatnashgan m tadan o‘rinlashtirish (qisqacha, takrorli o‘rinlashtirish) deb ataladi.

n ta turli elementlardan m tadan takrorli o’rinlashtirishlar sonini bilan belgilaymiz.
2- teorema. n ta turli elementlardan m tadan takrorli o‘rinlashtirishlar soni ga teng, ya’ni .
Isboti . Berilgan n uchun takrorli o’rinlashtirishdagi elementlar soni m
bo’yicha matematik induksiya usulini qo’llaymiz. Baza: takrorli o’rinlashtirishlar m=1 bo’lganda bitta elementdan tuzilishi ravshan. Tabiiyki, bunda hech qanaqa takrorlanish haqida gap bo’lishi mumkin emas. Bu holda elementlar soni n bo’lgani uchun takrorli o’rinlashtirishlar soni ham n ga teng: .
Induksion o’tish: teoremaning tasdig’i m=k bo’lganda to’g’ri, ya’ni bo’lsin. Bu tasdiq m=k+1 bo’lganda ham to’g’ri bo’lishini isbotlaymiz. Buning uchun n ta turli elementlardan k tadan takrorli o’rinlashtirishning istalgan birini olib, unga n elementli to’plamning ixtiyoriy bitta elementini (k+1)- element sifatida kiritamiz. Natijada qandaydir (k+1) tadan takrorli o’rinlashtirishni paydo qilamiz. Tabiyki, qaralayotgan k tadan o’rinlashtirishlarning har biridan yangi n ta (k+1) tadan takrorli o’rinlashtirishlar hosil qilish mumkin. Shunday usul bilan ishni davom ettirsak, barcha mumkin bo’lgan (k+1) tadan takrorli o’rinlashtirishlarni hosil qilamiz, bu yerda birorta ham (k+1) tadan takrorli o’rinlashtirishlar qolib ketmaydi va hech qaysi ilgari ko’rilgan (k+1) tadan takrorli o’rinlashtirish qaytadan paydo bo’lmaydi. Ko’paytirish qoidasiga asosan n ta turli elementlardan (k+1) tadan takrorli o’rinlashtirishlar soni k tadan takrorli o’rinlashtirishlar soniga nisbatan n marta ortiqdir, ya’ni .