اصل شمول و عدم شمول - ویکی‌پدیا، دانشنامهٔ آزاد

در ترکیبیات اصل شمول و عدم شمول یک تکنیک شمارش است که روش معمول شمارش اعضای اجتماع دو مجموعه متناهی -که به صورت زیر است- را بسط می‌دهد.

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|,}$

که A و B دو مجموعهٔ متناهی اند و |S| نمایانگر تعداد اعضای مجموعهٔ متناهی S است. این فرمول بیان می‌کند که مجموع اندازهٔ دو مجموعه ممکن است بزرگتر از اندازهٔ اجتماع آن‌ها باشد چون بعضی از اعضا شاید دو بار شمرده شوند. اعضایی که دو بار شمرده شده‌اند همان اعضایی اند که در اشتراک دو مجموعه حضور دارند بنابراین با کم کردن این تعداد، اندازهٔ واقعی مجموعهٔ اجتماع بدست می‌آید. این اصل در حالتی که سه مجموعه داریم واضح‌تر دیده می‌شود:

${\displaystyle |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.}$

این فرمول می‌تواند به این صورت امتحان شود که بشماریم هر ناحیه در نمودار ون چند بار در سمت راست فرمول شمرده شده‌است.

بسط نتایج این مثال‌ها اصل شمول و عدم شمول را بدست می‌دهد: برای یافتن اندازهٔ اجتماع n مجموعه،

1. اندازهٔ هر مجموعه را اضافه کنید،
2. اندازهٔ اشتراک دو به دو مجموعه‌ها را کم کنید،
3. اندازهٔ اشتراک هر سه‌تایی از مجموعه‌ها را اضافه کنید،
4. اندازهٔ اشتراک هر چهارتایی از مجموعه‌ها را کم کنید،
5. اندازهٔ اشتراک هر پنج‌تایی از مجموعه‌ها را اضافه کنید،
6. به همین صورت ادامه دهید تا زمانی که اندازهٔ اشتراک nتایی مجموعه‌ها اضافه (برای n فرد) یا کم (برای n زوج) شود.

این اسم از اینجا آمده که این اصل براساس یک سری شمول و عدم شمول استوار است. این مفهوم به ابراهام دو مواور (۱۷۱۸) نسبت داده می‌شود، ولی بار اول در مقاله‌ای از دنیل داسیلوا (۱۸۵۴) و بعداً در مقاله‌ای از جیمز جوزف سیلوستر (۱۸۸۳) ظاهر شد. به همین دلیل گاهی این اصل به عنوان فرمول داسیلوا یا سیلوستر شناخته می‌شود.

از آنجایی که احتمالات متناهی براساس اندازهٔ فضای احتمال محاسبه می‌شوند، زمانی که اندازهٔ مجموعه‌ها با احتمالات متناهی جایگزین می‌شوند، فرمول‌های اصل شمول و عدم شمول همچنان برقرار خواهد بود. به‌صورت کلی‌تر، هر دو نسخه از این اصل را می‌توان در چتر بزرگتر نظریه‌ی اندازه‌گیری جای داد.

در یک نگاه کاملاً انتزاعی، اصل شمول چیزی فراتر از محاسبهٔ معکوس یک ماتریس نیست. از این دیدگاه از لحاظ ریاضیاتی هیچ چیز جالبی در مورد این اصل وجود ندارد. با وجود این استفاده‌پذیری گستردهٔ این اصل باعث می‌شود که این اصل به ابزاری بسیار ارزشمند در ترکیبیات و رشته‌های مرتبط با آن بدل شود. آنطور که جیان کارلو روتا گفته‌است:

"یکی از پراستفاده‌ترین اصول در شمارش و احتمالات گسسته و ترکیبیات، اصل شمول و عدم شمول است. زمانی که این اصل با مهارت کافی استفاده شود می‌تواند پاسخ بسیاری از مسائل ترکیبیاتی را بدست آورد."

بیان[ویرایش]

در حالت کلی، این اصل بیان می‌کند که برای مجموعه‌های متناهی A_n،... ،A_۱، اتحاد زیر برقرار است:

${\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{i=1}^{n}\left|A_{i}\right|\;-\sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\;+\sum _{1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|\;-\ \ldots \ +\;\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.}$

به صورت فشرده‌تر می‌توان اینطور نوشت:

${\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leq i_{1}<\cdots <i_{k}\leq n}\left|A_{i_{1}}\cap \cdots \cap A_{i_{k}}\right|\right).}$

