§. Natural va butun sonlar

24- §. Kombinatorika.
Kombinatorika- diskret matematikaning bir bo’limi bo’lib, asosan chekli to’plamlar ustida ish ko’radi. Kombinatorikada sodda, ammo muhim bo’lgan qoidalar bor. Bunday qoidalar sifatida qo’shish, ko’paytirish qoidalari mavjud.
m ta elementli A to’plam va n ta elementli B to’plamlar berilgan bo’lib, ular kesishmasin. Qo’shish qoidasiga ko’ra, A yoki B to’plamga tegishli bo’ladigan birorta elementni tanlash imkoniyatlari soni (m+n) ga tengdir.
Ko’paytirish qoidasiga asosan, m ta elementli A va n ta elementli B to’plamlarning elementlaridan tuzish mumkin bo’lgan barcha (a , b ) juftliklar soni mn ga teng.
Misol: A =10 (har xil ruchka ), B =5 (har xil daftar).
Bu to’plamlardagi elementlarning faqat birini tanlasak, unda tanlashlar soni qo’shish qoidasiga asosan 15 ta bo’ladi.
Agar A va B to’plam elementlaridan juft-juft qilib tanlasak, tanlashlar soni ko’paytirish qoidasiga asosan 50 ta bo’ladi.
Kombinatorika berilishiga ko’ra takrorlanadigan va takrorlanmaydigan:
1) o’rin almashtirish;
2)o’rinlashtirish;
3)gruppalash turlariga ajraladi
1) O’rin almashtirishlar. Elementlari a₁, a₂, a₃,……, a_n bo’lgan to’plamni qaraymiz. Bu to’plam elementlarini har xil tartibda joylashtirib (yozib), tuzilmalar (kombinatsiyalar) hosil qilish mumkin, masalan,
(a₁,a₂,a₃,……,a_n); ( a₁,a₂,a₃,……,a_n); (a₃,a₂,a₁,……,a_n)………
Bu tuzilmalarning har birida berilgan to’plamning barcha elementlari ishtirok etgan holda ular bir-biridan faqat elementlarining joylashish o’rinlari bilan farq qiladi. Shu usul yordamida hosil qilingan kombinatsiyalarning har biri berilgan (a₁,a₂,a₃,……,a_n) to’plam elementlarining o’rin almashtirishi deb ataladi.
1-teorema. Elementlari soni n ta bo’lgan to’plam uchun o’rin almashtirishlar soni n! ga teng, ya’ni P_n =n!
Misol: Kitob javonidagi 10 ta har xil kitobni necha xil usul bilan joylashtirish mumkin?
Birinchi o’rinda turgan kitob o’rniga kitob qo’yish uchun bizga 10 xil variant mavjud, ikkinchi kitob o’rniga turgan kitob qo’yish uchun bizga 9 xil variant mavjud. Shu usulda davom ettirsak jami joylashtirishlar usuli P₁₀ =10! Ga teng bo’ladi.