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

5-teorema (umumlashgan kiritish va chiqarish qoidasi). Ixtiyoriy chekli to‘plamlar uchun



.
munosabat o‘rinlidir.
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 3-teoremaga asosan to‘g‘ri.
Induksion o‘tish: teoremaning tasdig‘i uchun to‘g‘ri, ya’ni




tenglik o‘rinli bo‘lsin. Tasdiqning bo‘lgan holda to‘g‘ri ekanligini ko‘rsatamiz. Avvalo, to‘plamlarning birlashmasini ko‘rinishda ifodalaymiz. So‘ngra 3-teoremani va kesishmaga nisbatan umumlashgan distributivlik qonunini qo‘llab hamda teorema tasdig‘ining uchun to‘g‘riligini hisobga olib, quyidagilarga ega bo‘lamiz:




.
Bu ifodadagi oxirgi ayriluvchi ( ) ko‘rinishdagi ta to‘plamlar birlashmasining quvvatini ifodalaydi. Shuning uchun, induksiya faraziga ko‘ra, bu ayriluvchini quyidagicha yozish mumkin:











.
Bu ifodani o‘z o‘rniga qo‘yib




tenglikni hosil qilamiz.
6-teorema (umumlashgan qo‘shish qoidasi). Juft-jufti bilan kesishmaydigan ixtiyoriy chekli to‘plamlar uchun

tenglik o‘rinlidir.
Isboti. Teorema shartiga ko‘ra barcha , , indekslar uchun bo‘lgani sababli 5-teorema asosida kerakli tenglikni hosil qilamiz.