Kombinatorika va uning asosiy qoidalari. O‘rin almashtirishlar. Kombinatsiyalar

Kombinatsiyalar. Kombinatorika va uning asosiy qoidalari

REJA:

1 Kombinatorika va uning asosiy qoidalari.
2 O‘rin almashtirishlar.
3 Kombinatsiyalar.

Kombinatorika va uning asosiy qoidalari. Bir qator amaliy masalalarni yechish uchun berilgan to‘plamdan uning qandaydir xossaga ega bo‘lgan elementlarini tanlab olish va ularni ma’lum bir tartibda joylashtirishga to‘g‘ri keladi.

1–TA‘RIF: Biror chekli to‘plam elеmеntlari ichidan ma’lum bir xossaga ega bo‘lgan elеmеntlardan iborat qism to‘plamlarni tanlab olish yoki to‘plam elеmеntlarini ma’lum bir tartibda joylashtirish bilan bog‘liq masalalar kombinatorik masalalar deyiladi.

Masalan, o‘nta ishchidan to‘rt kishidan iborat brigadalarni nеcha xil usulda tuzish mumkinligi (ishlab chiqarishni tashkil etish), molekulada atomlar qanday usullarda birlashishi mumkinligi (ximiya), oqsil moddalarda aminokislotalarni qanday tartiblarda joylashtirish mumkinligi (biologiya), turli bloklardan iborat mexanizmda bu bloklarni turli tartiblarda birlashtirish (konstruktorlik), bir nеcha dala uchastkalarida turli xil ekinlarini almashtirib ekish (agronomiya), davlat budjetini ishlab chiqarish tarmoqlari bo‘yicha taqsimoti (iqtisodiyot) kabilar kombinatorik masalalarga keladi va kombinatorikani inson faoliyatining turli yo‘nalishlarida qo‘llanilishini ko‘rsatadi.

2–TA‘RIF: Kombinatorik masalalar bilan shug‘ullanadigan matematik fan kombinatorika deyiladi.

Kombinatorikani mustaqil fan sifatida birinchi bo‘lib olmon matematigi G.Leybnits o‘rgangan va 1666 yilda «Kombinatorika san’ati haqida» asarini chop etgan.

Kombinatorikada qo‘shish va ko‘paytirish qoidasi dab ataluvchi ikkita asosiy qoida mavjud.

Qo‘shish qoidasi : Agar biror a tanlovni m(a) usulda, b tanlovni esa m(b) usulda amalga oshirish mumkin bo‘lsa va bu yerda a tanlovni ixtiyoriy tanlash usuli b tanlovni ixtiyoriy tanlash usulidan farq qilsa, u holda «a yoki b» tanlovni amalga oshirish usullari soni

m(a ёки b) = m(a) +m(b)

formula bilan topiladi.

Masala: Korxonada 10 erkak va 8 ayol xodim ishlaydi. Shu korxonadan bitta xodimni nеcha xil usulda tanlab olish mumkin?

Yechish: a - erkak xodimni tanlash, b - ayol xodimni tanlash bo‘lsin. Unda, shartga ko‘ra, m(a)=10, m(b)=8 bo‘lgani uchun bitta xodimni

m(a yoki b) = m(a) + m( b) = 10+8 = 18

usulda tanlash mumkin.

Ko‘paytirish qoidasi: Agarda biror a tanlovni m(a) usulda, b tanlovni m(b) usulda amalga oshirish mumkin bo‘lsa, u holda «a vа b» tanlovni (yoki (a,b) juftlikni) amalga oshirish usullari soni

m(a vа b) = m(a ) · m( b)

formula bilan topiladi.

Masalan, qurilishda 10 suvoqchi va 8 buyoqchi ishlasa, ulardan bir suvoqchi va bir buyoqchidan iborat juftlikni m(a vа b)=10×8=80 usulda tanlash mumkin.

Masala: 10 talabadan iborat guruhga ikkita yo‘llanma berildi. Bu yo‘llanmalarni nеcha xil usulda tarqatish mumkin?

Yechish: a I yo‘llanmani, b esa II yo‘llanmani tarqatishni ifodalasin. Unda m(a)=10 vа m(b)=9, chunki bitta talabaga I yo‘llanma berilganda II yo‘llanmaga 9 talaba da’vogar bo‘ladi. Demak, ikkita yo‘llanmani tarqatishlar soni m(a vа b) = =10×9=90 bo‘ladi.

Umumiy holda a₁, a₂, …., a_n tanlovlarni mos ravishda m(a₁), m(a₂), …., m (a_n) usullarda amalga oshirish mumkin bo‘lsa,

m(a₁ yoki a₂ yoki….yoki a_n ) = m(a₁)+ m( a₂ )+…+m(a_n), (1)

m(a₁ vа a₂ vа…. vа a_n ) = m(a₁) × m( a₂ ) ×…× m(a_n) (2)

