Kombinatorikaning asosiy qoidalari

Kombinatorikaning asosiy qoidalari Qo'shish qoidasiga ko'ra, A yoki Вto'plamga tegishli bo'ladigan birorta elemental tanlash imkoniyatlari soni (m+«)ga tengdir. «Yoki» qoidasi deb ham ataluvchi bu qoida mazmunini quyidagi teorema orqali ham ifodalash mumkin. 1-teorema. Agar ixtiyoriy chekli A va Вto'plamlar uchun Af]B = 0 bo'lsa, иholda AJ В = A + В bo'ladi. Isboti o'quvchiga havola qilinadi. ■ Demak, qo'shish qoidasiga ko'ra, kesishmaydigan ikkita to'plam birlashmasining quvvati shu to'plamlar quwatlarining yig'indisiga tengdir. Ko'paytirish qoidasiga asosan, m ta elementli A va n ta elementli В to'plamlarning elementlaridan tuzish mumkin bo'lgan barcha (aeA, b^B) kortejlar (juftliklar) soni mnga teng. Bu qoida «va» qoidasi deb ham ataladi. Uni quyidagi teorema ko'rinishida ifodalash ham mumkin. 2-teorema. Ixtiyoriy chekli A va В to 'plamlar uchun |у4х!?|=|у4| |jB| tenglik о 'rinlidir. Isboti o'quvchiga havola qilinadi. ■ Demak, ko'paytirish qoidasiga ko'ra, ixtiyoriy ikkita chekli to'plam Dekart ko'paytmasining quvvati shu to'plamlar quwatlarining ko'paytmasiga tengdir. Umurniy holda, agar chekli A va В to'plamlar hech bo'lma-ganda bitta umurniy elementga ega bo'lsa, u holda И+I^l yig'indining qiymatini aniqlashda^ U В to'plamning ba'zi elementlarini, aniq-rog'i, А П В to'plamning elementlarini ikki marta hisobga olishga to'g'ri keladi. Bu mulohaza asosida quyidagi tasdiqqa kelamiz. 3-teorema. Ixtiyoriy chekli A va В to'plamlar uchun А[ВЦА+ В-АВtenglikо 'rinlidir. Isboti.Osonlik bilan ko'rish mumkinki: a) A U В = A U (В A) vaАП(В A) = 0; b) В = (А П B) U(В A) va(А П В) П B A) = 0. Bu munosabatlarga 2-teoremani qo'llasak, mos ravishda, AJBHA+ BAvaB^Af)B + BAtengliklarni hosil qilamiz.Bu tengliklardan isbotlanishi kerak bo'lgan tenglikni hosil qilish qiyin emas.■ 3-teoremaning tasdig'ini umurniy holda ikkita chekli to'plamlar birlashmasining quwatini hisoblash qoidasi deyish mumkin. Bu qoidaning ma'nosidan kelib chiqqan holda, uni kiritish va chiqarish qoidasi, deb atash qabul qilingan. Ravshanki, 3-teoremada keltirilgan tenglikdan foydalanib |A|, |B|, | A U В | va | А П В | miqdorlarning ixtiyoriy uchtasi malum bo'lganda to'rtinchisini hisoblash formulasini hosil qilish mumkin. Yuqorida bayon qilingan ikkita to'plam uchun qo'shish, ko'paytirish hamda kiritish va chiqarish qoidalarini chekli sondagi istalgan chekli to'plamlar uchun umumlashtirish mumkin. Awalo, kiritish va chiqarish qoidasining umumlashmasi sifatida quyidagi teoremani keltiramiz: ...