Kombinatorika elementlari. O‘rinlashtirishlar va o‘rin almashtirishlar

Ko’paytma qoidasi. Chekli to’plamlarning dekart ko’paytmasi elementlari sonini topishga imkon beradigan qoida ko’paytma qoidasi deyiladi. A = {a1, a2, …, an} va B = {b1,b2, …, bm} to’plamlar elementlaridan nechta tartiblangan (ai, bj.) juftlik tuzish mumkinligini ko’raylik. Barcha juftliklarni tartib bilan quyidagicha joylashtiramiz:
 (a1; b1), (a1; b2), … , (a1; bm), (a2; b1), (a2; b2), … , (a2; bm), (an; b1), (an; b2), … , (an; bm).
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.
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.
Savollar

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