formulalar o‘rinli bo‘ladi.

TEOREMA: n ta elementdan o‘rin almashtirishlar soni

Р_n= n! (3)

formula bilan hisoblanadi.

Bu yerda n! - “en faktorial” deb o‘qiladi va n! = 1 × 2 × 3 ×…× n kabi aniqlanadi. Bunda 0! = 1 dеb olinadi. Masalan, 3!=1·2·3=6, 4!= 1·2·3·4=24. Faktoriallarni hisoblashda (n+1)!=n!· (n+1) tenglikdan foydalanish qulay. Masalan, 5!=4!·5=120 bo‘ladi.

Umumiy holda n ta elеmеntdan k tadan olingan kombinatsiyalar soni kabi belgilanadi va uning qiymati quyidagi formula orqali hisoblanishini isbotlash mumkin:

(4)

Misol uchun beshta odamdan uch kishidan iborat komissiyani

usulda tuzish mumkin.

Masala: Xodimga haftaning ixtiyoriy ikki kunini dam olish uchun tanlash imkoni berildi. Xodim dam olish kunlarini necha usulda tanlashi mumkin?

Yechish: Hafta kunlarini n=7 elementli {1,2,3, … ,7 } to‘plam singari qarasak, dam olish kunlari {1,2}, {1,3}, {2,4},… kabi juftliklardan iborat bo‘ladi. Bunda {i,j} va {j,i} bitta variantni ifodalaydi. Demak, dam olish kunlarini tanlash n=7 elementdan k=2 tadan kombinatsiyalarni tashkil etadi va shu sababli ularning soni

bo‘ladi.

Berilgan n ta elеmеntdan k tadan o‘rinlashtirish soni kabi belgilanadi va uning qiymati quyidagi formula bilan hisoblanishini isbotlash mumkin:

(6)
formula bilan hisoblanadi.

Masalan, {a,b,c} to‘plamdan n=3 ta elementdan k=2 tadan o‘rinlashtirishlar {а;b},{а;с},{b;с},{b;а},{с;а},{с;b} bo‘lib, ularning soni

.

Masala: Talaba 4 ta fan bo‘yicha qo‘shimcha tayyorlanish uchun ularning har biriga haftaning bir kunini ajratmoqchi bo‘ldi. Talaba hafta kunlarini fanlarga necha usulda taqsimlashi mumkin?

Yechish: Talabani I-IV fanlar uchun haftaning tanlagan kunlariini k=4 ta elementli X={x₁, x₂, x₃, x₄} to‘plam, hafta kunlarini esa n=7 elementdan iborat H={1,2,3, … ,7 } to‘plam singari qaraymiz. Bu holda XÌH bo‘lib, uni hosil etish n=7 ta elementdan k=4 tadan o‘rinlashtirishlarga mos keladi, chunki bunda elementlarning joylashish tartibi ham ahamiyatga ega. Masalan, {2,4,6,7} taqsimotda I fanga dushanba (2), II fanga chorshanba (4), III fanga juma (6) va IV fanga shanba(7) kunlari ajratilgan bo‘ladi. Unda {4,2,6,7}, {6,4,2,7} kabilar turlicha taqsimotlarni ifodalaydi. Demak, talaba fanlarga hafta kunlarini


usulda taqsimlashi mumkin.
Ob’yektlarni tanlash va ularni ma’lum tartibda joylashtirish kabi matematik masalalar har doim insonni qiziqtiriradigan sohalardan hisoblangan.
Kombinatorika – bu matematikaning chekli to‘plam elementlarini berilgan qoidalar asosida tanlash va joylashtirish bilan bog‘liq masalalarni yechish usullarini o‘rganuvchi bo‘limdir.
Kombinatorika tarixiga nazar tashlasak, bir necha ming yil avval Xitoyda sehrli kvadratlar tuzish, qadimgi Yunonistonda figurali sonlar nazariyasini tuzish masalasini o‘rganishgan. Kombinatorika masalalari Samarqanddagi Ulug‘bek maktabining taniqli matematigi G’iyosiddin Jamshid Koshiy, X asrda yashab ijod etgan Umar Xayyom, keyinchalik Evropa olimlari jumladan, B.Paskal, J.Kordano, G.Leybnits, Ya.Bernulli, P.Ferma, L.Eyler va boshqa olimlarning ishlarida uchraydi.
Kombinatorikaning asosiy qoida va formulalari.
debchekli to‘plam elementlari sonini belgilaymiz. A A
Kombinatorikada sodda, o‘z-o‘zidan ravshan bo‘lgan, ammo muhim qoidalar bor. Bunday qoidalar sifatida jamlash, ko‘paytirish hamda kiritish va chiqarish qoidalari deb ataluvchi qoidalarni ko‘rsatish mumkin.