Kombinatorika elementlari haqida

Kombinatorika elementlari Reja: Kombinatorik masalalar va ularni yechishda qo'llaniladigan qoidalar. O'rin almashtirishlar. O'rinlashtirishlar. Takrorlanuvchi o'rinlashtirishlar. Guruhlashlar. Chekli to'plamning qism to'plamlari soni. Tayanch iboralar: ikkita va undan ortiq to'plamlarning Dekart ko'paytmasi, kombinatorika, kombinatorik masala, tartiblangan to'plam, tartiblanmaydigan o'rin almashtirish, takrorlanuvchi va takrorlanmaydigan o'rinlashtirishlar, guruhlashlar. 1. Kombinatorik masalalar. Ikkita chekli to'plamning Dekart ko'paytmasidagi juftliklarni hisoblash qoidasi va uni to'plamlar n ta bo'lgan hol uchun umumlashtirish kombinatorik masalalar deb ataluvchi masalalarni yechishda keng qo'llaniladi. Kombinatorik masalalar - bu shunday masalalarki, ular chekli to'plamlar elementlaridan turli-tuman kombinatsiya (birlashma)larning ba'zi qoidalari bo'yicha tuziladi. Jumladan, 4, 5, 6 raqamlardan foydalanib, mumkin bo'lgan barcha ikki xonali sonlarni shunday yozingki, sonning yozuvida ayni bir raqam takrorlanmasin degan masalada 4, 5, 6 raqamlar bilan bajariladigan turli kombinatsiyalarni, bu kombinatsiyalarda raqamlar takrorlanmasligi shartida ko'rib chiqish talab etiladi. Hayotda ham kombinatorik masalalar ko'plab uchraydi, bunda obyektlarning biror to'plamidan uning qism to'plamlarini tanlash, to'plam elementlarini biron bir tartibda joylashtirish va hoka'zolar qaraladi. Masalan, fermer o'z ishchilariga turli ishlarni bo'lib berishi, katta jamoa ichidan delegatlar tanlash, shaxmat o'yinida turli yurishlar seriyasidan eng ma'qulini tanlash kombinatorik masalalardan iboratdir. Ko'plab kombinatorik masalalarni yechishda qo'shish va ko'paytirish qoidalari qo'l keladi: a) qo'shish qoidasi: agar X to'plam m elementli, Y to'plam esa n elementli bo'lsa va ular o'zaro kesishmasa, to'plamning elementlari soni ga teng, ya'ni agar bo'lsa, bo'ladi. Umuman ixtiyoriy ikki X va Y to'plamlar uchun o'rinli bo'ladi. b) ko'paytirish qoidasi: agar X to'plam m elementga, Y to'plam n elementga ega bo'lsa, u holda to'plam (Dekart ko'paytma) elementga ega bo'ladi. Haqiqatdan, bo'lsa, to'plam ushbu mumkin bo'lgan barcha juftliklardan tashkil topadi: ……. Ko'rinib turibdiki, bu juftliklar soni mn ga teng. Buni qisqacha ko'rinishda yozish mumkin. Umuman, n ta to'plamlar berilgan bo'lsa, o'rinli bo'ladi. 1-misol. A shahardan B shaharga uchta yo'l B dan C ga esa 2 ta yo'l olib boradi. Necha xil usul bilan A shahardan C shaharga borish mumkin? yechish. A dan B ga 1-, 2- va 3-yo'llar olib boradi. B shahardan C shaharga a va b yo'llar olib boradi. 1-rasm. U holda A dan C ga qo'yiladigan usullar bilan borish mumkin: (1,a), (1,b), (2,a), (2,b), (3,a), (3,b). Buni boshqacha usul bilan ham hal qilsa bo'ladi. A va B gacha boradigan yo'llarki, tanlash usuli 3 ta, B dan C gacha boradigan yo'llarni tanlash usuli esa 2 ta. Bunda ko'paytma qoidasiga ko'ra, yo'llarning tartiblangan juftliklarini 32=6 usul bilan tanlash mumkinligi ko'rinib turibdi. Quyida kombinatorik masalalardan o'rin almashtirishlar, takrorlanmaydigan o'rin almashtirishlar, takrorlanmaydigan o'rinlashtirishlar va guruhlashlarni ko'rib chiqamiz. 2. O'rin ...