به صورت گفتاری، برای شمردن تعداد اعضای اجتماع تعدادی متناهی از مجموعه‌های متناهی، ابتدا مجموع اندازهٔ مجموعه‌ها را بدست می‌آوریم، سپس تعداد اعضایی که در بیشتر از یک مجموعه ظاهر شده‌اند را از آن کم می‌کنیم، سپس تعداد اعضایی را که در بیش از دو مجموعه ظاهر شده‌اند را اضافه می‌کنیم، سپس تعداد اعضایی را که در بیش از سه مجموعه تکرار شده‌اند را کم می‌کنیم و به همین صورت تا آخر. این روند به صورت طبیعی به پایان می‌رسد، چون هیچ عضوی وجود ندارد که در بیشتر از تعداد کل مجموعه‌ها آمده باشد.

در کاربرد معمول است که این اصل را به صورت فرم مکملش بیان کنند. به این صورت که فرض کنید S مجموعه‌ی مرجع باشد که تمام مجموعه‌های A_i را شامل می‌شود و همچنین فرض کنید که ${\displaystyle {\bar {A_{i}}}}$ بیانگر مکمل A_i باشد. براساس قوانین دومورگان داریم:

${\displaystyle {\biggl |}\bigcap _{i=1}^{n}{\bar {A_{i}}}{\biggr |}={\biggl |}S-\bigcup _{i=1}^{n}A_{i}{\biggr |}=\left|S\right|\;-\sum _{i=1}^{n}\left|A_{i}\right|\;+\sum _{1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\;-\;\ldots \ +\;\left(-1\right)^{n}\left|A_{1}\cap \cdots \cap A_{n}\right|.}$

به عنوان یک بیان دیگر، فرض کنید P_n، …، P_۲، P_۱ لیستی از خصوصیاتی باشد که اعضای مجموعهٔ S ممکن است داشته یا نداشته باشند، در این صورت اصل شمول و عدم شمول راهی برای محاسبهٔ تعداد اعضایی که هیچ‌یک از این خصوصیات را ندارند در اختیار قرار می‌دهد. فقط کافی است مجموعهٔ A_i را مجموعهٔ اعضایی که خصوصیت P_i را دارند قرار دهید و از فرم مکمل این اصل استفاده کنید.

مثال‌ها[ویرایش]

به عنوان یک مثال ساده از استفادهٔ این اصل پرسش زیر را در نظر بگیرید:

چه تعداد عدد طبیعی در {۱، …، ۱۰۰} بر هیچ‌یک از اعداد ۲، ۳ و ۵ تقسیم‌پذیر نیستند؟

فرض کنید S مجموعهٔ اعداد طبیعی ۱ تا ۱۰۰ باشد و P_۱ این خصوصیت که یک عدد بر ۲ بخش‌پذیر است و P_۲ این خصوصیت که یک عدد بر ۳ بخش‌پذیر است و P_۳ این خصوصیت که یک عدد بر ۵ بخش‌پذیر است باشد. فرض کنید A_i مجموعهٔ اعدادی از S است که خصوصیت P_i را دارند. داریم ${\displaystyle |A_{1}|=50}$، ${\displaystyle |A_{2}|=33}$ و ${\displaystyle |A_{3}|=20}$. ۱۶ تا از این اعداد بر ۶ بخشپذیرند، ۱۰تایشان بر ۱۰ و ۶تایشان بر ۱۵. در نهایت فقط ۳تا از اعداد بر ۳۰ بخش‌پذیرند، بنابراین تعداد اعدادی که بر هیچ‌یک از ۲ یا ۳ یا ۵ بخش‌پذیر نیستند برابر است با:

یک مثال پیچیده‌تر مورد زیر است:

فرض کنید n کارت داریم، هر کارت شماره‌ای از ۱ تا n دارد فرض کنید کارت با شمارهٔ m در جای درست قرار دارد اگر mامین کارت باشد. به چند طریق می‌توان کارت‌ها را بُر زد به طوری که حداقل یک کارت در جای درستش قرار داشته باشد؟

A_m را مجموعه‌ای از جایگشت بگیرید که کارت با شمارهٔ m در جای درستش قرار دارد. در این صورت تعداد جایگشت‌های مورد نظر (W) برابر است با:

${\displaystyle W={\biggl |}\bigcup _{m=1}^{n}A_{m}{\biggr |}.}$

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

${\displaystyle W=\sum _{m_{1}=1}^{n}\left|A_{m_{1}}\right|{}-\sum _{1\leq m_{1}<m_{2}\leq n}\left|A_{m_{1}}\cap A_{m_{2}}\right|{}+\sum _{1\leq m_{1}<m_{2}<m_{3}\leq n}\left|A_{m_{1}}\cap A_{m_{2}}\cap A_{m_{3}}\right|{}-\cdots {}+(-1)^{p-1}\sum _{1\leq m_{1}<\cdots <m_{p}\leq n}\left|A_{m_{1}}\cap \cdots \cap A_{m_{p}}\right|\cdots .}$

هر مقدار ${\displaystyle A_{m_{1}}\cap \cdots \cap A_{m_{p}}}$ بیانگر مجموعهٔ جایگشت‌هایی است که در آن‌ها p کارت m_p، …، m_۱ در جای درست قرار دارند. توجه کنید که تعداد جایگشت‌های با p مقدار درست تنها به p بستگی دارد نه به مقادیر ${\displaystyle m}$. به عنوان مثال، تعداد جایگشت‌هایی که اولین و سومین و ۱۷امین کارت در جای درست قرار دارند برابر با تعداد جایگشت‌هایی است که ۲امین و ۵امین و ۱۳امین کارت در جای درست قرار دارند. تنها این مهم است که از n کارت ۳ کارت انتخاب شده که در جای درست قرار گیرد. چون به تعداد ${\displaystyle {n \choose p}}$ مورد در هر مجموع وجود دارد، داریم:

${\displaystyle W={n \choose 1}\left|A_{1}\right|-{n \choose 2}\left|A_{1}\cap A_{2}\right|+{n \choose 3}\left|A_{1}\cap A_{2}\cap A_{3}\right|-\cdots +(-1)^{p-1}{n \choose p}\left|A_{1}\cap \cdots \cap A_{p}\right|\cdots .}$

${\displaystyle \left|A_{1}\cap \cdots \cap A_{p}\right|}$ تعداد جایگشت‌هایی است که p عنصر دارند که در جای درست قرار گرفته‌اند که برابر است با ${\displaystyle (n-p)!}$. بنابراین در نهایت داریم:

${\displaystyle W={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+{n \choose 3}(n-3)!-\cdots +(-1)^{p-1}{n \choose p}(n-p)!\cdots W=\sum _{p=1}^{n}(-1)^{p-1}{n \choose p}(n-p)!.}$

با توجه به اینکه ${\displaystyle {n \choose p}={\frac {n!}{p!(n-p)!}}}$ بدست می‌آید:

${\displaystyle W=\sum _{p=1}^{n}(-1)^{p-1}\,{\frac {n!}{p!}}.}$

یک جایگشت که در آن هیچ عنصری سر جایش نیست یک پریش نامیده می‌شود. وقتی ${\displaystyle n!}$ تعداد کل جایگشت‌ها است، احتمال (Q) این که یک جایگشت تصادفی یک پریش باشد برابر است با:

${\displaystyle Q=1-{\frac {W}{n!}}=\sum _{p=0}^{n}{\frac {(-1)^{p}}{p!}},}$

یک مورد خاص[ویرایش]

این وضعیت که در مورد مثال پریش اتفاق می‌افتد به اندازه‌ای تکرار می‌شود که شایستهٔ توجه ویژه باشد. منظور زمانی است که اندازهٔ مجموعهٔ اشتراکی ظاهر شده در فرمول اصل شمول و عدم شمول فقط به تعداد مجموعه‌ها بستگی دارد نه به خود مجموعه‌ها. به بیانی رسمی، زمانی که اشتراک

${\displaystyle A_{J}:=\bigcap _{j\in J}A_{j}}$

اندازه‌ای برابر با ${\displaystyle |A_{J}|=\alpha _{k}}$ داشته باشد، برای هر زیرمجموعهٔ kعضوی از اعداد ۱ تا n. داریم:

${\displaystyle {\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.}$

یا در فرم مکمل زمانی که مجموعهٔ مرجع S دارای اندازهٔ α₀ است،

${\displaystyle {\biggl |}S-\bigcup _{i=1}^{n}A_{i}{\biggr |}=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}\alpha _{k}.}$

یک تعمیم[ویرایش]

یک خانواده از زیرمجموعه‌های A_n، …، A₂، A_۱ از مجموعهٔ مرجع S را در نظر بگیرید. اصل شمول و عدم شمول تعداد عناصری از S را که در هیچ‌یک از این زیرمجموعه‌ها نیستند را محاسبه می‌کند. یک تعمیم از این مفهوم این است که تعداد عناصری را که در دقیقاً m زیرمجموعهٔ مشخص آمده است را بشماریم.

فرض کنید:

N = [n] = {1,2،... ,n}

اگر تعریف کنیم ${\displaystyle A_{\emptyset }=S}$، اصل شمول و عدم شمول می‌تواند به صورت زیر نوشته شود:

${\displaystyle \sum _{J\subseteq [n]}(-1)^{|J|}|A_{J}|.}$

اگر I یک زیرمجموعهٔ خاص از N باشد، تعداد عناصری که به A_i به ازای تمام iهای عضو I و نه بغیر از آن‌ها تعلق دارند برابر است با:

${\displaystyle \sum _{I\subseteq J}(-1)^{|J|-|I|}|A_{J}|.}$

با تعریف مجموعهٔ

${\displaystyle B_{k}=A_{I\cup \{k\}}}$ برای هر k در ${\displaystyle N\setminus I}$.

ما به دنبال تعداد عناصری می‌گردیم که در هیچ‌یک از B_kها نیستند، که برابر است با: (با ${\displaystyle B_{\emptyset }=A_{I}}$)

${\displaystyle \sum _{K\subseteq N\setminus I}(-1)^{|K|}|B_{K}|.}$

تناظر K ↔ J = I ∪ K بین زیرمجموعه‌های N که شامل I هستند دوسویی است و اگر J و K متناظر باشند سپس B_K = A_J ، که نشان می‌دهد نتیجه درست است.

در احتمالات[ویرایش]

در احتمالات، برای رویدادهای A_n، …، A_۱ در یک فضای احتمالی ${\displaystyle \scriptstyle (\Omega ,{\mathcal {F}},\mathbb {P} )}$، برای n=۲ به شکل زیر در می‌آید:

${\displaystyle \mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),}$

برای n=۳:

${\displaystyle \mathbb {P} (A_{1}\cup A_{2}\cup A_{3})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})\qquad {}-\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})\qquad {}+\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})}$

