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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

اثبات[ویرایش]

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

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۱، ...، An این کار را بکنیم. فرض کنیم x دقیقن به mتا از مجموعه‌ها تعلق دارد (۱ ≤ m ≤ n). برای سادگی این مجموعه‌ها را A۱، ...، Am در نظر می‌گیریم. پس مشخصه در 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 متعلق به Am باشد، پرانتز mام صفر می‌شود (۱ - ۱ = ۰). با بسط ضرب در سمت راست به معادلهٔ (*) می‌رسیم.

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

بیان قضیه[ویرایش]

فرض میکنیم 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