Raxmanova gulnoza annakulovna

2.5 Kombinatorika elementlari mavzusini o’qitishni
takomillashgan variant
Kombinatorika (lot. combinare -birlashtirish), kombinator analiz, kombina-tor matematika — matematikaning chekli toʻplamlar ustida bajariladigan amal-larni oʻrganadigan boʻlimi. Eng koʻp qo’llanadigan amallari: 1) toʻplamni tartib-lash, yaʼni berilgan p elementli toʻplam elementlarini nomerlab (ag a2, ..., ap), ketma-ketlik hosil qilish. Bunday ketma-ketlik p elementdan tuzilgan o’rin al-mashtirish deyiladi.
Variantlarni qarab chiqishga oid kombinatorika masalalari. Kombinatorika-ning asosiy savoli−“qancha?”, asosiy masalasi esa berilgan chekli sondagi obyektlarning u yoki bu shartga boʻysunuvchi har xil kombinatsiyalarini sanash-dir. Variantlarni birma-bir qarab chiqishda quyidagi ikkita qoidaga amal qilish maqsadga muvofiq:
1. Kombinatsiyalarni harflar yoki raqamlar ketma-ketligi bilan belgilaymiz, bunda belgilash bir qiymatli boʻlishi kerak.
2. Kombinatsiyalarni alifbo tartibida (agar belgilashda harflar ishlatilsa) yoki sonlarni oʻsish tartibida yozib chiqish. Bunday holatda birorta ham variant qolib ketmaydi va ayrim variantlarning takrorlanishiga yoʻl qoʻyilmaydi.
1-masala. Madina olma, nok va mandarinni еmoqchi. Buni u necha usul bilan bajarishi mumkin?  Mevalarni harflar bilan belgilaymiz: O−olma, N−nok, M−mandarin. Bu holda, masalan, NMO−bu dastlab nok, soʻng mandarin va oxirida olma еyilishiga mos variant. Variantlarni yozib chiqamiz: MNO, MON, NMO, NOM, OMN, ONM. Jami 6 ta usul hosil boʻldi. ▲
2-masala. Raqamlari yigʻindisi 4 dan kichik boʻlgan toʻrt xonali sonlar nechta?  Raqamlari yigʻindisi 1, 2 va 3 boʻlgan toʻrt xonali sonlarni oʻsish tar-tibida yozamiz: 1000; 1001; 1002; 1010; 1011; 1020; 1100; 1101; 1110; 1200; 2000; 2001; 2010; 2100; 3000. Jami 15 ta son hosil boʻldi. ▲
3-masala. Birinchi raqami 2 boʻlgan va 1, 2, 3, 4 va 5 raqamlardan tashkil topgan uch xonali sonlar nechta?  Oxirgi ikkita raqam bo‘yicha barcha variant-larni qarab chiqamiz: 211 212 213 214 215 221 222 223 224 225 231 232 233 234 235 241 242 243 244 245 251 252 253 254 255 Javob. Jami 25 ta son. ▲
4-masala. Maktabda beshta 11-sinf mavjud. Shu sinflardan ikki nafar nav-batchini tanlashimiz kerak, bunda har qanday juftlikda turli sinf oʻquvchilari boʻ-lishi kerak. Buni necha usulda amalga oshirsa boʻladi?  Sinflarni 1, 2, 3, 4, 5 ra-qamlar bilan belgilaymiz va variantlarni yozib chiqamiz: (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5). Javob. Jami 10 ta usul. ▲
Qoʻshish va koʻpaytirish qoidalari.
Qoʻshish va koʻpaytirish qoidalari kombinatorika masalalarini еchishda eng koʻp qoʻllaniladigan va samarali usullar hisoblanadi.
5-masala. Savatda 5 ta olma va 3 ta nok bor. Savatdan 1 ta meva tanlashni necha usulda amalga oshirish mumkin?  Olmani 5 ta usulda, nokni esa 3 ta usulda tanlash mumkin. Demak, savatdan mevani tanlash 5+3=8 usulda amalga oshirilishi mumkin. ▲
6-masala. a) Toqqa 7 ta yoʻl olib boradi. Sayyoh toqqa chiqib, soʻng pastga tushmoqchi. Bu ishni necha usulda amalga oshirish mumkin? b) Agar yuqoriga chiqish va pastga tushish har xil yoʻllar bilan amalga oshirilsa, javob qanday oʻzgaradi?
a) Sayyoh toqqa 7 usulda chiqishi mumkin, har bir chiqishda 7 ta usulda pastga tushishi mumkin. Jami 7+7+7+7+7+7+7=7⋅7=49 ta usul.
b) Sayyoh toqqa 7 usulda chiqishi mumkin, har bir chiqishda 6 usulda pastga tushishi mumkin. Jami 7⋅6=42 ta usul. ▲
7-masala. Do‘konda 5 ta turli piyola, 3 ta turli likopcha va 4 ta turli choy qoshigʻi bor.
a) Piyola va likopcha juftligi necha usulda xarid qilinishi mumkin?
b) Piyola, likopcha va choy qoshigʻi uchligi necha usulda xarid qilinishi mumkin? c) Turli nomdagi ikkita idishning juftligi necha usulda xarid qilinishi mumkin?
a) Dastlab piyolani tanlaymiz. Unga juft qilib uchta likopchadan ixtiyoriysini olishimiz mumkin. Jami beshta piyola boʻlgani sababli turli juftliklar soni 15 (15 = 5⋅3) ga teng.
b) Oldingi masaladagi 15 juftliklardan ixtiyoriysini tanlaymiz. Uni choy qoshigʻi bilan “uchlik” kacha 4 ta usulda toʻldirish mumkin. Shuning uchun barcha uchliklar soni 60 (60 =15⋅4 =5⋅3⋅4) ga teng.
c) Uchta holat boʻlishi mumkin: birinchisi piyola va likopcha juftligi 29 sotib olinadi, ikkinchisi – piyola va qoshiq, uchinchisi– likopcha va qoshiq. Har bir holat uchun juftliklar soni oson topiladi (birinchisida – 15 ta, ikkinchisida – 20 ta, uchinchisida – 12 ta). Hammasini qoʻshib chiqsak, barcha variantlar sonini topamiz: 47 ta. ▲
8-masala. Barcha raqamlari juft boʻlgan besh xonali sonlar nechta?  Besh xonali sonning raqamlari uchun 5 ta oʻrinni belgilaymiz. Birinchi oʻringa 4 ta raqam qoʻysa boʻladi: 2, 4, 6 yoki 8. Ikkinchi oʻringa beshta raqam qoʻysa boʻladi: 0, 2, 4, 6 yoki 8. Uchinchi, toʻrtinchi va beshinchi oʻrinlarga ham shu beshta raqamni qoʻysa boʻladi: 0, 2, 4, 6 yoki 8. Demak, jami oʻrinlarni toʻldirishning 4⋅5⋅5⋅5⋅5=2500 usuli mavjud. Barcha raqamlari juft boʻlgan besh xonali sonlar ham 2500 ta. ▲
Bu masalalarni hal qilishda quyidagi qoidalardan foydalandik.
Qoʻshish qoidasi. Agar A obyekt m ta usul bilan, B obyekt esa boshqa n ta usul bilan tanlanishi mumkin boʻlsa, u holda (A yoki B) m + n ta usul bilan tanlanishi mumkin. Koʻpaytirish qoidasi. Agar A obyekt m ta usul bilan tanlansa va shunday tanlashdan soʻng B obyekt n ta usul bilan tanlanishi mumkin boʻlsa, u holda (A va B) mn ta usul bilan tanlanishi mumkin. Takrorli va takrorsiz o‘rinlashtirishlar 9-masala. Xonada beshta chiroq bor. Ularning har biri yo yonishi, yo yonmasligi mumkin. Xonani nechta usulda yoritish mumkin?  Har bir chiroq uchun ikkita variant mavjud – yo yonish, yo yonmaslik. Jami boʻlib 2⋅2⋅2⋅2⋅2=25 =32 ta usul. ▲
Yuqoridagi masalani umumlashtiramiz: n ta elementdan tashkil topgan toʻplamning barcha qism toʻplamlari sonini topaylik.
Toʻplamning n elementlaridan har biri uchun ikkita imkoniyat bor−u yo qism toʻplamga tegishli, yo tegishli emas. Oldingi masalaga oʻxshab 2n ta variant hosil boʻladi.
10-masala. 3 ta tovuq, 4 ta oʻrdak va 2 ta gʻoz bor. Bir nechta qush tanlanmoqda, bunda tanlangan qushlar ichida ham tovuq, ham oʻrdak, ham gʻoz boʻlishi shart. Bunday variantlar soni nechta?  Ixtiyoriy tovuq tanlanganlar ichida yo bor, yo yoʻq. Shuning uchun tovuqni 2³ ta usul bilan tanlab olishimiz mumkin. Shartga koʻra tovuq albatta boʻlishi uchun 2³ − 1=7 ta imkoniyat bor. Xuddi shunday, oʻrdakni 4² −1=15 ta, gʻozni esa 2² − 1=3 ta usulda tanlasa boʻladi. Jami 7⋅15⋅3=315 ta usul. ▲
11-masala. Futbol jamoasida 11 nafar oʻyinchi bor.
a) Jamoa sardori va uning yordamchisi;
b) jamoa sardori, uning birinchi yordamchisi, uning ikkinchi yordamchisi necha usulda tayinlanishi mumkin?
a) Sardor etib jamoaning 11 nafar oʻyinchisidan ixtiyoriysini tayinlash mumkin. Sardorning yordamchisi etib qolgan 10 nafar oʻyinchidan ixtiyoriysini tayinlash mumkin. Shuning uchun jamoa sardori va uning yordamchisi 11⋅10=110 usulda tayinlanishi mumkin.
b) Jamoa sardori va uning birinchi yordamchisini 11⋅10=110 usulda tayinladik. Ikkinchi yordamchi etib qolgan 9 nafar oʻyinchidan ixtiyoriysini tayinlash mumkin. Shuning uchun jamoa sardori, uning birinchi yordamchisi, uning ikkinchi yordamchisi 11⋅10⋅9=990 usulda tayinlanishi mumkin. ▲
Bu masalada biz 11 elementli toʻplamda tartiblangan juftliklar va tartiblangan uchliklar sonini topdik. Endi bu masalani umumiy holda еchaylik.