Kombinatorika asosiy prinsipi va kombinatotikaning asosiy formulalari’’

Mavzuga doir yechimlari bilan berilgan topshiriqlardan namunalar

1. Korxonada 10 erkak va 8 ayol xodim ishlaydi. Shu korxonadan bitta xodimni necha xil usulda tanlab olish mumkin?

   
   Yechish:  - erkak xodimni tanlash,  - ayol xodimni tanlash bo’lsin. U holda, shartga ko’ra,  bo’lgani uchun bitta xodimni  usulda tanlash mumkin.
   

2. 10 ta talabadan iborat guruhga ikkita yo’llanma ajratildi. Bu yo’llanmalarni necha xil usul bilan tarqatish mumkin?

   
   Yechish:  birinchi yo’llanmani,  esa ikkinchi yo’llanmani tarqatishni ifodalasin. U holda  va  chunki bitta talabaga birinchi yo’llanma berilganda, ikkinchi yo’llanmaga to’qqizta talaba davogar bo’ladi. Demak, ikkinchi yo’llanmani tarqatishlar soni  ga teng bo’ladi.
   

3. Qurilishda 10 ta suvoqchi va 8 ta bo’yoqchi ishlaydi. Ulardan bir suvoqchi va bir bo’yoqchidan iborat juftlikni necha usulda tanlash mumkin?

   
   

Yechish:  va  bo’lgani uchun 

4. Nazoratchi korxonada ishlab chiqarilgan 5 ta maxsulot sifatini ketma-ket tekshirishi kerak. Nazoratchi buni nechta usulda amalga oshirishi mumkin?

   
   

Yechish: Bu 5 ta maxsulot sifatini ketma-ket tekshirishlar 5 tadan o’rinlashtirishlardan iborat.

Ya’ni,  bo’ladi.

5. Ishlab chiqarish korxonasini tekshirish uchun besh kishidan iborat guruh ajratildi. Shu besh kishidan tarkibida uch kishi bo’lgan guruhni necha xil usulda tuzish mumkin.

   
   Yechish:  formuladan foydalanamiz. Bizda  bo’lgani uchun 
   

6. Tikuvchilik fabrikasida ishlayotgan xodimga haftaning ixtiyoriy ikki kunini dam olish uchun tanlash imkoni berildi. Xodim dam olish kunlarini necha usulda tanlashi mumkin?

   
   Yechish: Hafta kunlarini  elementli  to’plam sifatida qarasak, dam olish kunlari    kabi juftliklardan iborat bo’ladi. Bunda  va  bitta variantni ifodalaydi. Demak, dam olish kunlarini tanlash  elementdan  tadan kombinatsiyalarni tashkil etadi va ularning soni  bo’ladi.
   

7. 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 fanlari uchun haftaning tanlagan kunlarini  ta elementli  to’plam, hafta kunlarini esa  elementlidan iborat  to’plam sifatida qaraymiz. Bu holda   bo’lib, uni hosil etish  elementlidan  tadan o’rinlashtirishlarga mos keladi, chunki bu holda elementlarning joylashishi tartibi ham ahamiyatga ega. Masalan,  taqsimotda birinchi fanga dushanba (2), ikkinchi fanga chorshanba (4), uchinchi fanga juma (6) va to’rtinchi fanga shanba (7) kunlari ajratilgan bo’ladi. Unda  kabilar turlicha taqsimotlarni ifodalaydi. Demak, talaba fanlarga hafta kunlarini
   usulda tanlashi mumkin.
   

8. Xorijiy tillar fakulteti ingliz tili yo’nalishining birinchi kursida 10 ta fan o’qitiladi va har kuni 4 xil dars o’tiladi. Kunlik dars necha usul bilan taqsimlab qo’yilishi mumkin?

   
   

Yechish: Darslarning barcha mumkin bo’lgan kunlik taqsimoti o’n elementdan to’rttadan olib tuzish mumkin bo’lgan barcha o’rinlashtirishlardan iborat. Uni  formuladan foydalanib topamiz. Bizda  bo’lgani uchun

9. Butun sonlarning har biri uchta har xil qiymatli raqamlar bilan ifoda qilinadigan bo’lsa, qancha butun son tuzish mumkin?

   
   

