Kombinatorika elementlari. Kombinatorika masalalari. Yig;indi va ko’paytma qoidasi Kombinatorika elеmеntlari. Reja

3.Ko’paytma qoidasi. Chekli to’plamlarning dekart ko’paytmasi elementlari sonini topishga imkon beradigan qoida ko’paytma qoidasi deyiladi.
A = {a₁, a₂, …, a_n} va B = {b₁,b₂, …, b_m} to’plamlar elementlaridan nechta tartiblangan (a_i, b_j.) juftlik tuzish mumkinligini ko’raylik. Barcha juftliklarni tartib bilan quyidagicha joylashtiramiz:


(a₁; b₁), (a₁; b₂), … , (a₁; b_m),
(a₂; b₁), (a₂; b₂), … , (a₂; b_m),
(a_n; b₁), (a_n; b₂), … , (a_n; b_m).
Bu jadvalda n ta qator va m ta ustun bo’lib, undagi barcha juftliklar soni n·mga teng. Bu yerda n = n(A) va m = n(B).
Ko’paytma qoidasi n(A×B) = n(A) · n(B) ko’rinishda yoziladi.
Ko’paytma qoidasiga oid kombinatorika masalasining umumiy ko’rinishi: «Agar x elementni m usul, y elementni n usul bilan tanlash mumkin bo’lsa, (x;y) tartiblangan juftlikni mn usul bilan tanlash mumkin».
Ikkitadan ortiq to’plamlar uchun bu formula quyidagicha yoziladi:
n(A₁×A₂× … ×A_n) = n(A₁) ·n(A₂) ·… · n(A_n),(n>2).
Masalan, A shahardan B shaharga 3 yo’l bilan, B shahardan C shaharga ikki yo’l bilan borish mumkin bo’lsa, A shahardan C shaharga necha xil usul bilan borish mumkin?
Yo’lning 1-qismini 3 xil, 2-qismini 2 xil yo’l bilan o’tish mumkin bo’lsa, umumiy yo’lni 3·2 = 6 usul bilan o’tish mumkin.
Umumlashgan ko’paytma qoidasi: «Agar x elementni m usul bilan, y elementni, x ni tanlab bo’lgandan so ‘ng, n usul bilan tanlash mumkin bo’lsa, (x;y) juftlikni mn usul bilan tanlash mumkin».
Masala. Nechta turli raqamlar bilan yozilgan ikki xonali sonlar bor?
Yechish. 1-raqamni 9 usul bilan (1, 2, …, 9), 2-raqamni ham 9 usul bilan (noldan boshlab o’nliklar raqamidan boshqa raqamlar) tanlash mumkin. Hammasi bo’lib 9·9 = 81 ta shunday son bor ekan.


Chekli to’plamlarning dekart ko’paytmasi elementlari sonini topishga imkon beradigan qoida ko’paytma qoidasi deyiladi.
A = {a₁, a₂, …, a_n} va B = {b₁,b₂, …, b_m} to’plamlar elementlaridan nechta tartiblangan (a_i, b_j.) juftlik tuzish mumkinligini ko’raylik. Barcha juftliklarni tartib bilan quyidagicha joylashtiramiz:
(a₁; b₁), (a₁; b₂), … , (a₁; b_m),
(a₂; b₁), (a₂; b₂), … , (a₂; b_m),
(a_n; b₁), (a_n; b₂), … , (a_n; b_m).
Bu jadvalda n ta qator va m ta ustun bo’lib, undagi barcha juftliklar soni n·mga teng. Bu yerda n = n(A) va m = n(B).
Ko’paytma qoidasi n(A×B) = n(A) · n(B) ko’rinishda yoziladi.
Ko’paytma qoidasiga oid kombinatorika masalasining umumiy ko’rinishi: «Agar x elementni m usul, y elementni n usul bilan tanlash mumkin bo’lsa, (x;y) tartiblangan juftlikni mn usul bilan tanlash mumkin».
Ikkitadan ortiq to’plamlar uchun bu formula quyidagicha yoziladi:
n(A₁×A₂× … ×A_n) = n(A₁) ·n(A₂) ·… · n(A_n),(n>2).
Masalan, A shahardan B shaharga 3 yo’l bilan, B shahardan C shaharga ikki yo’l bilan borish mumkin bo’lsa, A shahardan C shaharga necha xil usul bilan borish mumkin?
Yo’lning 1-qismini 3 xil, 2-qismini 2 xil yo’l bilan o’tish mumkin bo’lsa, umumiy yo’lni 3·2 = 6 usul bilan o’tish mumkin.
Umumlashgan ko’paytma qoidasi: «Agar x elementni m usul bilan, y elementni, x ni tanlab bo’lgandan so ‘ng, n usul bilan tanlash mumkin bo’lsa, (x;y) juftlikni mn usul bilan tanlash mumkin».
Masala. Nechta turli raqamlar bilan yozilgan ikki xonali sonlar bor?
Yechish. 1-raqamni 9 usul bilan (1, 2, …, 9), 2-raqamni ham 9 usul bilan (noldan boshlab o’nliklar raqamidan boshqa raqamlar) tanlash mumkin. Hammasi bo’lib 9·9 = 81 ta shunday son bor ekan.

