KOMBINATORIKA HAQIDA UMUMIY TUSHUNCHALAR.

Abstract

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 ichidan ma‟lum bir xossaga ega bo„lgan elementlardan 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 o„yinchidan to„rt kishidan iborat guruhlarni necha xil usulda tuzish mumkinligi (mashg„ulotlarni tashkil etish), molekulada atomlar qanday usullarda birlashishi mumkinligi (ximiya), oqsil moddalarda aminokislotalarni qanday tartiblarda joylashtirish mumkinligi (biologiya), turli bloklardan iborat mexanizmda bu bloklarni turli tartiblarda birlashtirish (konstruktorlik), bir necha dala uchastkalarida turli xil ekinlarini almashtirib ekish (agronomiya), davlat budjetini ishlab chiqarish tarmoqlari bo„yicha taqsimoti (iqtisodiyot) kabilar kombinatorik masalalarga keladi va kombinatorikani inson faoliyatining turli yo„nalishlarida qo„llanilishini ko„rsatadi. Ta’rif: Kombinatorik masalalar bilan shug„ullanadigan matematik fan kombinatorika deyiladi. Masalan: O„nta yakkakurashchilarni (boks, kurash, qilichbozlik, ...) bellashuvga bir necha xil usulda o„tkazish mumkin: - jismoniy sifatlardagi sifatlarni (kuch, tezkorlik, chaqqonlik, egiluvchanlik, chidamlilik) turlicha tartibda birlashtirish; - sport turlarida jismoniy sifatlarni (kuch, tezkorlik, chaqqonlik, egiluvchanlik, chidamlilik) har xil tartibda rivojlantirish. Kombinatorikada qo„shish va ko„paytirish qoidasi dab ataluvchi ikkita asosiy qoida mavjud. Qo‘shish qoidasi: Agar biror a tanlovni m(a) usulda, b tanlovni esa m(b) usulda amalga oshirish mumkin bo„lsa va bu yerda a tanlovni ixtiyoriy tanlash usuli b tanlovni ixtiyoriy tanlash usulidan farq qilsa, u holda «a yoki b» tanlovni amalga oshirish usullari soni m(a yoki b) = m(a) + m(b) formula bilan topiladi. Masala: Musobaqada 10 ta erkak va 8 ta ayol sportchi ishtirok etadi. Shu musobaqadan bitta ishtirokchini necha xil usulda tanlab olish mumkin? Yechish: a - erkak ishtirokchini tanlash, b - ayol ishtirokchini tanlash bo„lsin. Unda, shartga ko„ra, m(a)=10, m(b)=8 bo„lgani uchun bitta ishtirokchini m(a yoki b) = m(a) + m( b) = 10+8 = 18 usulda tanlash mumkin. Ko‘paytirish qoidasi: Agarda biror a tanlovni m(a) usulda, b tanlovni m(b) usulda amalga oshirish mumkin bo„lsa, u holda «a va b» tanlovni (yoki (a,b) juftlikni) amalga oshirish usullari soni m(a va b) = m(a ) · m( b) formula bilan topiladi. Masalan, musobaqada 10 ta suzuvchi va 8 ta eshkak eshuvchi ishtirok etsa, ulardan bir suzuvchi va bir eshkak eshuvchidan iborat juftlikni m(a va b)=10×8=80 usulda tanlash mumkin. Masala: 10 ta talabadan iborat guruhga olimpiadaga ikkita yo„llanma berildi. Bu yo„llanmalarni necha xil usulda tarqatish mumkin? Yechish: a I yo„llanmani, b esa II yo„llanmani tarqatishni ifodalasin. Unda m(a)=10 va m(b)=9, chunki bitta talabaga I yo„llanma berilganda II yo„llanmaga 9 talaba da‟vogar bo„ladi. Demak, ikkita yo„llanmani tarqatishlar soni m(a va b) = =10×9=90 bo„ladi. Umumiy holda a1, a2, …., an tanlovlarni mos ravishda m(a1), m(a2), …., m (an) usullarda amalga oshirish mumkin bo„lsa, m(a1 yoki a2 yoki….yoki an ) = m(a1)+ m( a2 )+…+m(an), (1) m(a1 va a2 va…. va an ) = m(a1) × m( a2 ) ×…× m(an) (2) formulalar o„rinli bo„ladi. Kombinatsiya – bu kombinatorikaning asosiy tushunchasidir. Bu tushuncha yordamida ixtiyoriy to„plamning qandaydir sondagi elementlaridan tashkil topgan tuzilmalar ifodalanadi. Kombinatorikada bunday tuzilmalarning o‘rin almashtirishlar, o‘rinlashtirishlar va guruhlashlar deb ataluvchi asosiy ko„rinishlari o„rganiladi. O‘rin almashtirishlar. Kombinatorik masalalarni yechishda keng qo„llaniladigan tushunchalar bilan tanishishni boshlaymiz. Ta’rif: Chekli va n ta elementdan iborat to„plamning barcha elementlarini faqat joylashish tartibini o„zgartirib qism to„plam hosil qilish n elementli o‘rin almashtirish deb ataladi. Berilgan n ta elementdan tashkil topadigan o„rin almashtirishlar soni Pn kabi belgilanadi. P fransuzcha “Permution”, ya‟ni o„rin almashtirish so„zining bosh harfidir. Teorema: n ta elementdan o„rin almashtirishlar soni Pn= n! (3) formula bilan hisoblanadi. Bu yerda n! - “en faktorial” deb o„qiladi va n! = 1×2×3×…×n kabi aniqlanadi. Bunda 0! = 1 deb olinadi. Masalan, 3!=1·2·3=6, 4!= 1·2·3·4=24. Faktoriallarni hisoblashda (n+1)!=n!·(n+1) tenglikdan foydalanish qulay. Masalan, 5!=4!·5=