Mavzu: Kombinatorika elementlari

Mavzu: Kombinatorika elementlari

Reja:

1. 
   Kombinatorikaning asosiy qoida va formulalari.
   
2. 
   O‘rinlashtirishlar, o’rin almashtirishlar, birikmalar.
   

Tayanch tushunchalar: kombinatorika elementlari, kombinatorikaning asosiy qoida va teoremalari, guruhlashlar va o‘rinlashtirishlar, birikmalar, elementlar, takrorlanuvchi o’rinlashtirishlar, takrorlanuvchi guruhlashlar.
Ob’yektlarni tanlash va ularni ma’lum tartibda joylashtirish kabi matematik masalalar har doim insonni qiziqtiriradigan sohalardan hisoblangan.
Kombinatorika – bu matematikaning chekli to‘plam elementlarini berilgan qoidalar asosida tanlash va joylashtirish bilan bog‘liq masalalarni yechish usullarini o‘rganuvchi bo‘limdir.
Kombinatorika tarixiga nazar tashlasak, bir necha ming yil avval Xitoyda sehrli kvadratlar tuzish, qadimgi Yunonistonda figurali sonlar nazariyasini tuzish masalasini o‘rganishgan. Kombinatorika masalalari Samarqanddagi Ulug‘bek maktabining taniqli matematigi G’iyosiddin Jamshid Koshiy, X asrda yashab ijod etgan Umar Xayyom, keyinchalik Evropa olimlari jumladan, B.Paskal, J.Kordano, G.Leybnits, Ya.Bernulli, P.Ferma, L.Eyler va boshqa olimlarning ishlarida uchraydi.

Kombinatorikaning asosiy qoida va formulalari.

A ^debchekli A ^{to‘plam elementlari sonini belgilaymiz.}
Kombinatorikada sodda, o‘z-o‘zidan ravshan bo‘lgan, ammo muhim qoidalar bor. Bunday qoidalar sifatida jamlash, ko‘paytirish hamda kiritish va chiqarish qoidalari deb ataluvchi qoidalarni ko‘rsatish mumkin.
^{Qo‘shish (jamlash) qoidasi: Agar} A ^{to‘plam n ta elementdan,} B ^{to‘plam esa m ta elementdan iborat bo‘lib, bu ikki to‘plam o‘zaro kesishmasa, u holda} A ^va B ^{ning barcha elementlaridan iborat} A B ^{to‘plam n +m ta elementga ega, ya’ni}
| A B || A |  | B |
^{Qo’shish qoidasi bilan} A ^va B ^{to‘plamlar o‘zaro kesishganda ham} A B to‘plam elementlari nechtaligini hisoblash mumkin. Bunda quyidagi kiritish- chiqarish qoidasio‘rinli:

B || A |  | B |  | A B |
| A

Ravshanki, bu tenglikdan foydalanib | A | , | B | , | A va | A
miqdorlarning ixtiyoriy uchtasi ma’lum bo‘lganda to‘rtinchisini hisoblash mumkin.
Misol. 50 ta talabadan 40 tasiingliz tilini, 25 tasi esa nemis tilini o‘rganmoqdalar. Ikkala tilni ham o‘rganayotgan talaba nechta?
^{Yechilishi. Ingliz tilini o‘rganayotgan talabalar to‘plamini} A ^{orqali, nemis tilini o‘rganayotgan talabalar to‘plamini} B ^{orqali belgilaymiz.}
Ma’lumki, | A B |= 50, | A |= 40, | B |=25. U holda ikkala tilni ham ^{o‘rganayotgan talabalar} A B ^{to‘plamni tashkil qilib, kiritish-chiqarish} formulasidan | A B |=| A |+| B | -| A B |=15.

uchun