Mavzu: Kombinatorikada ko’p qo’llaniladigan usul va amallar 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
. ■