Kombinatorika – bu diskret matematikaning diskret to’plam elementlarini berilgan qoidalar asosida tanlash va joylashtirish bilan bog’liq bo’lgan masalalarni yechish usullarini o’rganuvchi bo’limidir.
Qandaydir predmetlardan tashkil topgan guruxlar birikmalar deyiladi.
Birikmalarni tashkil etgan predmetlar elementlar deyiladi.
Birikmalarning 3 xil turi mavjud:

1. 
   o’rin almashtirish;
   
2. 
   o’rinlashtirish;
   
3. 
   gruppalash.
   

-ta’rif_.'>1-ta’rif. n ta elementli o’rin almashtirish deb, bir- biridan faqat elementlarining tartibi bilan farq qiladigan n ta elementli birikmalarga aytiladi.
Ularning soni quyidagi formula orqali topiladi:

Xossalari:
1.
2.
1-masala. 1, 2, 3 raqamlardan nechta 3 xonali son tuzish mumkin.
Yechilishi: ta .
2-ta’rif. Takrorli o’rin almashtirish deb, tarkibida A element marta, B element marta va hokazo, hamda C element marta qatnashuvchi uzunlikdagi har qanday n talikka aytiladi.
Takrorli o’rin almashtirishlarning soni quyidagi formula orqali topiladi:
.
2-masala. 1, 1, 2, 3 raqamlardan nechta 4 xonali son tuzish mumkin?
Yechilishi: ta
3-ta’rif. n ta elementdan m tadan o’rin almashtirish deb, har birida berilgan n ta elementdan m tasi olingan shunday birikmalarga aytiladiki, ularning har biri hech bo’lmaganda bitta elementi bilan, yoki faqat ularning joylashish tartibi bilan farq qiladi.
Ularning soni quyidagi formula orqali topiladi:

Xossalari:

3-masala. 1, 2, 3, 4, 5 raqamlardan nechta 2 xonali son tuzish mumkin.
ta
n ta elementdan m tadan takrorlanuvchi o’rinlashtirishlarda ixtiyoriy element 1 dan m martagacha uchrashi yoki umuman uchramasligi mumkin, ya’ni har bir n ta elementdan m tadan takrorlanishli o’rinlashtirish nafaqat turli elementlardan, balki m ta ixtiyoriy ravishda takrorlanuvchi ixtiyoriy elementlardan tashkil topishi mumkin.
n ta elementdan m tadan takrorlanuvchi o’rinlashtirishlar soni quyidagi formula bilan hisoblanadi:

4-masala. Seyfning shifrli kodi besh xonali sondan iborat. Kodlashtirilganda nechta turli kombinatsiya tuzish mumkin?
Yechilishi: Kodlashtirishda 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 raqamlarning hammasidan foydalanish mumkin. n=10. kod besh xonali son bo’lgani uchun m=5.
usul bilan kodlashtirish mumkin.
5-ta’rif. n element orasidan m ta elementdan tuzilgan gruppalash deb, har birida berilgan n ta elementdan m tasi olingan shunday birikmalarga aytiladiki, ularning har biri hech bo’lmaganda bitta element bilan farq qiladi.
Ularning soni quyidagi formula orqali topiladi:

Xossalari:
1)
2)
3)
4)
5-masala. Yashikda 8 ta detal bor. Ulardan 3 ta qilib nechta usulda olish mumkin?
Yechilishi:
n ta elementdan m tadan element bo’lgan takrorlanishli gruhlashlarda ixtiyoriy element 1 dan m martagacha uchrashi yoki umuman uchramasligi mumkin, ya’ni har bir n ta elementdan m tadan takrorlanishli o’rinlashtirish nafaqat elementlardan, balki m ta ixtiyoriy ravishda takrorlanuvchi ixtiyoriy elementlardan tashkil topishi mumkin. Tarkibi bir xil bo’lib, faqat elementlarning tartibi bilan farq qiluvchi guruhlar farq qilinmaydi, ya’ni faqat elementlarining joylashishi.
tartibi bilangina farq qiluvchi guruhlar bir xil guruhlar hisoblanadi.
n ta elementdan m tadan takrorlanishli gruhlashlar soni quyidagi formula orqali hisoblanadi:

Izoh: m n dan katta bo’lishi ham mumkin.
6-masala. 4 xil kitobdan necha usul bilan 7 kitobdan iborat to’plam yozish mumkin?
Yechilishi: to’p.


Savollar

1. 
   Kombinatorika masalasi ta’rifini bering.
   
2. 
   Kombinatorika fani rivojiga xissa qo’shgan olimlarni ayting.
   
3. 
   Yig’indi qoidasining turli xollarini ko’rsating.
   
4. 
   Ko’paytma qoidasini ayting va misollar keltiring.
   

Foydalaniladigan asosiy adabiyotlar ro‘yxati
Asosiy adabiyotlar

1. 
   Xamedova N.A, Ibragimova Z, Tasetov T. Matеmatika. Darslik. T.: Turon-iqbol, 2007. 363b.(26-28 betlar)
   
2. 
   Н.А.Хамедова, А.В.Садыкова, И.Ш.Лактаева. Maтемaтикa. Учебное пособие. Т.: Жахон-принт, 2007.(90-92 betlar)
   

Qo‘shimcha adabiyotlar

1. 
   Abdullayeva B.S., Sadikova A.V., Muxitdinova M.N., Toshpo‘latova M.I., Raximova F. Matematika. TDPU. (Boshlang‘ich ta’lim va sport-tarbiyaviy ish bakalavriyat ta’lim yo‘nalishi talabalari uchun darslik) Toshkent-2012, 284 bet (65-70).