5- mavzu. Kombinatorika elementlari. Kombinatorika masalalari

5- mavzu. Kombinatorika elementlari.

1. 
   Kombinatorika masalalari.
   
2. 
   Yig’indi qoidasi.
   
3. 
   Ko’paytma qoidasi.
   

Kombinatorika - matematikaning ma'lum bir shartlarga bo'ysungan holda qancha xil kombinatsiyalarni yaratish mumkinligi haqidagi savollarni o'rganadigan bo'limi.
"Kombinatorika" so'zi lotincha "kombininare" so'zidan kelib chiqqan bo'lib, rus tiliga tarjima qilingan "birlashtirish", "birlashish" degan ma'noni anglatadi. "Kombinatorika" atamasini dunyoga mashhur nemis olimi mashhur Gotfrid Vilgelm Leybnits kiritgan. Kombinatorika matematikaning muhim sohasidir, bilimlari turli mutaxassisliklar vakillari uchun zarurdir. Kombinatoriya muammolarini fiziklar, kimyogarlar, biologlar, tilshunoslar, kod bo'yicha mutaxassislar va boshqalar hal qilishlari kerak. Kombinatoriya usullari nazariyaning ko'plab muammolarini hal qilish uchun asosdir ehtimolliklar va uning arizalari.
Qadimgi Yunonistonda
she'riy kattalikdagi uzun va qisqa bo'g'inlarning turli xil birikmalarini hisobladi, figurali sonlar nazariyasini o'rgandi, qismlardan iborat bo'lishi mumkin bo'lgan figuralarni o'rganib chiqdi va hokazo.
Vaqt o'tishi bilan turli xil o'yinlar paydo bo'ldi
(tavla, kartalar, shashka, shaxmat va boshqalar)
Ushbu o'yinlarning har biri raqamlarning turli xil kombinatsiyalarini ko'rib chiqishi kerak edi va g'olib ularni yaxshiroq o'rgangan, g'olib kombinatsiyalarni bilgan va yutqazishni oldini olishni bilgan edi.
Gotfrid Vilgelm Leybnits (1.07.1646 - 14.11.1716)
Nemis olimi G. Leybnits birinchi bo'lib 1666 yilda nashr etilgan "Kombinatorika san'ati to'g'risida" asarida kombinatorikani matematikaning mustaqil tarmog'i deb hisoblagan. Shuningdek, u birinchi marta "Kombinatorika" atamasini yaratdi.
Leonard Eyler (1707-1783) raqamlarni taqsimlash, moslashtirish, tsiklik tartib, sehr va lotin kvadratlarini qurish muammolarini ko'rib chiqdi, keyinchalik kosmos va figuralarning umumiy xususiyatlarini o'rganadigan katta va muhim topologiya faniga aylangan yangi tadqiqot maydoniga asos yaratdi.
Agar biron bir A ob'ekti m usulida, yana bir B ob'ekti n usulida tanlanishi mumkin bo'lsa, u holda "yo A yoki B" tanlovi (m + n) usulda bajarilishi mumkin.
Agar biron bir A ob'ekti m usulida, yana bir B ob'ekti n usulida tanlanishi mumkin bo'lsa, u holda "yo A yoki B" tanlovi (m + n) usulda bajarilishi mumkin.
Yig'ish qoidasidan foydalanganda siz A ob'ektini tanlash usullarining hech biri B ob'ekti tanlashning biron bir usuli bilan mos kelmasligini ta'minlashingiz kerak.
Agar shunday mosliklar bo'lsa, yig'indilar qoidasi bekor bo'ladi va biz faqat (m + n - k) tanlash usullarini olamiz, bu erda k - mos kelishlar soni.
1.Kombinatorika masalasi. Elementlarning turli kombinatsiyalari va ularning sonini topish bilan bog’liq masalalar kombinatorika masalalari deyiladi. Bunday masalalar matematika fanining tarmogi — kombinatorikada o’rganiladi. Kombinatorika asosan, XVII—XIX asrlarda mustaqil fan sifatida yuzaga kelgan bo’lib, uning rivojiga B.Paskal, P.Ferma, G.Leybnis, Y.Bernulli, L.Eyler kabi olimlar katta hissa qo’shganlar.
Kombinatorikada, asosan, chekli to’plamlar, ularning qism to’plamlari, chekli to’plam elementlaridan tuzilgan kortejlar va ularning sonini topish masalalari o’rganilgani uchun uni to’plamlar nazariyasining bir qismi sifatida qarash mumkin.
2.Yig’indi qoidasi. Kombinatorikada to’plamlar birlashmasi elementlari sonini hisoblash masalasi yig’indi qoidasi deb ataladi.

1. 
   Agar A∩B =∅ bo’lsa, n(A∪B) = n(A) + n(B) (1) bo’ladi.
   

Ya’ni kesishmaydigan A va B to’plamlar birlashmasi elementlari soni shu to’plamlar elementlari sonlarining yig’indisiga teng.

2. 
   Agar A∩B≠∅ bo’lsa, n(A∪B) = n(A) + n(B) - n(A∩B) (2) bo’ladi. Ya’ni umumiy elementga ega ikki to’plam birlashmasi ele- mentlari soni to’plamlarning har biri elementlari sonlari yig’indisidan ularning umumiy elementlari sonining ayrilganiga teng. (2) formula (1) formulaning umumiy holi bo’lib, (1) formulada n(A∩B)=∅, ya’ni to’plamlarning umumiy elementi yo’q.
   

(1) formula bilan yechiladigan kombinatorika masalasi umumiy holda quyidagicha ifodalanadi: agar x elementni k usul, y elementni m usul bilan tanlash mumkin bo’lsa, «x yoki y» elementni k + m usul bilan tanlash mumkin.
Masalan, savatda 8 ta olma va 10 ta nok bor bo’lsa, 1 ta mevani 8 + 10 = 18 usul bilan tanlash mumkin.
(2) formula bilan yechiladigan masala: 40 talabadan 35 tasi matematika imtihonini, 37 tasi rus tili imtihonini topshira oldi. 2-talaba ikkala fandan «2» oldi. Nechta qarzdor talaba bor?
Yechish. A — matematika fanidan «2» olgan, B - rus tili fanidan «2» olgan talabalar to’plami bo’lsin.