22-Ma’ruza. Kombinatorikaning umumiy tushunchalari, usullari va qoidalari. Asosiy kombinasiyalar reja

Mustaqil ishlash uchun savollar

1. 
   Kombinatorika predmeti nima?
   
2. 
   Kombinatorika sohasida ilmiy tadqiqotlar olib borgan qaysi olimlarni bilasiz?
   
3. 
   Kombinatorika matematikaning alohida ilmiy yo‘nalishi sifatida qachon shakllandi?
   
4. 
   Figurali sonlar deganda nimani tushunasiz?
   
5. 
   “Kombinatorika” iborasi kim tomonidan qachon kiritilgan?
   
6. 
   Matematik induksiya usulidan foydalanib tasdiq qanday isbotlanadi?
   
7. 
   Qo‘shish va ko‘paytirish qoidalari qanday ifodalanadi?
   

Umumlashgan qo‘shish va ko‘paytirish qoidalarini bilasizmi?

23-Ma’ruza. O’RINLASHTIRISH, O’RIN ALMASHTIRISHLAR. GRUPPALASHLAR
Reja:
1. O‘rin almashtirishlar.
2. O‘rinlashtirishlar.
3. Gruppalashlar.


1. O‘rin almashtirishlar. Elementlari bo‘lgan to‘plamni qaraymiz. Bu to‘plam elementlarini har xil tartibda joylashtirib (yozib), tuzilmalar (kombinatsiyalar) hosil qilish mumkin, masalan,
; ; .
Bu tuzilmalarning har birida berilgan to‘plamning barcha elementlari ishtirok etgan holda ular bir-biridan faqat elementlarning joylashish o‘rinlari bilan farq qiladilar. Shu usul yordamida hosil qilingan kombinatsiyalarning har biri berilgan to‘plam elementlarining o‘rin almashtirishi deb ataladi.
Aslida “o‘rin almashtirish” iborasi to‘plam elementlarining o‘rinlarini o‘zgartirish harakatini anglatsada, bu yerda uni shu harakat natijasidagi hosil bo‘lgan tuzilma sifatida qo‘llaymiz. Bu iboradan uning asl ma’nosida ham foydalanamiz.
O‘rin almashtirishni ifodalashda uning elementlarini ajratuvchi belgi sifatida yuqorida “,” (vergul) belgisidan foydalanildi. Ammo bu muhim emas, bu yerda boshqa belgidan ham foydalanish, hattoki, yozuvning ixchamligi maqsadida, elementlar orasidagi ajratuvchi belgilarni tushirib qoldirilish ham mumkin. Bu eslatma bundan keyin bayon etiladigan boshqa kombinatorik tuzilmalar uchun ham o‘rinlidir.
To‘plam tushunchasiga asoslanib, bu yerda qaralayotgan o‘rin almashtirishlar tarkibida elementlarning takrorlanmasligini eslatib o‘tamiz. Shu sababli bunday o‘rin almashtirishlarni betakror (takrorli emas) o‘rin almashtirishlar deb ham atash mumkin. Ushbu bobning 4-paragrafida takrorli o‘rin almashtirishlar ko‘riladi.
Berilgan ta elementli to‘plam uchun barcha o‘rin almashtirishlar sonini bilan belgilash qabul qilingan⁸.
Bitta elementli to‘plam uchun faqat bitta ko‘rinishdagi o‘rin almashtirish borligi ravshandir: .
Ikkita elementli to‘plam elementlaridan o‘rin almashtirishlarni bitta elementli to‘plam uchun o‘rin almashtirishidan foydalanib quyidagicha tashkil qilamiz: element elementdan keyin yozilsa o‘rin almashtirishga, oldin yozilsa esa o‘rin almashtirishga ega bo‘lamiz. Demak, ko‘paytirish qoidasiga (ushbu bobning 1-paragrafiga qarang) binoan ikkita o‘rin almashtirish bor: .
Uchta elementli to‘plam uchun o‘rin almashtirishlar tashkil qilishda ikkita elementli to‘plam uchun tuzilgan va o‘rin almashtirishlardan foydalanish mumkin. Berilgan to‘plamning elementini va o‘rin almashtirishning har biriga uch xil usul bilan joylashtirish mumkin: ularning elementlaridan keyin, elementlarining orasiga va elementlaridan oldin. Ko‘paytirish qoidasini qo‘llasak, uchta elementli to‘plam uchun oltita ( ) har xil o‘rin almashtirishlar hosil bo‘lishini aniqlaymiz. Ular quyidagilardir:
.
To‘rtta elementli to‘plamni qarab, uchta elementli to‘plam uchun tuzilgan oltita o‘rin almashtirishlarning har biriga elementni to‘rt xil usul bilan joylashtirish imkoniyati borligini e’tiborga olsak, ko‘paytirish qoidasiga ko‘ra, bo‘lishini topamiz. Bu yerda barcha o‘rin almashtirishlar quyidagilardir:
,
,
,
,
,
.
Shu tarzda davom etib “ ta elementli to‘plam uchun barcha o‘rin almashtirishlar soni birdan gacha bo‘lgan barcha natural sonlarning ko‘paytmasiga teng” deb faraz qilish mumkin: . Bu farazning to‘g‘riligi quyidagi 1-teoremada isbot qilinadi.
Dastlabki ta natural sonlar ko‘paytmasini ko‘rinishida⁹ belgilash qabul qilingan, ya’ni . belgisidan bunday ma’noda birinchi bo‘lib K. Kramp¹⁰ 1808 yilda nashr etilgan algebra bo‘yicha qo‘llanmada foydalangan.
ifodada bo‘lganda faqat 1 soni ishtirok etadi, shuning uchun, ta’rif sifatida deb hisoblash qabul qilingan. Bundan tashqari, bo‘lganda esa ifoda umuman ma’nosini yo‘qotadi. Lekin, ta’rif sifatida deb qabul qilinadi.