در حالت کلی:

${\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}{}=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i<j}\mathbb {P} (A_{i}\cap A_{j})\qquad +\sum _{i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})-\ \cdots \ +(-1)^{n-1}\,\mathbb {P} {\biggl (}\bigcap _{i=1}^{n}A_{i}{\biggr )},}$

که به در فرم بسته می‌تواند به صورت زیر نوشته شود:

${\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}\left((-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,n\} \atop \scriptstyle |I|=k}\mathbb {P} (A_{I})\right),}$

که آخرین سیگما روی تمام زیرمجموعه‌های I از اندیس ۱ تا n که دقیقاً k عضو دارند حرکت می‌کند و

${\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}$

نمایانگر اشتراک تمام A_iهاست که اندیسشان در I است.

براساس نامساوی بول، مجموع اولین جملات در فرمول یک حد بالا و حد پایین برای سمت چپ معادله‌اند. این می‌تواند در مواردی استفاده شود که فرمول کامل بسیار سنگین باشد.

حالت خاص[ویرایش]

اگر در نسخهٔ احتمالی اصل شمول و عدم شمول احتمال اشتراک A_I فقط به اندازهٔ I بستگی داشته‌باشد، داریم:

${\displaystyle a_{k}=\mathbb {P} (A_{I})\quad {\text{for every}}\quad I\subset \{1,\ldots ,n\}\quad {\text{with}}\quad |I|=k,}$

