مبدأ الشمول والإقصاء
يُحصي مبدأ الشمول والإقصاء حجم اتحاد المجموعات عن طريق إضافة وطرح أحجام تقاطعاتها بالتناوب.
Definition
متطابقة عدية تنص على أن عدد عناصر اتحاد مجموعات منتهية يساوي المجموع التناوبي لعدد عناصر جميع تقاطعاتها، مأخوذة على كل مجموعة فرعية غير فارغة.
Scope
يقدم هذا الموضوع صيغة الشمول والإقصاء وتطبيقاتها في عد الكائنات التي تتجنب قائمة من الخصائص المحظورة: التباديل المضطربة (derangements)، والشموليات (surjections)، ودالة أويلر التوتية (Euler's totient)، وعدد الأعداد الصحيحة الأولية لعدد معين. كما يقدم وجهة نظر الغربال وتعميم دالة موبيوس (Mobius-function) على المجموعات المرتبة جزئيًا، مما يضع المبدأ في سياق جبري أوسع.
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
- لماذا تتناوب الإشارات؟
- تُضاف العناصر الموجودة في عدة مجموعات عددًا كبيرًا جدًا من المرات؛ ويؤدي طرح تقاطعات الأزواج إلى تصحيح زائد، لذا تُضاف تقاطعات الثلاثيات مرة أخرى، مما ينتج النمط المتناوب الذي يحصي كل عنصر مرة واحدة بالضبط.
- ما هي العلاقة بدالة موبيوس؟
- الشمول والإقصاء هو الحالة الخاصة لمقلوب موبيوس على الشبكة البوليانية للمجموعات الفرعية، حيث تأخذ دالة موبيوس قيمًا موجبة أو سالبة واحد.