1-Mavzu: Kombinatorika haqida umumiy tushunchalar

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. ■