اصل شمول و عدم شمول
اصل شمول و عدم شمول، اندازه اجتماع مجموعهها را با جمع و تفریق متناوب اندازههای اشتراکهای آنها محاسبه میکند.
Definition
یک هویت شمارشی که بیان میکند کاردینالیتی اجتماع مجموعههای متناهی برابر است با مجموع متناوب کاردینالیتیهای تمام اشتراکهای آنها، که بر روی هر زیرمجموعه ناتهی گرفته میشود.
Scope
این موضوع فرمول شمول و عدم شمول و کاربردهای آن را در شمارش اشیایی که از فهرستی از ویژگیهای ممنوعه اجتناب میکنند، ارائه میدهد: جایگشتهای آشفته، پوشاها، تابع فی اویلر، و تعداد اعداد اول نسبت به یک عدد معین. این موضوع دیدگاه غربال و تعمیم تابع موبیوس بر روی مجموعههای جزئی مرتب را معرفی میکند که این اصل را در یک بستر جبری گستردهتر قرار میدهد.
Core questions
- چند عنصر حداقل یکی از چندین شرط همپوشان را برآورده میکنند؟
- چگونه میتوان اشیایی را که از تمام مجموعهای از ویژگیهای ممنوعه اجتناب میکنند، شمارش کرد؟
- چگونه شمارش جایگشتهای آشفته و پوشاها از این اصل پیروی میکند؟
- چگونه تابع موبیوس بر روی یک پوزت، شمول و عدم شمول را تعمیم میدهد؟
Key concepts
- اجتماع مجموعههای همپوشان
- روش غربال
- جایگشتهای آشفته از طریق شمول و عدم شمول
- شمارش پوشاها
- تابع فی اویلر
- تابع موبیوس بر روی پوزتها
Key theories
- فرمول شمول و عدم شمول
- کاردینالیتی اجتماع مجموعههای A_1 تا A_n برابر است با مجموع اندازههای تکمجموعهها منهای اشتراکهای دوتایی به اضافه اشتراکهای سهتایی و غیره، که به طور سیستماتیک برای شمارش بیش از حد عناصر مشترک اصلاح میشود.
- وارونگی موبیوس بر روی پوزتها
- تعمیم پوزت-نظری استنلی، علائم متناوب شمول و عدم شمول را با تابع موبیوس یک مجموعه جزئی مرتب جایگزین میکند و این اصل را با فرمولهای وارونگی نظریه اعداد و نظریه مشبکه یکپارچه میسازد.
Clinical relevance
ایده غربال به نظریه اعداد (غربال اراتوستن و غربالهای تحلیلی)، احتمال (نامساویهای بونفرونی که احتمالهای اجتماع را محدود میکنند)، و تحلیل قابلیت اطمینان سیستمهایی با حالتهای خرابی همپوشان تعمیم مییابد.
History
این اصل که اساساً توسط دو موآور و سیلوستر بیان شد، در سال 1964 توسط روتا در چارچوب نظریه عمومی توابع موبیوس بر روی مجموعههای جزئی مرتب قرار گرفت که نقطه عطفی در ترکیبیات مدرن محسوب میشود.
Key figures
- Abraham de Moivre
- Gian-Carlo Rota
Related topics
Seminal works
- stanley2011
Frequently asked questions
- چرا علائم متناوب هستند؟
- عناصری که در چندین مجموعه قرار دارند، بیش از حد اضافه میشوند؛ تفریق اشتراکهای دوتایی بیش از حد اصلاح میکند، بنابراین اشتراکهای سهتایی دوباره اضافه میشوند و الگوی متناوبی را ایجاد میکنند که هر عنصر را دقیقاً یک بار محاسبه میکند.
- ارتباط با تابع موبیوس چیست؟
- شمول و عدم شمول حالت خاصی از وارونگی موبیوس بر روی مشبکه بولی زیرمجموعهها است، جایی که تابع موبیوس مقادیر مثبت یا منفی یک را میگیرد.