МЕТОДИКА РЕШЕНИЯ ЗАДАЧ КОМБИНАТОРНЫХ ЭЛЕМЕНТОВ

KOMBINATORIKA ELEMENTLARIGA DOIR MASALALAR YECHISH METODIKASI

Xamidov Sanjar Xakimovich - Buxoro shahar 24-sonli ko’rish bo’yicha imkoniyati cheklangan bolalar uchun ixtisoslashtirilgan davlat ta’lim muassasi matematika fani o’qituvchisi

Annotatsiya:

Maqolada kombinatorika oid asosiy tushunchalar, qo’shish qoidasi, ko’yayritish qoidasi, o’rin almashtirish, o’rinlashtirish, takrorlanuvchi o’rinlashtirish kabilar haqida ma’lumot keltirilib, ularga doir masalalar tadbiqi yoritilgan.

Kalit so’zlar: qo’shish qoidasi, ko’yayritish qoidasi, o’rin almashtirish, o’rinlashtirish, takrorlanuvchi o’rinlashtirish

Kombinatorik masalalar – bu shunday masalalarki, ular chekli to‘plamlar elementlaridan turli-tuman kombinatsiya (birlashma)larning ba’zi qoidalari bo‘yicha tuziladi. Jumladan, “1, 5, 9 raqamlardan foydalanib, mumkin bo‘lgan barcha ikki xonali sonlarni shunday yozingki, sonning yozuvida ayni bir raqam takrorlanmasin” degan masalada 1, 5, 9 raqamlar bilan bajariladigan turli kombinatsiyalarni, bu kombinatsiyalarda raqamlar takrorlanmasligi shartida ko‘rib chiqish talab etiladi.

Hayotda ham kombinatorik masalalar ko‘plab uchraydi, bunda ob’ektlarning biror to‘plamidan uning qism to‘plamlarini tanlash, to‘plam elementlarini biron bir tartibda joylashtirish va hokazolar 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 m´n 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 3´2=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 almashtirishlar.

Agar chekli X to‘plamning elementlari qandaydir yo‘l bilan raqamlangan bo‘lsa, uni tartiblangan to‘plam deymiz:  Kortej tushunchasidan farqli o‘laroq tartiblangan to‘plam elemetlari orasida o‘zaro tenglari bo‘lmaydi.

Masalan, (2, 3, 2, 4, 5) kortej tartiblangan to‘plam emas, (2, 3, 4, 5) esa tartiblangan to‘plam bo‘ladi. Bitta to‘plamni turlicha tartiblash mumkin. m elementli X to‘plamni necha xil usul bilan tartiblash mumkin degan masalani qaraymiz.

Har bir tartiblash quyidagicha amalga oshiriladi. To‘plamning qaysi bir elementini 1-nomer bilan, qaysi birini 2-nomer bilan va hokazo qaysi bir elementini m nomer bilan belgilaymiz. Agar birinchi element tanlangan bo‘lsa, ikkinchi elementni tanlash (m–1) ta elementning ichidan olinadi. Demak, birinchi element m usul bilan, ikkinchisi esa (m–1) usul bilan tanlanadi. Uchinchi element (m–2) usul bilan va hokazo oxirgi element m-o‘rinni egallaydi. Masalan, {5, 6, 7} elementli to‘plam quyidagicha tartiblanadi 567, 657, 756 – birinchi element 3 usul bilan olindi. 657, 756 – ikkinchi element 2 usul bilan tanlandi. Oxirgi tartiblash 765 bo‘ladi.

Umumiy holda ko‘paytirish qoidasiga asosan tartiblash usulining umumiy soni

ga teng bo‘ladi. Bunday tartiblash m elementdan takrorlanmaydigan o‘rin almashtirish deyiladi. Bunda har bir tartiblangan to‘plamning elementlari turlicha bo‘ladi.

3. O‘rinlashtirishlar.

Endi m elementli X to‘plam elementlaridan nechta k elementli tartiblangan to‘plamlar tuzish mumkin degan masalani qaraymiz.

Bu masalaning yuqoridagi masaladan farqi shundaki, bu yerda k elementli tartiblangan to‘plamni tuzish k ta elementni olish bilan tugallanadi. Bunday tartiblangan to‘plamlarning sonini topish uchun k ta m, m–1, m–2, …, m–k+1 sonlarni ko‘paytirish yetarli (chunki {m, m–1, m–2,…,m–k+1} to‘plamda k ta element mavjud).

Shunday qilib, X to‘plamdagi k elementli tartiblangan to‘plamlar soni

ga teng bo‘ladi. Bunday tartiblangan to‘plamlarni m elementdan k tadan takrorlanmaydigan o‘rinlashtirishlar deyiladi.  ning ifodasini ga ko‘paytirib va bo‘lib, uning ko‘rinishini o‘zgartirish mumkin:

Bunda  bo‘ladi, bu yerda 0!=1 deb olinadi.

4. Takrorlanuvchi o‘rinlashtirishlar.

Bu yerda quyidagi masala qaraladi: m elementli X to‘plamdan nechta uzunligi k ga teng bo‘lgan kortejlar tuzish mumkin. Bu masalani hal qilish uchun  dan iborat k ta ko‘paytuvchiga ega bo‘lgan Dekart ko‘paytmadagi kortejlar sonini topish yetarli. Bunda

