Kombinatorika. Shaxmat masalasi Kombinatorika turidagi masalalar



Yüklə 230,5 Kb.
səhifə2/2
tarix07.10.2023
ölçüsü230,5 Kb.
#152995
1   2
комбинаторика

Kr




Kr




Kr




























Kr




Kr




Kr




Kr




























5-rasm.



Joylashtirishlarga doir masalalarning boshqa bir sinfi figuralar taxtaning hamma bo’sh kataklarini zarba ostida tutuvchi joylashuvlarining minimal soni bilan bog’liq. Bu maqsad uchun beshta farzin (6- rasm), sakkizta rux (ularni 3-rasmda farzinlar turgan kataklarga qo’yish mumkin), 8 ta fil (7-rasm) 12 ta asp (8-rasm) 9 ta shox (9-rasm) olish kerak. Bunda barcha figura uchun ham zarur joylashuvlar soni ma’lum deya olmaymiz.
Taxtani figuralar soni beshtadan kam bo’lganda qo’riqlab bo’lmaydi, ammo beshta farzindan ikkitasini ruxlar bilan yoki hatto bir rux va bir shox yoki fil bilan almashtirib «iqtisod qilish» mumkin (10-rasm).








































F













F




























F




























F













F




























































6-rasm.
















S






















S






















S






















S






















S






















S






















S






















S









7-rasm.


































K






















K

K




K

K



















K





































K




K

K










K

K







K






























8-rasm.




Kr







Kr







Kr














































Kr




Kr







Kr





























































Kr







Kr







Kr



























9-rasm.
















L


































F































S































F


































F







































10-rasm.

    1. Kombinatorikaning asosiy tushunchalari


Qandaydir buyumlarning bir yoki bir nechta to’plami berilgan bo’lib, bu buyumlarning biror qo’yilgan shartni qanoatlantiruvchi kombinatsiyalarini tuzish talab qilingan bo’lsin. Mumkin bo’lgan kombinatsiyalar sonini sanash masalasi kombinatorli masala deyiladi.
«Birlashma» degan umumiy nom bilan biror sonli o’zaro har xil predmetlardan (elementlardan) tuzilgan quyidagi uch tur kombinatsiyalarini belgilash qabul qilingan.

O’rin almashtirish


m ta har xil a1, a2, . . . , am elementlarni olamiz va ularning sonini o’zgarishsiz qoldirib va faqat ularning tartiblarinigina almashtirib, bu elementlarni mumkin bo’lgan barcha usullar bilan almashtirib chiqamiz. Shunday yo’l bilan hosil qilingan kombinatsiyalarning har biri (jumladan dastlabkisi ham) o’rin almashtirishlar degan nom bilan ataladi. m ta elementdan umumiy o’rinlashtirishlarning umumiy soni Rm bilan belgilanadi. Bu son 1 dan m gacha bo’lgan barcha butun sonlarning ko’paytmasiga teng
Rm = 1*2*3* . . . *(m-1)*m = m!
Misol 1: Uchta {a, b, c} elemenlardan o’rin almashtirishlar soni topilsin. R3 = 1*2*3 = 6 ni hosil qilamiz. Haqiqatan ham oltita o’rin almashtirishlar mavjud
abc acb bac bca cab cba
Misol 2: Sport tashkiloti prezidumiga saylangan beshta kishi o’rtasida beshta lavozimni nechta usul bilan taqsimlash mumkin? Agar lavozimlar ro’yxatini biror tartibda tuzib va har bir lavozim to’g’risiga nomzodlar familiyalarini yozsak har bir taqsimotga biror «o’rinlashtirish» mos keladi. Bunday o’rin almashtirishlarning umumiy soni R5 = 1*2*3*4*5 = 120.
O’rinlatish
m ta har xil elementlardan har biri n ta elementdan iborat guruhlar tashkil etamiz. Olingan n ta element har xil tartibda joylashadi. Bu usulda hosil qilingan kombinatsiyalar m elementdan n tadan o’rinlatish deyiladi. m elementdan n tadan o’rinlatishlarning umumiy soni Anm ko’rinishda belgilanadi. Bu son eng kattasi m ga teng bo’lgan n ta ketma-ket butun sonlarning ko’paytmasiga teng. O’rin almashtirishni o’rinlatishning xususiy holi deb qarash mumkin (m elementni m tadan o’rinlatish)
Anm = m*(m-1)*(m-2)* . . . *(m-(n-1))
Misol 1: To’rtta {a, b, c, d} elementdan ikkitadan o’rinlatishlar sonini toping.
A24 = 4*3 = 12 ni hosil qilamiz.
Ular quyidagi o’rinlatishlar: ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db,dc
Misol 2: Majlis prezidumiga sakkiz kishi saylandi. Nechta usul bilan ular o’rtasida rais, sekretar va hisobchi vazifalarini taqsimlash mumkin? Bu 8 elementdan 3 tadan o’rinlatishlar soniga teng
A38 = 8*7*6 = 336


Birlashma (kombinatsiya)
M ta turli elementdan har birida n tadan element bo’lgan guruhlar tuzamiz. Bunda guruhlardagi elementlarning tartibini hisobga olmaymiz. Bu usulda hosil qilingan kombinatsiya m elementdan n tadan qilib tuzilgan birlashma deyiladi.
O’zaro har xil bo’lgan birlashmalarning umumiy soni Snm ko’rinishda belgilanadi. Bu sonni (u albatta butun son) quyidagi formula bilan tasvirlash mumkin
Snm = Rm / (Rn * Rm-n ) = m! / (n!*(m-n)!)
m elementning 0 tadan birlashmasi 1 ga teng deb qabul qilinadi, ya’ni S0m = 1.
O’z-o’zidan ravshanki, Snm = Sm-nm .
1-misol: Besh elementdan uchtadan barcha birlashmalarni toping. Formuladan foydalanib hisoblaymiz
S35 = 5! / (3!*(5 – 3)!) = 1*2*3*4*5/ (1*2*3*1*2) = 10
Bu quyidagi birlashmalardir: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.
2-misol: Mo’ljallangan sakkizta nomzoddan uchta hisobchini tanlab olish kerak. Buni nechta usul bilan bajarish mumkin? Har bir hisobchining vazifalari bir xil bo’lganligi uchun o’rinlatish emas, balki birlashma hisoblanadi. Bunday birlashmalar soni 56 ga teng, ya’ni
S38 = 8! / (3!*(8 – 3)!) = 1*2*3*4*5*6*7*8/ (1*2*3*1*2*3*4*5) = 56.
Yüklə 230,5 Kb.

Dostları ilə paylaş:
1   2




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin