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

7-teorema. Ixtiyoriy chekli to‘plamlar uchun



.
munosabat o‘rinlidir.
Isboti o‘quvchiga havola qilinadi.
8-teorema (umumlashgan ko‘paytirish qoidasi). Elementlari soni mos ravishda bo‘lgan to‘plamlardan faqat bittadan element olib tuzilgan uzunlikka ega kortejlar soni ga tengdir.
Isboti. Teoremani isbotlash uchun matematik induksiya usulini qo‘llaymiz. bo‘lgan hol uchun teoremaning tasdig‘i trivialdir.
Induksiya usulining bazasi sifatida bo‘lgan holni qaraymiz. Bu holda teoremaning tasdig‘i yuqorida keltirilgan ikkita to‘plam uchun ko‘paytirish qoidasidan kelib chiqadi.
Induksion o‘tish: teoremaning tasdig‘i ( ) uchun to‘g‘ri bo‘lsin, ya’ni, to‘plamlardan faqat bittadan element olib tuzilgan uzunlikdagi kortejlar soni bo‘lsin deb faraz qilamiz. Teorema tasdig‘ining uchun ham to‘g‘ri ekanligini ko‘rsatamiz.
to‘plamlardan faqat bittadan element olib uzunligi ( )ga teng bo‘lgan kortejlar sonini aniqlash uchun turlicha usullardan foydalanish mumkin. Bu yerda quyidagi usul bilan kerakli natijani olsa bo‘ladi. Dastlab uzunligi birga teng bo‘lgan kortejlarni tuzamiz. Uzunligi birga teng bo‘lgan kortejlar berilgan to‘plamlarning ixtiyoriy biridan faqat bitta elementni tanlash yordamida tuzilishi ravshan. Tabiiyki, agar uzunligi birga teng kortejlar to‘plamning elementlaridan tuzilsa, bunday kortejlar soni ga tengdir.
Uzunligi birga teng kortejlardan ixtiyoriy birini, masalan, ni olib, uning o‘ng tomoniga to‘plamdan boshqa biror to‘plamning, masalan, to‘plamning elementlaridan birini joylashtirib, birinchi koordinatasi bo‘lgan uzunligi ikkiga teng ta kortejlar hosil qilamiz. Uzunligi birga teng kortej sifatida ta kortejlardan ixtiyoriy birini olish mumkinligini hisobga olib, hammasi bo‘lib uzunligi ikkiga teng ta kortejlarga ega bo‘lamiz.
Uzunligi ikkiga teng kortejlarning har biriga o‘ng tomondan va to‘plamlardan boshqa biror to‘plamning, masalan, to‘plamning ta elementlaridan birini joylashtirib, uzunligi uchga teng ta kortejlar hosil qilamiz. Bu yerda uzunligi ikkiga teng kortej sifatida ta kortejlardan ixtiyoriy birini olish mumkinligini e’tiborga olib, uzunligi uchga teng ta kortejlarni hosil qilamiz.
Kortejlar hosil qilish jarayonini yuqoridagiga o‘xshash mulohazalar bilan davom ettirib, bu kortejlarning har biriga o‘ng tomondan to‘plamlardan boshqa to‘plamning ta elementlaridan birini joylashtirib, uzunligi ga teng bo‘lgan ta kortejlar hosil qilamiz. Bu yerda ham uzunligi ga teng kortej sifatida ta kortejlardan ixtiyoriy birini olish mumkinligini e’tiborga olamiz. Shunday qilib, marta ta kortej hosil bo‘ldi. Demak, uzunligi ga teng bo‘lgan kortejlar tadir.