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

اصل شمول و عدم شمول (همچنین اصل ورود و خروج و یا از روش ورود و خروج) است روش مفیدی برای تعیین قدرت مجموعه . این است که عمدتا در ترکیب ، نظریه اعداد و تصادفات استفاده می شود .

اصل بیانگر قلبی بودن یک مجموعه اصلی است $ایکس$ توسط کاردینال های زیر مجموعه های آنها . معمولاً تعیین این موارد آسانتر است. این نام به روشی گفته می شود که در آن مجموع اندازه زیرمجموعه های لزوماً از هم جدا نیستند $ایکس$ از بالا تخمین زده شده است (شمول) ، اما پس از آن سعی شده با کم کردن اندازه بخش مشترک زیر مجموعه ها (محرومیت) دوباره این مسئله را اصلاح کنید .

فهرست

اصل [ ویرایش | ویرایش منبع ]

اصل شمول و طرد با استفاده از مثال سه مجموعه

این یک نتیجه شناخته شده است که برای هر دو مجموعه محدود است $آ.$ و $ب$

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

اعمال میشود. در اینجا می توانید اصل شمول و محرومیت را مشاهده کنید. توسط $| الف | + | ب |$ اول می شود $| A \ cup B |$ تخمین زده شده از بالا. این تعداد زیاد زیاد سپس با کم کردن محاسبه می شود $| A \ cap B |$ تصحیح شده. هدف از این اصلاح ، تفریق آن عناصری است که در هر دو قرار دارند{\ نمایشگر A $آ.$ و همچنین در $ب$ گنجانده شده است و بنابراین در ابتدا دو بار شمارش می شدند.

شکل سمت راست نشان می دهد که تعمیم به سه مجموعه متناهی

$| A \ cup B \ cup C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap ج |$

نتایج.

به طور کلی ما می خواهیم کاردینال اتحادیه از $ن$ مجموعه های محدود

$\ displaystyle X = A_ {1} \ فنجان A_ {2} \ فنجان \ dotsb \ فنجان A_ {n}$

تعیین کردن به عنوان یک تقریب اول ، ما مجموع کاردینالیت های آن را بدست می آوریم $A_ {من$ . با این حال ، این مبلغ می تواند خیلی بزرگ باشد زیرا ما عناصر تقاطع دو مجموعه هستیم $A_ {i} \ cap A_ {j$ چندین بار حساب می کرد:

$\ displaystyle | X | \ leq \ sum _ {1 \ leq i \ leq n} | A_ {i} |}$

برای تصحیح این موضوع ، اکنون می توانیم مبلغ کاردینالیتی تقاطع های همه جفت های مجموعه را با استفاده از محرومیت کم کنیم. سپس:

زیرا عناصر تقاطع سه مجموعه $A_ {i} \ cap A_ {j} \ cap A_ {k}$ اگرچه فقط دو بار یکبار در شمول موارد شمارش می شدند $| A_ {i} \ cap A_ {j} |$ ، توسط $| A_ {i} \ cap A_ {k} |$ و از طریق $| A_ {j} \ کلاه A_ {k} |$ برداشت سه بار تصحیح این کار با شمول ، یعنی با اضافه کردن مجموع اندازه همه بخش ها از سه مجموعه ، نتیجه می گیرد:

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

\ displaystyle | X | \ geq \ sum _ {1 \ leq i \ leq n} | A_ {i} | ~ - \ sum _ {1 \ leq i

و غیره ، جایی که به عنوان مثال \ displaystyle \ sum _ {1 \ leq i بدان معنی است که بیش از همه سه برابر سفارش داده شده است {\ نمایشگر (من ، ج ، ک) $(من ، ج ، ک)$ که به نابرابری خلاصه شده است \ displaystyle 1 \ leq i پیروی کردن، اطاعت کردن، تسلیم شدن.

جمله [ ویرایش | ویرایش منبع ]

جمله عمومی زیر قابل اثبات است.

مجموعه متناهی داده شده است $ایکس$ ، که یک انجمن است $ن$ زیرمجموعه ها ${\ displaystyle A_ {1} ، A_ {2} ، \ dotsc ، A_ {n}}$ بگذارید بنویسید ، د. ح $X = \ bigcup _ {{i = 1}} ^ {n} A_ {i$ . در زیر مجموعه ای از شاخص را بیان می کند $\ displaystyle I \ subseteq \ {1،2 ، \ dotsc ، n \}$ مقدار $A_ {من}$ تقاطع همه زیر مجموعه های مشخص شده توسط عناصر مجموعه شاخص ، یعنی:

$A_ {I}: = \ bigcap _ {{i \ in I}} A_ {i}$ با مورد خاص \ نمایشگر A _ {\ پوسته} = X} $A _ {\ vacyset} = X$

سپس:

$\ displaystyle | X | = \ sum _ {\ vacyset \ not = I \ subseteq \ {1، \ dotsc، n \}} \ چپ (-1 \ راست) ^ {| I | +1 | A_ {من |}$

به عبارت دیگر ، تمام برش های احتمالی را در نظر بگیرید $A_ {من}$ (به جز برش خالی $A _ {\ vacyset$ ) ، سپس کاردینالی بودن $ایکس$ برابر با کل کاردینالیت تمام بخشهای تعداد زیر مجموعه های عجیب و غریب (شامل) منهای مجموع کاردینالیت تمام بخشهای یک تعداد مشترک زیر مجموعه (حذف) ، به طور رسمی:

$\ displaystyle | X | = \ sum _ {{I \ subseteq \ {1، \ dotsc، n \}،} \ atop {| I | | {\ text {عجیب و غریب}}} A | A_ {I} | - \ sum _ {{\ vacyset \ not = I \ subseteq \ {1، \ dotsc، n \}،} \ atop {| I | ~ {\ متن {حتی}}} A | A_ {I} |}$

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

فرمول غربالگری Poincaré و Sylvester ، که برای احتمالات نیز قضیه اضافی نیز خوانده می شود ، کاربردی از این اصل را ارائه می دهد :

برای احتمال هر رویدادی $A_ {من$ از یک فضای احتمال $(\ امگا ، \ سیگما ، پ)$ اعمال میشود:

$\ displaystyle P \ left (\ bigcup _ {i = 1} ^ {n} A_ {i} \ Right) = \ sum _ {k = 1} ^ {n} \ left ((- 1) ^ {k + 1} \! \! \ Sum_ {I \ subseteq \ {1، \ dotsc، n \}، \ atop | I | = k} \! \! \! \! \! \! P \ left (\ bigcap _ {i \ در I} A_ {i} \ درست) \ درست)}$

از آنجا که از جمع پذیری از اقدامات ، اثبات اکتشافی بالا به اصل ورود و خروج، که با استفاده از ابزار نظریه مجموعه ابتدایی انجام شد داده می شود، می توان به طور مستقیم به احتمال منتقل شده است.

به عنوان مثال ، در مورد سه رویداد اعمال می شود $آ.$ ، $ب$ و $ج$ همیشه

$\ displaystyle {P (A \ cup B \ cup C) = P (A) + P (B) + P (C) -P (A \ cap B) -P (A \ cap C) -P (B \ درپوش C) + P (A \ cap B \ cap C)}$ .

به طور کلی، این بیانیه همچنین شامل محدود محتوای در حلقه .

مثال [ ویرایش | ویرایش منبع ]

→ نوشتار اصلی : رایگان نقطه جایگشت ثابت

در سنت قبل از کریسمس الف ها ، گروهی به یکدیگر هدیه می دهند. هرکسی دقیقاً به یک نفر هدیه می دهد و به نوبه خود دقیقاً یک نفر به آنها هدیه می دهد. برای تعیین اینکه چه کسی هدیه را دریافت می کند ، از یک ترسیم تصادفی استفاده می شود. در حالت ایده آل ، هرکدام باید هدیه شخص دیگری را دریافت کنند. با این وجود ، ممکن است اتفاق بیفتد که شخصی به طور تصادفی هدیه خود را دریافت کند. برای شخص مربوطه ، غافلگیری تمام می شد. اما چقدر این پرونده برای گروهی احتمال دارد $ن$ مردم؟

به صورت ریاضی بیان شده است که احتمال وقوع A را مشخص می کند: = "حداقل یک نفر هدیه خود را دریافت می کند". این معادل حداقل یکی از رویدادهای A i : = "شخصی است که من هدیه خود را دریافت می کنم" برای آن ${\ displaystyle i \ in \ {1، \ dotsc، n \}}$ اعمال می شود ، در $ن$ تعداد افرادی است که در الف ها شرکت می کنند. اصطلاح درست فرمول غربال

می تواند بیش از حد ساده شود

$\ displaystyle {nP (A_ {1}) - {\ binom {n} {2}} P (A_ {1} \ cap A_ {2}) + {\ binom {n} {3}} P (A_ { 1} \ cap A_ {2} \ cap A_ {3}) - {\ binom {n} {4}} P (A_ {1} \ cap A_ {2} \ cap A_ {3} \ cap A_ {4} )}}$

$\ displaystyle + {\ binom {n} {5}} P (A_ {1} \ cap A_ {2} \ cap A_ {3} \ cap A_ {4} \ cap A_ {5}) - \ dotsb + \ dotsb + (- 1) ^ {n + 1} P (A_ {1} \ cap \ dotsb \ cap A_ {n)}}$ ،

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

$\ displaystyle P (A_ {1} \ cap A_ {2} \ cap A_ {3} \ cap \ dotsb \ cap A_ {k}) = {\ frac {1} {n \ cdot (n-1) \ cdot (n-2) \ cdot \ dotsm \ cdot (n-k + 1)}}$ .

با کمک تعریف ضریب دوتایی ، فردی به دست می آید

$\ displaystyle {P (A_ {1} \ cup \ dotsb \ cup A_ {n}) = n \ cdot {\ frac {1} {n}} - {\ frac {n (n-1)} {1 \ cdot 2}} \ cdot {\ frac {1} {n (n-1)}} + {\ frac {n (n-1) (n-2)} {1 \ cdot 2 \ cdot 3}} \ cdot \ frac {1} {n (n-1) (n-2)}}}}$

$\ displaystyle - {\ frac {n (n-1) (n-2) (n-3)} {1 \ cdot 2 \ cdot 3 \ cdot 4}} \ cdot \ frac {1} {n ( n-1) (n-2) (n-3)}} + {\ frac {n (n-1) (n-2) (n-3) (n-4) {1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5} \ cdot {\ frac {1} {n (n-1) (n-2) (n-3) (n-4)}}}}$

$\ displaystyle - \ dotsb + \ dotsb - \ dotsb + \ dotsb + (- 1) ^ {n + 1} \ cdot {\ frac {1} {1 \ cdot 2 \ cdot 3 \ cdot \ dotsm \ cdot n }}}$ .

پس از کوتاه کردن کسری نتیجه می گیرد

$\ displaystyle {P (A_ {1} \ cup \ dotsb \ cup A_ {n}) = 1 - {\ frac {1} {1 \ cdot 2}} + {\ frac {1} {1 \ cdot 2 \ cdot 3}} - {\ frac {1} {1 \ cdot 2 \ cdot 3 \ cdot 4}} + {\ frac {1} {1 \ cdot 2 \ cdot 3 \ cdot 4 \ cdot 5}} - \ dotsb + \ dotsb - \ dotsb + \ dotsb + (- 1) ^ {n + 1} \ cdot {\ frac {1} {1 \ cdot 2 \ cdot 3 \ cdot \ dotsm \ cdot n}}$ .

با نماد مبالغ ، می توان به عنوان کوتاه کرد $\ displaystyle P (A_ {1} \ cup \ dotsb \ cup A_ {n}) = 1- \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k !}}$ بیان.

با گروه های بزرگ ، تعداد کاملاً جمع باید اضافه شود و کارخانه! $ک!$ به سرعت بسیار بزرگ می شود در این حالت محدود کردن این مبلغ مفید است $n \ to \ infty$ ساختن:

$\ displaystyle \ lim _ {n \ to \ infty} \ left (1- \ sum _ {k = 0} ^ {n} {\ frac {(-1) ^ {k}} {k!}} \ Right ) = 1- \ sum _ {k = 0} ^ {\ infty} {\ frac {(-1) ^ {k}} {k!}} = 1-e ^ {- 1 = 1 - {\ frac {1} {e} approx \ تقریبی 63 ،} 2 \ ، \٪$

این سریال ارزیابی سریال تیلور با نقطه توسعه است{\ نمایشگر 0} ${\ نمایشگر 0}$ تابع نمایی طبیعی در نقطه $x = -1$ به همین دلیل راه حل در کل است $\ displaystyle 1 - {\ frac {1} {e}}}$ ساده شده. این مقدار می تواند به عنوان یک تقریب برای بزرگ استفاده شود $ن$ به عنوان مشاهده شود. در گروه های بزرگ ، احتمالاً تقریباً است ${\ displaystyle 63 {،} 2 \، \٪$ برای حداقل یک نفر هدیه خود را دریافت کند. [1] [2]