Mavzu: Kombinatorikaning asosiy formulalari

2-Misol. Bizga uch elementli

to’plam berilgan bo’lsin.Bu to’plamning barcha ikki elementli qismlari sonini aniqlang.
Yechilishi. Masalani qo’shish qoidasi bilan yechish uchun belgilashlar kiritaylik:
berilgan to’plamning barcha ikki elementli qismlari to’plami ;
– ni o’zida saqlovchi barcha ikki elementli qismlar to’plami ;
– ni o’zida saqlamaydigan barcha ikki elementli qismlar to’plami.
U holda

bo’lib, bo’ladi. Aniqlasak,


bo’lib, natijada

tenglik kelib chiqadi.
3-misol. Bizga elementli

to’plam berilgan bo’lsin. Bu to’plamning elementli barcha qismlari to’plamini o’rganaylik. Odatda bu to’plamning elementlari sonini bilan belgilanadi.
U holda

tenglikning to’g’riligini isbotlang.
Isboti. Bizga berilgan to’plamdan elementni tanlab olib, to’plamni ikki qismga ajratamiz: ni o’zida saqlovchi va ni o’zida saqlamaydigan qismlarga.Masalani qo’shish qoidasi bilan yechish uchun belgilashlar kiritaylik:
- berilgan to’plamning barcha k elementli qismlari to’plami ;
– ni o’zida saqlovchi barcha k elementli qismlar to’plami ;
– ni o’zida saqlamaydigan barcha k elementli qismlar to’plami.
U holda

bo’lib, bo’ladi. Aniqlasak,


bo’lib, natijada

tenglik kelib chiqadi. Demak,

formula to’g’riligiga yetib keldik. Tenglik isbotlandi.

Kombinatorikaning asosiy formulalari, o’rinlashtirishlar,gruppalash
Bir qator amaliy masalalarni yechish uchun berilgan to’plamdan uning qandaydir xossaga ega bo’lgan elementlarini tanlab olish va ularni ma’lum bir tartibda joylashtirishga to’g’ri keladi.
Ta’rif. Biror chekli to’plam elementlari ichida ma’lum bir xossaga ega bo’lgan elementlaridan iborat qism to’plamlarni tanlab olish yoki to’plam elementlarini ma’lum bir tartibda joylashtirish bilan bog’liq masalalar kombinatorik masalalar deyiladi.
Masalan, o’nta ishchidan to’rt kishidan iborat brigadalarni necha xil usulda tuzish mumkinligini (ishlab chiqarishni tashkil etish), molekulada atomlar qanday usullarda birlashishi mumkinligi (kimyo), oqsil moddalarda aminokislotalarni qanday tartiblarda joylashtirish mumkinligi (biologiya), turli bloklardan iborat mexanizmda bu bloklarni turli tartiblarda birlashtirish (konstruktorlik), bir necha dala uchastkalarida turli xil ekinlarni almashtirib ekish (agronomiya), davlat budjetini ishlab chiqarish tarmoqlari bo’yicha taqsimoti (iqtisodiyot) kabilar kombinatorik masalalarga keladi va kombinatorikani inson faoliyatining turli yo’nalishlarida qo’llanishini ko’rsatadi.
Ta’rif. Kombinatorik masalalar bilan shug’ullanadigan matematik fan kombinatorika deyiladi.
Kombinatorikani mustaqil fan sifatida birinchi bo’lib olmon matematigi G.Leybnits o’rgangan va 1666 yilda “Kombinatorika san’ati haqida” asarini chop etgan.
Kombinatorikada qo’shish va ko’paytirish qoidasi deb ataluvchi ikkita asosiy qoida mavjud.
Qo’shish qoidasi.
Agar biror  tanlovni  usulda,  tanlovni  usulda amalga oshirish mumkin bo’lsa va bu yerda  tanlovni ixtiyoriy tanlash usuli   tanlovni ixtiyoriy tanlash usulidan farq qilsa, u holda “ yoki” tanlovni amalga oshirish usullari soni  formuladan topiladi.
Ko’paytirish qoidasi.
Agar biror  tanlovni  usulda,  tanlovni  usulda amalga oshirish mumkin bo’lsa, u holda “ va  ” tanlovni (yoki ( , ) juftlikni) amalga oshirish usullari soni  formuladan topiladi.
Kombinatorik masalalarni yechishda ko’p qo’llaniladigan tushunchalardan biri o’rin almashtirish tushunchasidir.
Ta’rif. Chekli va   ta elementdan iborat to’plamning barcha elementlarini faqat joylashish tartibini o’zgartirib qism to’plam hosil qilish   elementli o’rin almashtirish deb ataladi.
Berilgan  ta elementdan tashkil topadigan o’rin almashtirishlar soni  bilan belgilanadi.
Teorema.  ta elementdan iborat o’rin almashtirishlar soni  formula bilan hisoblanadi.
Bu yerda  – en faktorial deb o’qiladi va  kabi aniqlanadi. Bunda  deb olinadi. Masalan,  va hokazo. Faktoriallarni hisoblashda  tenglikdan foydalanish qulay bo’ladi. Masalan,  elementli  to’plamdan hosil bo’ladigan o’rin almashtirishlar  bo’lib, ularning soni  bo’ladi.
Kombinatorik tushunchalardan yana biri kombinatsiya tushunchasidir.
Ta’rif. Chekli va  ta elementli to’plamning  ta elementli va kamida bitta element bilan farqlanadigan qism to’plam hosil qilish   elementdan  ta olingan kombinatsiya deyiladi.
Masalan,  ko’rinishdagi  elementli to’plamdan ikkita elemenli kombinatsiyalar  bo’lib, ularning soni 3 tadir. Bu yerda  deb olinadi.
ta elementdan  tadan olingan kombinatsiyalar soni  kabi belgilanadi va uning qiymati   formula yordamida hisoblanadi.
Bu formula orqali kiritilgan  sonlar yordamida quyidagi tenglikni yozish mumkin:

