اصل شمول و عدم شمول

در ترکیبیات اصل شمول و عدم شمول بیان می‌کند اگر A و B دو مجموعه متناهی (۲=n) باشند، آنگاه

$|A \cup B| = |A| + |B| - |A \cap B| \,$

اصل شمول و عدم شمول یک قضیه (قابل اثبات) است، اما به علت سادگی، به عنوان یک اصل بیان می‌شود.

اثبات

A را اجتماع $\scriptstyle \cup_{i=1}^n A_i$ از مجموعه‌های A_۱، ...، A_n در نظر می‌گیریم. برای اثبات اصل شمول و عدم شمول در حالت عام، اول باید مشخصات

$1_A =\sum_{k=1}^n (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,n\}\atop\scriptstyle|I|=k} 1_{A_I}\qquad(*)$

را برای توابع مشخصه به صورت

$A_I = \bigcap_{i\in I} A_i$

بررسی کنیم. حداقل دو راه برای این کار هست

راه اول: کافی است برای هر x در اجتماع A_۱، ...، A_n این کار را بکنیم. فرض کنیم x دقیقن به mتا از مجموعه‌ها تعلق دارد (۱ ≤ m ≤ n). برای سادگی این مجموعه‌ها را A_۱، ...، A_m در نظر می‌گیریم. پس مشخصه در x به

$1 =\sum_{k=1}^m (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,m\}\atop\scriptstyle|I|=k} 1$

کاهش می‌یابد.

تعداد زیرمجموعه‌های kعضوی از مجموعه mعضوی برابر با $\textstyle\binom mk$  است. چون $\textstyle1=\binom m0$ ٬

$\binom m0 =\sum_{k=1}^m (-1)^{k-1}\binom mk$

با قرار دادن همهٔ جملات در سمت چپ معادله، بسط (۱ – ۱)^m را با استفاده از بسط دو جمله‌ای به دست می‌آوریم. بنابراین (*) برای x صادق است.

راه دوم: تابع زیر همیشه صفر است

$(1_A-1_{A_1})(1_A-1_{A_2})\cdots(1_A-1_{A_n})\,=\,0\,$

زیرا: اگز x در A نباشد، آنگاه تمام پرانتزها صفر می‌شوند (۰ - ۰ = ۰). در غبر این صورت، اگر x متعلق به A_m باشد، پرانتز mام صفر می‌شود (۱ - ۱ = ۰). با بسط ضرب در سمت راست به معادلهٔ (*) می‌رسیم.

استفاده از (*): برای اثبات اصل شمول و عدم شمول برای اندازهٔ مجموعه‌ها، معادلهٔ (*) را برای تمام xها در اجتماع A_۱، ...، A_n جمع می‌کنیم.

بیان قضیه

فرض میکنیم S مجموعه ای از اعداد باشد و همچنین فرض میکنیم $C1 , C2 , ... , Cm$ مجموعه ای از ویژگی هایی باشند که برخی از عناصر S و یا همه آنها در این شرایط صدق کنند.

( N(Ci۱ ، Ci۲ ، ... ، Cij را تعداد عناصری از S تعریف میکنیم که در شرط‌های Cij ، ... ، Ci۲ ، Ci۱ صدق می‌کنند.

( N(!Ci۱ ، !Ci۲ ، ... ، !Cij را تعداد عناصری از S تعریف میکنیم که در هیچ یک از شرط‌های Cij ، ... ، Ci۲ ، Ci۱ صدق نمی‌کنند.

( N(!C۱ ، !C۲ ، .. ، !Cm ) = N - ∑ N(C(i۱ )) + ∑ N(C(i۱ ) ، C(i۲ ) ) - ∑ N(C(i۱ )،C(i۲ )،C(i۳ ) ) + ⋯ + (-۱)^t N(C۱،C۲،C۳…،Ct

یک مثال

مثال)فرض کنید { S = { ۱،۲، … ، ۱۰۰، چند عضو از S وجود دارد که بر ۲و۵ بخش نباشد؟

حل) تعداد اعدادی که مضرب ۲ هستند = ۵۰

تعداد اعدادی که مضرب ۵ هستند = ۲۰

تعداد اعدادی که مضرب ۲،۵ هستند = ۱۰

جواب = ۱۰ + ۲۰ - ۵۰ - ۱۰۰ = ۴۰

منابع

کتاب ترکیبات انتشارات فاطمی، علیرضا علیپور

برای اطلاعات بیشتر

http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=اصل+شمول+و+طرد&SSOReturnPage=Check&Rand=0