مبدأ التضمن والاستبعاد

Inclusion and Exclusion Principle

لنرمز لعدد عناصر مجموعة منتهية A بالرمز $\left| A \right|$ . معلوم أنه إذا كانت A,B مجموعتين منتهيتين منفصلتين فإن

$\left| {A \cup B} \right| = \left| A \right| + \left| B \right|$

أما إذا كان تقاطع المجموعتين غير خال فإن $\left| A \right| + \left| B \right|$ لا يعبر عن المجموع الصحيح لعناصر إتحاد المجموعتين وذلك لأن عناصر التقاطع تضمنها المجموع مرتين, مرة باعتبارها عناصر من A وأخرى باعتبارها عناصر من B لذلك فلابد من استبعادها مرة واحدة. وعليه فإن

$\left| {A \cup B} \right| = \left| A \right| + \left| B \right| - \left| {A \cap B} \right|$

هذا هو مبدأ التضمين والاستبعاد في أبسط صور.

في حالة ثلاث مجموعات $A_1 ,A_2 ,A_3$ منتهية فإن المبدأ على الصورة التالية

$\left| {A_1 \cup A_2 \cup A_3 } \right| = \left| {A_1 } \right| + \left| {A_2 } \right| + \left| {A_3 } \right| - \left| {A_1 \cap A_2 } \right| - \left| {A_2 \cap A_3 } \right| - \left| {A_3 \cap A_1 } \right| + \left| {A_1 \cap A_2 \cap A_3 } \right|$

لاحظ الإشارات كانت موجبة في حالة حساب عدد عناصر كل مجموعة لوحدها ثم سالبة في حالة حساب تقاطع المجموعات مثنى مثنى ثم تغيرت إلى موجبة في حالة حساب التقاطع ثلاثة ثلاثة. الآن الى الصورة العامة.

مبدأ التضمن والاستبعاد: إذا كانت $A_1 ,A_2 , \cdots ,A_n$ مجموعات منتهية فإن

$\left| {A_1 \cup A_2 \cup \cdots \cup A_n } \right| = \sum\limits_{k = 0}^n {\left| {A_k } \right|} - \sum\limits_{\scriptstyle i,j \hfill \atop \scriptstyle i \ne j \hfill}^n {\left| {A_i \cap A_j } \right|} + \cdots + ( - 1)^{n - 1} \left| {A_1 \cap A_2 \cap \cdots \cap A_n } \right|$

إذا كانت A مجموعة جزئية من مجموعة شاملة X عدد عناصرها N فإن

$\left| X \right| = \left| {A \cup A^c } \right| = \left| A \right| + \left| {A^c } \right| \Rightarrow \left| {A^c } \right| = N - \left| A \right|$

من هذا ومن قانون ديمورغان

$(A_1 \cup A_2 \cup \cdots \cup A_n )^c = A_1 ^c \cap A_2 ^c \cap \cdots \cap A_n ^c$

نستنتج أن

$\left| {(A_1 \cup A_2 \cup \cdots \cup A_n )^c } \right| = N - \left| {A_1 \cup A_2 \cup \cdots \cup A_n } \right|$

وبالتعويض في صيغة التضمن والاستبعاد نحصل على العلاقة

$\left| {A_1 ^c \cap A_2 ^c \cap \cdots \cap A_n ^c } \right| = N - \sum\limits_{k = 0}^n {\left| {A_k } \right|} + \sum\limits_{\scriptstyle i,j \hfill \atop \scriptstyle i \ne j \hfill}^n {\left| {A_i \cap A_j } \right|} + \cdots + ( - 1)^n \left| {A_1 \cap A_2 \cap \cdots \cap A_n } \right|$

لمبدأ التضمن والاستبعاد تطبيقات متعددة تتعلق بالعناصر من مجموعة أو عدة مجموعات والتي لها أكثر من خاصية. ونبدأ بهذه المسألة البسيطة والمباشرة

مثال 1: إذا كان هناك مجموعة من الطلاب فيهم 15 طالبا ناجحين في الرياضيات و9 ناجحين في الفيزياء و 11 طالبا ناجحا في كلتا المادتين فكم طالب في هذه المجموعة؟

الحل: إذا عبرنا عن الناجحين في الرياضيات بالمجموعة الجزئية A والناجحين في الفيزياء بالمجموعة الجزئية Y فإن السؤال يتعلق بإيجاد $\left| {A \cup B} \right|$ . إذا لدينا 13 طالبا لأن

$\left| {A \cup B} \right| = \left| A \right| + \left| B \right| - \left| {A \cap B} \right| = 15 + 9 - 11 = 13$

مثال 2: كم عددا في المجموعة ليس مربعا كاملا ولا مكعبا كاملا ولا كاملا بقوة رابعة؟.

الحل: لتكن A,B,C هي المجموعات الجزئية من X التي تحوي المربعات , المكعبات , القوة الرابعة على الترتيب.

المطلوب من المسألة ليس سوى $\left| {(A \cup B \cup C)^c } \right|$ . إذا علينا أيجاد عناصر التقاطعات المختلفة من المجموعات الثلاث A,B,C.

المجموعة $A \cap B$ هي تحديدا العناصر من X التي يمكن كتابتها على شكل قوة سادسة وحيث 3 هو أكبر عدد بقوة 6 يقع داخل X فإن $\left| {A \cap B} \right| = 3$ . كل عنصر من C يقع في $A \cap C$ (لماذا؟). إذا $\left| {A \cap C} \right| = \left| C \right| = 5$ . أخيرا $\left| {B \cap C} \right| = 1$ لأن هذا التقاطع خاص فقط بالعناصر التي هي على الشكل $a^{12}$ وليس هنا سوى a=1. وحيث

$\left| {A \cap B \cap C} \right| = 1$

وهذا لأن هذا التقاطع محتوى في $B \cap C$ والعدد 1 موجود في المجموعات الثلاث. من كل ما سبق ومن مبدأ التضمن والاستبعاد

$\left| {A \cup B \cup C} \right| = \left| A \right| + \left| B \right| + \left| C \right| - \left| {A \cap B} \right| - \left| {B \cap C} \right| - \left| {C \cap A} \right| + \left| {A \cap B \cap C} \right|$