Kombinatorika. Shaxmat masalasi Kombinatorika turidagi masalalar

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.

2. 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 a₁, a₂, . . . , a_m 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 R_m bilan belgilanadi. Bu son 1 dan m gacha bo’lgan barcha butun sonlarning ko’paytmasiga teng
R_m = 1*2*3* . . . *(m-1)*m = m!
Misol 1: Uchta {a, b, c} elemenlardan o’rin almashtirishlar soni topilsin. R₃ = 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 R₅ = 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 Aⁿ_m 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)
Aⁿ_m = m*(m-1)*(m-2)* . . . *(m-(n-1))
Misol 1: To’rtta {a, b, c, d} elementdan ikkitadan o’rinlatishlar sonini toping.
A²₄ = 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
A³₈ = 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 Sⁿ_m ko’rinishda belgilanadi. Bu sonni (u albatta butun son) quyidagi formula bilan tasvirlash mumkin
Sⁿ_m = R_m / (R_n * R_m-n ) = m! / (n!*(m-n)!)
m elementning 0 tadan birlashmasi 1 ga teng deb qabul qilinadi, ya’ni S⁰_m = 1.
O’z-o’zidan ravshanki, Sⁿ_m = S^m-n_{m .}
1-misol: Besh elementdan uchtadan barcha birlashmalarni toping. Formuladan foydalanib hisoblaymiz
S³₅ = 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
S³₈ = 8! / (3!*(8 – 3)!) = 1*2*3*4*5*6*7*8/ (1*2*3*1*2*3*4*5) = 56.