فرمول بالایی ساده می‌شود به:

${\displaystyle \mathbb {P} {\biggl (}\bigcup _{i=1}^{n}A_{i}{\biggr )}=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}}$

صورت‌های دیگر[ویرایش]

این اصل گاهی اوقات به این صورت بیان می‌شود که می‌گوید اگر

${\displaystyle g(A)=\sum _{S\subseteq A}f(S)}$

آنگاه

${\displaystyle f(A)=\sum _{S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)\qquad (**)}$

می‌توان نشان داد که حالت ترکیبیاتی و احتمالاتی اصل شمول و عدم شمول نمونه‌هایی از (**)‌اند.

کاربردها[ویرایش]

این اصل کاربردهای زیادی دارد تنها چند نمونه از آن‌ها در اینجا آورده شده‌است.

شمردن تعداد پریش‌ها[ویرایش]

یک کاربرد معروف از این اصل در مسائل ترکیبیاتی شمردن تمام پریش‌های یک مجموعهٔ متناهی است. یک پریش از A یک تناظر یک به یک از خودش به خودش است به طوری که نقطهٔ ثابت نداشته باشد. با استفاده از اصل شمول و عدم شمول می‌توان نشان داد که اگر اندازهٔ A برابر با n باشد، تعداد پریش‌های آن برابر است با ${\displaystyle \lfloor n!/e\rfloor }$

