Mavzu : O’rin almashtirishning hosil qiluvchi funksiyasi, guruhlashni hosil qiluvchi funksiyasi

Takrorli gruppalashlar. Har bir elementi birlashmaga istalgancha marta kiritiladigan va turli n ta elementlardan m tadan olinadigan hamda elementlar tartibi e’tiborga olinmaydigan birlashmalarni (kortejlarni) qaraymiz. Bunaqa birlashmalar n ta turli elementlardan m tadan takrorlanuvchi elementlar qatnashgan gruppalashlar (qisqacha, takrorli gruppalashlar) deb ataladi. n ta elementlardan m tadan takrorlanuvchi elementlar qatnashgan gruppalashlar ta’rifidan ko’rinib turibdiki, turli kombinatsiyalar bir-birlaridan hech bo’lmasa bitta elementi bilan farq qiladi. n ta elementdan m tadan takrorli gruppalashlar sonini deb belgilaymiz. 3- teorema. n ta elementdan m tadan takrorli gruppalashlar soni ga teng, ya’ni . 1-misol . 30 nafar oʻquvchisi bor sinfda olimpiadada qatnashish uchun 2 nafar oʻquvchini tanlab olishimiz kerak. Buni nechta usulda amalga oshirish mumkin? Yechilishi. Birinchi oʻquvchini 30 ta usulda, ikkinchi oʻquvchini esa qolgan 29 nafar oʻquvchidan 29 ta usulda tanlasak boʻladi. Bunda har bir juftlik ikki marta sanalgani bois jami 30×29/2=435 ta usulni hosil qilamiz. 2-misol. Har birining yoqlariga 1, 2, 3, 4, 5 va 6 sonlari yozilgan kub shaklidagi ikkita soqqalarni tashlaganda jami nechta sonlar juftligini hosil qilish mumkin?

Soqqalarni tashlaganda jami quyidagi 21 imkoniyatlardan biri ro’y beradi: (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (2,2) (2,3) (2,4) (2,5) (2,6) (3,3) (3,4) (3,5) (3,6) (4,4) (4,5) (4,6) (5,5) (5,6) (6,6) Bu juftliklar oltita elementdan ikkitadan takrorli gruppalashlarni tashkil etadi. Ularning soni 3- teoremaga asosan bo’ladi. Takrorlanmaydigan guruhlashlar. Bizga tartiblanmagan takrorlanmaydigan n ta elementi bo`lgan S to‘plam berilgan bo`lsin. bilan ni taqqoslaymiz. Bilamizki, k ta elementni k! ta usulda tartiblash mumkin, ya` ni bo`ladi. Bundan kelib chiqadi.

1-misol. Bir vazifaga ko'rsatilgan 10 nomzoddan uch kishi saylanishi kerak. Saylovdagi turli ehtimollar qancha bo'lishi mumkin? Yechish: Saylovdagi ehtimollar soni 10 elementni 3 tadan joylashtirib tuzish mumkin bo'lgan barcha gruppalashlar soniga teng bo'ladi, ya’ni Teorema 1. n ta elementi bo`lgan S to‘plamning barcha tartiblanmagan k elementli qism to‘plamlari soni ga teng. Ushbu teoremani umumlashtiramiz: n ta elementi bo`lgan S to‘plamni k ta qism to‘plamlar yig‘indisi ko‘rinishida necha xil usulda yoyish mumkin degan savolni qo‘yamiz. Buning uchun S to`plamni o`zaro kesishmaydigan k ta qism to‘plamlarga ajratish mumkin bo`lsin. Bunda ularning elementlari soni mos ravishda N(A1) = k1 , N(A2) = k2,….,N(Am)=km bo‘lib, k1 , k2,….,km berilgan sonlar uchun k1 + k2+….+km = n shartlar bajariladi. A1 , A2,….,Am to‘plamlar umumiy elementga ega emas.