Principle of Inclusion-Exclusion

الفصل السابع: مبدأ الشمول والاستبعاد

الهدف: عد العناصر في مجموعات متداخلة بدقة (مثل عدد الطلاب الذين يدرسون CS أو Math).
1

The Inclusion-Exclusion Principle

الفكرة الأساسية

عندما نجمع حجم مجموعتين $|A| + |B|$، فإننا نعد المنطقة المشتركة (التقاطع) مرتين.
لذا يجب أن نطرح التقاطع مرة واحدة لتصحيح العد.

$|A \cup B| = |A| + |B| - |A \cap B|$
$|A \cup B \cup C| = |A| + |B| + |C|$
$- (|A \cap B| + |A \cap C| + |B \cap C|)$
$+ |A \cap B \cap C|$

Add Singles
Subtract Pairs
Add Triples

2

Applications: Counting Integers

مثال: الأعداد القابلة للقسمة

كم عدد الأعداد الصحيحة الموجبة $\le 100$ التي تقبل القسمة على 2 أو 3؟

Set A (Div by 2) $|A| = \lfloor 100/2 \rfloor = 50$
Set B (Div by 3) $|B| = \lfloor 100/3 \rfloor = 33$
Intersection (Div by 6) $|A \cap B| = \lfloor 100/6 \rfloor = 16$
Result = $50 + 33 - 16 = 67$
3

Derangements (Hat Check Problem)

ما هو الـ Derangement؟

هو تبديل (Permutation) للعناصر بحيث لا يوجد أي عنصر في مكانه الأصلي.
مثال: موظف يستلم قبعات 5 أشخاص ويعيدها لهم عشوائياً بحيث لا أحد يحصل على قبعته.

Original: 1 2 3
Derangements: 2 3 1, 3 1 2
Not Derangement: 1 3 2 (1 is fixed)
Formula ($D_n$)
$D_n = n! [ 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + (-1)^n \frac{1}{n!} ]$

تقريباً $D_n \approx \frac{n!}{e}$

🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / الإشارات

Sign Pattern (+ - +)

في قانون الشمول والاستبعاد، الإشارات دائماً تتبدل (Alternate):
1. اجمع المفردات (+).
2. اطرح الأزواج (-).
3. اجمع الثلاثيات (+).
4. اطرح الرباعيات (-)... وهكذا.

APPLICATION / الدوال الشاملة

Counting Onto Functions

عدد الدوال الشاملة (Onto) من مجموعة حجمها $m$ إلى $n$:
يستخدم مبدأ الشمول والاستبعاد:
$n^m - C(n,1)(n-1)^m + C(n,2)(n-2)^m - \dots$

→ السابق (Ch 6) الفصل التالي (Ch 8) ←