Kombinatorika va uning asosiy qoidalari

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

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

m( yoki ) = m() + m( ) = 10+8 = 18

usulda tanlash mumkin.

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

m( vа ) = m( ) · m( )

formula bilan topiladi.

Masalan, qurilishda 10 suvoqchi va 8 buyoqchi ishlasa, ulardan bir suvoqchi va bir buyoqchidan iborat juftlikni m( vа )=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:  I yo‘llanmani,  esa II yo‘llanmani tarqatishni ifodalasin. Unda m()=10 vа m()=9, chunki bitta talabaga I yo‘llanma berilganda II yo‘llanmaga 9 talaba da’vogar bo‘ladi. Demak, ikkita yo‘llanmani tarqatishlar soni m( vа ) = =109=90 bo‘ladi.

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

m(₁ yoki ₂ yoki….yoki _n ) = m(₁)+ m( ₂ )+…+m(_n), (1)

m(₁ vа ₂ vа…. vа _n ) = m(₁)  m( ₂ ) … m(_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.