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

1-teorema. Ixtiyoriy chekli to‘plam uchun tenglik o‘rinlidir.
Isboti. Matematik induksiya usulini berilgan to‘plamning quvvati bo‘yicha qo‘llaymiz.
Baza. Dastlab to‘plamning elementlari soni nolga teng, ya’ni bo‘lganda teoremaning tasdig‘i bajarilishini ko‘rsatamiz. bo‘lsin. U holda uchun , va bo‘ladi. Demak, teoremaning tasdig‘i bo‘lgan hol uchun to‘g‘ridir.
Induksion o‘tish. Chekli elementli ixtiyoriy to‘plam uchun teoremaning tasdig‘i to‘g‘ri bo‘lsin, ya’ni bo‘lganda tenglik bajarilsin. elementli to‘plamni qaraymiz. Ravshanki, uchun bo‘ladi. Qaralayotgan to‘plamning ixtiyoriy elementi uchun bulean to‘plamni o‘zaro kesishmaydigan ikkita va to‘plamlar birlashmasi sifatida yozish mumkin. Demak, .
Tuzilishiga ko‘ra, to‘plam elementli to‘plamning buleanidan iborat. Shuning uchun, induksion o‘tish faraziga ko‘ra bo‘ladi. to‘plam esa to‘plamning har bir element-to‘plamiga elementni kiritish yordamida hosil qilingan. Bundan kelib chiqadi. Demak, bo‘lgan hol uchun
.
Ushbu bobning 3-paragrafida 1-teoremaning kombinatorik tushunchalarga asoslangan boshqa isboti keltiriladi.
Berilgan chekli to‘plamning buleani uning barcha qism to‘lamlaridan tuzilgan toplam bo‘lgani sababli 1-teoremada isbotlangan tenglik to‘plamning buleanini ko‘rinishda belgilashga asos bo‘la oladi.
Kombinatorikada sodda, o‘z-o‘zidan ravshan bo‘lgan, ammo muhim qoidalar bor. Bunday qoidalar sifatida qo‘shish, ko‘paytirish hamda kiritish va chiqarish qoidalari deb ataluvchi qoidalarni ko‘rsatish mumkin.
ta elementli to‘plam va ta elementli to‘plamlar berilgan bo‘lib, ular kesishmasin. Qo‘shish qoidasiga ko‘ra, yoki to‘plamga tegishli bo‘ladigan birorta elementni tanlash imkoniyatlari soni ( )ga tengdir. “Yoki” qoidasi deb ham ataluvchi bu qoida mazmunini quyidagi teorema orqali ham ifodalash mumkin.