Demak, m elementli X to‘plamdan tuzilgan uzunligi k ga teng bo‘lgan kortejlar soni ga teng.

m elementli X to‘plam elementlaridan tuzilgan uzunligi k ga teng bo‘lgan kortej, m elementdan k tadan tuzilgan takrorlanadigan o‘rinlashtirish deyiladi.

1-misol.  uch elementli to‘plam elementlaridan uzunligi 2 ga teng bo‘lgan nechta kortej tuzish mumkin.

Yechish. Ular quyidagilardan iborat:

(a, a), (a, b), (a, c)

(b, a), (b, b), (b, c)

(c, a), (c, b), (c, c)

Ularning soni  ta bo‘ladi.

2-misol. Agar sonning yozuvida raqamlarning takrorlanishi mumkin bo‘lsa, 1, 2, 3 raqamlardan foydalanib nechta 3 xonali son tuzish mumkin?

Yechish. Uch xonali sonlarning yozuvidagi har bir o‘ringa berilgan uchta raqamdan istalgan birini qo‘yish mumkin, ya’ni 1-raqamning tanlash usuli 3 ta, 2-raqamning tanlash usuli 3 ta, 3-raqamning tanlash usuli ham 3 ta. Demak, bu holda  ta uch xonali son tuzish mumkin.

5. Guruhlash.

Endi biz kombinatorikaning quyidagi masalasini qaraymiz:

m elementli X elementlaridan nechta har biri k elementli qism to‘plamlar tuzish mumkin?

Bunday qism to‘plamlar m elementdan k tadan takrorlanmaydigan guruhlashlar deyiladi. Ularning soni  bilan belgilanadi.

Ko‘rsatish mumkinki,

bo‘ladi.

Misol. 12 kishilik guruhdan nechta 5 kishilik (ishchil) delegatsiya tuzish mumkin.

Yechish.

6. Chekli to’plamning qism to’plamlari soni.

Chekli to’plamlarning qism to’plamlari soni. Umumiy holda chekli m elementli x to’plamning barcha qism to’plamlari sonini toppish masalasini qaraymiz. Uni hal qilish uchun istalgan tarzda x to’plamni tartiblaymiz. So’ng har bir qism to’plamni m o’rinli kortej sifatida shifrlaymiz: qism to’plamga kirgan element o’rniga 1, kirmagan element o’rniga 10 yozamiz. Shunda qism to’plamlar soni 2 ta 50,1} elementdan tuzilgan barcha m o’rinli kortejlar soniga teng bo’ladi.   _

A^m₂ = 2^m . Masalan, 2 ele ent to’plam ostilari soni 2² = 4, 3 elementli to’plamning to’plam ostilari soni 2³ = 8 ga teng. 

Yechim:

Berilgan son abcd ko’rinishdagi to’rt xonali son deb qaraymiz. Bunda quyidagi holler bo’lishi mumkin.

1-hol – 5 soni 1-o’rinda, mingliklar xonasida ya’ni a ning o’rnida bo’lsin. U holda b o’rniga 0,1,2,3,4,6,7,8,9 raqamlarini qo’yish mumkin. 5 kirmaydi, chunki sonda faqat bitta 5 qatnashishi kerak Ularning umumiy soni 9 ta . c va d lar ham 9 tadan raqam qabul qiladi. Demak, agar 5 raqami 1-o’rinda kelsa, bunday 4 xonali sonlarning umumiy soni (1 ta besh raqami qatnashgan)  1ˑ9 ˑ9 ˑ9=729 ta

2-hol – 5 soni 100 liklar xonasida ya’ni b ning o’rnida kelsin. Bunday 4 xonali sonlarning umumiy sonini topish quyidagicha bo’ladi. a ning o’rniga nol kelishi mumkin emas, aks holda u 3 xonali bo’lar edi. Masala shartiga ko’ra 5 raqami 1 marta qatnashishi kerak. Shuning uchun a faqat  – 1,2,3,4,6,7,8,9 raqamlarini qabul qiladi. b ning o’rniga faqatgina 5 soni keladi c va d o’rniga esa 0,1,2,3,4,6,7,8,9 raqamlarini qo’yish mumkin. 2 xonada 5 rami qatnashganlarning umumiy soni: 8 ˑ1 ˑ9 ˑ9=648

2-hol – 5 soni 10 liklar xonasida ya’ni c ning o’rnida kelsin. Xuddi yuqoridagi kabi fikr yuritib,

8 ˑ9 ˑ1 ˑ9=648 ni hosil qilamiz.

3-hol – 5 soni 1 liklar xonasida ya’ni d ning o’rnida kelsin. Xuddi yuqoridagi kabi fikr yuritib,

8 ˑ9 ˑ9 ˑ1=648 ni hosil qilamiz.

Endi bu sonlarni yig’indisini topsak 729+648ˑ3=2673 faqatgina bitta 5 raqami bor to’rt xonali sonlarning umumiy soni kelib chiqadi.

1  ˑ  9  ˑ  9  ˑ 9=729

8  ˑ  1 ˑ  9  ˑ  9=648

8  ˑ  9  ˑ  1  ˑ 9=648

8  ˑ  9  ˑ  9  ˑ 1=648

729+648*3=2673

Javob: 2673