شمردن اندازهٔ اشتراک[ویرایش]

از این اصل با ترکیب با قوانین دمورگان می‌توان برای شمردن اندازهٔ اشتراک چند مجموعه نیز استفاده کرد. فرض کنید ${\displaystyle \scriptstyle {\overline {A}}_{k}}$ مکمل مجموعهٔ A_k نسبت به مجموعهٔ مرجع A باشد به طوری که برای هر k داشته باشیم ${\displaystyle \scriptstyle A_{k}\,\subseteq \,A}$ در اینصورت داریم:

${\displaystyle \bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A}}_{i}}}}$

رنگ‌آمیزی گراف[ویرایش]

این اصل پایهٔ چند الگوریتم افراز گراف از قبیل رنگ‌آمیزی گراف را تشکیل می‌دهد.

تطابق‌های گراف دوبخشی[ویرایش]

تعداد تطابقهای یک گراف دوبخشی با استفاده از این اصل قابل شمارش است.

تعداد توابع پوشا[ویرایش]

با استفاده از اصل شمول و عدم شمول می‌توان دریافت که تعداد توابع پوشا از A به B برابر است با:

${\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}(-1)^{j}(n-j)^{k}.}$

که ${\displaystyle |A|=k}$ و ${\displaystyle |B|=n}$

جایگشت‌ها با مکان‌های ممنوع[ویرایش]

جایگشت‌های اعداد ۱ تا n که هر عدد در برخی از مکان‌های مشخص نمی‌تواند قرار بگیرد، جایگشت‌ها با مکان‌های ممنوع گفته می‌شوند. تعداد این جایگشت‌ها را می‌توان با استفاده از اصل شمول و عدم شمول به دست آورد.

اعداد استرلینگ نوع دوم[ویرایش]

اعداد استرلینگ نوع دوم ${\displaystyle S(n,k)}$ تعداد افرازهای یک مجموعهٔ nعضوی را به k زیرمجموعهٔ غیرتهی می‌شمارد. یک فرمول صریح که با استفاده از اصل شمول و عدم شمول برای آن بدست می‌آید فرمول زیر است:

${\displaystyle S(n,k)={\frac {1}{k!}}\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}(k-t)^{n}.}$

چندجمله‌ای رخ[ویرایش]

چندجمله‌ای رخ یک تابع مولد است که تعداد راه‌هایی را که می‌توان رخ‌هایی را در صفحه شطرنج قرار داد بیان می‌کند. با استفاده از این اصل می‌توان جمله‌های این چندجمله‌ای را حساب کرد.

تابع فی اویلر[ویرایش]

تابع فی اویلر برای یک عدد مانند n تعداد اعداد مثبت اول نسبت به آن که از آن بزرگتر نیستند را بدست می‌دهد. با استفاده از اصل شمول و عدم شمول می‌توان این تابع را محاسبه کرد:

${\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{r}^{a_{r}}.}$

ثابت می‌شود که:

${\displaystyle \phi (n)=n-\sum _{i=1}^{r}{\frac {n}{p_{i}}}+\sum _{1\leq i<j\leq r}{\frac {n}{p_{i}p_{j}}}-\cdots =n\prod _{i=1}^{r}\left(1-{\frac {1}{p_{i}}}\right).}$

اصل شمول و عدم شمول رقیق[ویرایش]

در خیلی از مواردی که این اصل قادر است که فرمولی دقیق ارائه کند، آن فرمول به دلیل تعداد زیاد جملات کارایی ندارد. در این موارد یافتن یک کران بالا از مقدار دقیق عبارت می‌تواند مطلوب‌تر باشد.