Bu tenglikda  ixtiyoriy natural son bo’lib, u  va  qisqa ko’paytirish formulalarining umumlashmasini ifodalaydi va uni Nyuton binomi deb ataladi. Unga kiruvchi  sonlari binomial koeffitsentlar deb ataladi.
Agar Nyuton binomida  yoki  deb olsak, unda 
tengliklar o’rinli bo’ladi.
Agar formulada  o’rniga  qo’yilsa yoki  yoki  deb olinsa, unda  tengliklar hosil bo’ladi. Bular kombinatsiyalarni hisoblashni osonlashtiradi.
Kombinatorik masalalarni yechishda o’rinlashtirish deb ataluvchi tushunchadan ham foydalaniladi.
Ta’rif. Chekli va  ta elementdan iborat to’plamdan bir-biridan yoki elementlari yoki elementlarining joylashish tartibi bilan farq qiladigan va   ta elementdan iborat qism to’plamlarni hosil qilish   elementdan  tadan o’rinlashtirish deb ataladi.
Berilgan  ta elementdan  tadan o’rinlashtirishlar soni  kabi belgilanadi va uning qiymati
yoki  formula bilan hisoblanadi.
Masalan,  to’plamdan  elementdan  tadan o’rinlashtirishlar  bo’lib, ularning soni  yoki 


Xulosa
Ehtimollar nazariyasi va matematik statistika – bir-birga uzviy bog‘liq matematik fanlar hisoblanadi. Hozirgi paytda bu sohalar bo‘yicha olingan bilimlar turli kasb mutaxassislariga juda ham ham zurur. O‘z faoliyatini maqsadini aniqlay olish va unga erishish uchun shaxdam qadamlar qo‘yish – kompetentli, raqobatbardosh qobiliyatli mutaxassisning xarakterli xususiyati, ehtimollar nazariyasi va matematik statistika esa har qanday fanga qaraganda ko‘proq shaxsning ijobiy o‘zgarishlari uchun yordam beradi. Ommaviy tasodifiy jarayonlar qonuniyatlarini (ehtimollar nazariyasi fani) va kuzatishlar natijalarini qayta ishlash muhim usul va yo‘llarini (matematik statistika o‘rganadigan) bilish har bir kasbdagi mutaxassis uchun amaliy masalalarni yechishda qo‘l keladi.
Ehtimollar nazariyasi va matematik statistikani o‘rganishni esa avvalo kombinatorika asoslari bilan tanishmasdan mumkin bo‘lmaydi. «Kombinatorika» atamasi matematikaga Leybnits tomonidan kiritilgan bo‘lib, uni 1666 yilda chop etilgan «Kombinatorika san’ati to‘g‘risida mulohazalar» nomli kitobida birinchi marta qo‘llagan edi. Hozirgi vaqtda kombinatorik usullar informatsiya nazariyasi muammolarini, chiziqli dasturlash masalalarini yechishda, transport masalalarini yechish uchun va h.k.larni hal qilishda keng qo‘llanilmoqda.
Kombinatorik masalalar nafaqat matematika go‘zalligini ko‘rsatishga, balki amaliy matematik masalarni yechishda yangi kompyuter texnoogiyalarining imkoniyatlarini ko‘rsatishga imkon beradi. Diskret matematikaning masalalaridan hisoblangan kombinatorik masalalar ko‘pincha ob’ektlarning turli kombinatorik konfiguratsiyalarini tanlashga va ular orasidan u yoki bu masala shartigav nuqtai nazaridan eng yaxshisini tanlashga olib kelinadi. Shuning uchun keng tarqalgan kombinatorik konfiguratsiyalarni hosil qilish algoritmlarini bilish masalani butunlay muvaffaqiyatli yechishning zarur sharti hisoblanadi.