Yechish: Izlangan son 9 ta qiymatli raqamdan 3 tadan olib tuzilgan o’rinlashtirishlardan iborat. Ya’ni,

Buni  formuladan ham topish mumkin. Unga asosan 

A va B to’plamlar berilgan bo’lsin. Bu to’plamlar birlashmasining elementlari sonini yig’indi qoidasidan foydalanib topiladi. Bu qoida quyidagicha: A to’plamning elementlari n ta bo’lsin. r(A)=n. B to’plamning elementlari soni m ta bo’lsin. r (B)=m.

A va B to’plamlar umumiy elementga ega bo’lmasa,u holda bu to’plamlar birlashmasining elementlari soni A to’plam elementlari soni bilan B to’plam elementlari soni yig’indisidan iborat bo’ladi. Yani:
a) r (A B) = r (A) + r (B) = n + m
Bu qoidani n ta to’plam uchun ham to’g’ri deb qabul qilamiz. Ya’ni A₁, A₂ … A_n ta to’plam berilgan bo’lsin va bu to’plamlar umumiy elementga ega emas.Ya’ni o’zaro kesishmaydigan to’plamlardir. U holda. r (A₁ A₂ … A_n)=r(A₁)+r(A₂)+…+r(A_n)
b) A va B to’plamlar umumiy elementga ega bo’lsin.
r (A  B) = r (A) + r (B) – r (A  B)
A₁ A₂ … A_n to’plam uchun bu holni umumlashtiramiz. Ya’ni bu berilgan n ta to’plam umumiy elementga ega bo’lsa, u holda bu to’plamlar birlashmasining elementlari soni quyidagicha bo’ladi:
r (A₁ A₂ … A_n) = r (A₁) + r (A₂) +… + r (A_n) – r (A₁  A₂) – r (A₂  A₃) …- r (A_n-1 A_n ) + r (A₁ A₂  A₃) +…+ (-1^n-1) r (A₁ A₂…A_n).
Ya’ni n ta to’plam birlashmasining elementlari soni shu to’plamlar elementlari soniga juft sondan olingan to’plamlar kesishmalarining soni manfiy ishora bilan toq sondagi to’plamlar kesishmalarining elementlari soni musbat ishora bilan qo’shilishiga teng bo’ladi. Bu yig’indi A₁ A₂ …A_n to’plamlar birlashmasining elementlari sonini bildiradi.
X va Y chekli to’plamlar dekart ko’paytmasining elementlari soni X to’plam bilan Y to’plamdagi elementlari sonlarining ko’paytmasiga teng. X va Y to’plamlar dekart ko’paytmasi (x,y) ko’rinishidagi juftliklardan iborat bo’lib,bu juftliklar soni nechta degan savolga ko’paytirish qoidasi javob beradi.Bu juftliklarni tuzaylik.
X = {x₁, x₂ …x_n} va Y = {y₁, y₂,…y_m}
XY
(x₁; y₁) (x₁; y₂) …(x₁; y_m)
(x₂ ;y₁) (x₂ ;y₂)…(x₂; y_m)
…………………………
(x_n; y₁) (x_n; y₂)…(x_n; y_m)
Bu yerda har bir satrda m ta juftlik bor bo’lib,har bir ustunda n ta juftlik bor bo’lib,hammasi bo’lib bu yerdagi juftliklar soni m*n juftlik bor.
r (X Y) = r (X) · r (Y)
Bu qoida n ta to’plam uchun ham to’g’ri.
r (X₁  X₂ … X_n) = r (X₁) · r (X₂) …· r (X_n)

Ta’rif: n ta elementni k tadan o’rinlashtirish deb k tadan bitta elementi yoki elementlarining tartibi bilan farq qiluvchi gruppalarga (kombinasiyalarga) aytiladi.

Teorema: n elementni k tadan o’rinlashtirishlar soni
A^k_n = n (n-1) (n-2)…n- (k-1) ga teng.
Isbot. a, b, c, d…f n ta elementni 2 tadan o’rinlash tuzaylik.


ab, ac, ad…af
ba, bc, bd…bf
ca, cb, cd…cf
da, db,dc…df
……………..
fa, fb, fc…fd
n-1 gruppa
Demak, A¹_n = n, A²_n =n (n-1)
n elementni 2 tadan o’rinlashtirish soni. Shu n ta elementni 3 tadan o’rinlashtiraylik.