فرض کنید A_n، …، A_۱ مجموعه‌هایی دلخواه و p_n، …، p_۱ در بازهٔ بستهٔ [۰٬۱] باشند. برای هر k در ${\displaystyle \{0,\dots ,n\}}$ تابع مشخصه در تساوی زیر صدق می‌کند:

${\displaystyle 1_{A_{1}\cup \cdots \cup A_{n}}\geq \sum _{j=1}^{k}(-1)^{j-1}\sum _{1\leq i_{1}<\cdots <i_{j}\leq n}p_{i_{1}}\dots p_{i_{j}}\,1_{A_{i_{1}}\cap \cdots \cap A_{i_{j}}}.}$

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

فرض کنید A حاصل اشتراک ${\displaystyle \scriptstyle \cup _{i=1}^{n}A_{i}}$ باشد. برای اثبات اصل شمول و عدم شمول در حالت کلی ابتدا باید صحت اتحاد زیر را بررسی کنیم:

${\displaystyle 1_{A}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,n\} \atop \scriptstyle |I|=k}1_{A_{I}}\qquad (*)}$

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

${\displaystyle A_{I}=\bigcap _{i\in I}A_{i}.}$

برای این کار حداقل دو راه زیر وجود دارد:

روش اول: کافیست تا این کار را برای هر x عضو A انجام دهیم. فرض کنید x به دقیقاً m مجموعه تعلق دارد که ۱ ≤ n ≥ m، برای سادگی فرض کنید آن مجموعه‌ها A_m، …، A_۱ باشند. پس اتحاد برای x به صورت زیر تقلیل می‌یابد:

${\displaystyle 1=\sum _{k=1}^{m}(-1)^{k-1}\sum _{\scriptstyle I\subset \{1,\ldots ,m\} \atop \scriptstyle |I|=k}1.}$

تعداد زیرمجموعه‌ها با اندازهٔ k از یک مجموعهٔ mعضوی برابر با ${\displaystyle \textstyle {\binom {m}{k}}}$. بنابراین ${\displaystyle \textstyle 1={\binom {m}{0}}}$. داریم:

${\displaystyle {\binom {m}{0}}=\sum _{k=1}^{m}(-1)^{k-1}{\binom {m}{k}}.}$

با در نظر گرفتن تمام جملات سمت چپ معادله، به بسط ${\displaystyle (1-1)^{m}}$ می‌رسیم بنابراین (*) برای x برقرار است.

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

${\displaystyle (1_{A}-1_{A_{1}})(1_{A}-1_{A_{2}})\cdots (1_{A}-1_{A_{n}})\,=\,0,}$

چون: اگر x در A نباشد، تمام عوامل برابر با ۰–۰ = ۰ خواهند بود و در غیر این صورت، اگر x به مجموعه‌ای مثل A_m تعلق داشته باشد، عامل متناظر برابر با ۱–۱ = ۰ خواهد بود. با بسط عبارت سمت چپ (*) حاصل می‌شود.

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

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

عضوی از اجتماع تمام مجموعه‌ها انتخاب کنید و فرض کنید ${\displaystyle A_{1},A_{2},\dots ,A_{t}}$ مجموعه‌های شامل آن عضو باشند (دقت کنید کنید که t > 0). نیاز داریم که نشان دهیم این عضو دقیقاً یک بار در سمت راست اتحاد شمرده شده‌است. براساس قضیهٔ دوجمله‌ای داریم:

${\displaystyle (1-1)^{t}={\binom {t}{0}}-{\binom {t}{1}}+{\binom {t}{2}}-\cdots +(-1)^{t}{\binom {t}{t}}}$.

با استفاده از ${\displaystyle {\binom {t}{0}}=1}$ و مرتب کردن جملات، داریم:

${\displaystyle 1={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}}=|\{A_{i}\mid 1\leq i\leq t\}|-|\{A_{i}\cap A_{j}\mid 1\leq i<j\leq t\}|+\cdots +(-1)^{t+1}|\{A_{1}\cap A_{2}\cap \cdots \cap A_{t}\}|,}$

بنابراین عضو انتخاب شده دقیقاً یک بار در سمت راست معادله شمرده شده‌است.

منابع[ویرایش]

ویکی‌پدیای انگلیسی Inclusion-exclusion principle

برای اطلاعات بیشتر[ویرایش]

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