العدّ المتقدّم باستخدام مبدأ الاحتواء والاستبعاد

القسم 3.8 العدّ المتقدّم باستخدام مبدأ الاحتواء والاستبعاد

الأهداف

بعد إتمام هذا القسم، ينبغي أن تكون قادرًا على القيام بما يلي.

1. تطبيق مبدأ الاحتواء والاستبعاد (Principle of Inclusion/Exclusion) لحل مسائل عدّ تتضمّن مجموعات متعدّدة (multisets) ذات تكرار محدود.
2. تطبيق مبدأ الاحتواء والاستبعاد لحل مسائل عدّ تتضمّن التبديلات غير المطابقة (derangements).
3. تطبيق مبدأ الاحتواء والاستبعاد لحل مسائل عدّ تتضمّن الدوال الشاملة (surjective functions).

معاينة القسم

استكشف!

لديك 11 فطيرة ليمون صغيرة متطابقة لتوزّعها على 4 أطفال. لكنك لا تريد أن يحصل أي طفل على أكثر من 3 فطائر. كم طريقة لتوزيع هذه الفطائر؟

تتيح لنا طريقة «العصي والحصى» حساب عدد طرق توزيع 10 قطع من البسكويت على 3 أطفال، وكذلك الحلول في الأعداد الطبيعية للمعادلة $x+y+z = 10\text{,}$ مثلًا. ويسمحنا تعديلٌ سهل نسبيًا بوضع قيد حدّ أدنى على هذه المسائل: ربما يجب أن يحصل كل طفل على قطعتين من البسكويت على الأقل، أو $x,y,z \ge 2\text{.}$ وقد تم ذلك بإعطاء كل طفل (أو كل متغير) قطعتين (أو وحدتين) أولًا، ثم توزيع الباقي بواسطة العصي والحصى.

وماذا لو أردنا قيد حدّ أعلى؟ على سبيل المثال، قد نطالب بألا يحصل أي طفل على أكثر من 4 قطع من البسكويت، أو بأن $x, y, z \le 4\text{.}$ ويبيّن أنّ هذا أصعب بكثير.

ولاحظ أنك إذا أخذت في الحسبان الحدث التكميلي، أي توزيعات البسكويت التي يحصل فيها الأطفال فعلًا على أكثر من 4 قطع، فإنك تعود إلى مسألة عصي وحصى ذات حدّ أدنى. ولو استطعنا عدّ هذا، لكان طرحه من العدد الكلي للتوزيعات سيعطينا الإجابة المرغوبة. لكن المشكلة أن تكملة «لا يحصل أي طفل على أكثر من 4 قطع» هي «يحصل طفل واحد على الأقل على أكثر من 4 قطع». ونحن نعرف كيف نتعامل مع اشتراط أن يحصل جميع الأطفال على 4 قطع على الأقل، لكن كيف نتعامل مع الحالة التي يحصل فيها طفل واحد أو أكثر على 4 قطع على الأقل؟ علينا استخدام مبدأ الاحتواء والاستبعاد.

ورقة العمل: نشاط تمهيدي

لنراجع أولًا بعض المسائل من نوع «العصي والحصى» التي تعلّمناها في القسم 3.5.

ثم سنعدّل ذلك ونطبّق مبدأ الاحتواء والاستبعاد الوارد في القسم 3.3.

1.

لنفترض لدينا 10 قطع من البسكويت نوزّعها على ثلاثة أطفال: ألبِي وبيرتي وتشارلي.

(a)

كم طريقة لتوزيع قطع البسكويت دون أي قيود؟

(b)

كم طريقة لتوزيع قطع البسكويت إذا كان على كل طفل أن يحصل على قطعتين على الأقل؟

تلميح. أعطِ كل طفل أصغر عدد ممكن من القطع أولًا. كم طريقة لتوزيع القطع المتبقية؟

(c)

كم طريقة لتوزيع قطع البسكويت إذا كان على ألبِي أن يحصل على 3 قطع على الأقل، وعلى بيرتي قطعتين على الأقل (ولا قيود على تشارلي)؟

2.

لنعد إلى التفكير في الـ 10 قطع من البسكويت التي نريد توزيعها على ألبِي وبيرتي وتشارلي. لكن هذه المرة سنضع بعض قيود الحدّ الأعلى.

(a)

كم طريقة لتوزيع قطع البسكويت إذا كان على ألبِي أن يحصل فعلًا على أكثر من 3 قطع (أي 4 على الأقل)؟

وكم طريقة لتوزيعها إذا كان على ألبِي ألاّ يحصل على أكثر من 3 قطع؟

(b)

كم طريقة لتوزيع قطع البسكويت إذا كان على بيرتي أن يحصل فعلًا على أكثر من 3 قطع؟

(c)

كم طريقة لتوزيع قطع البسكويت إذا كان على ألبِي وبيرتي أن يحصل فعلًا كلٌّ منهما على أكثر من 3 قطع؟

(d)

باستخدام مبدأ الاحتواء والاستبعاد لمجموعتين، كم طريقة لتوزيع قطع البسكويت إذا كان طفل واحد على الأقل من ألبِي أو بيرتي يحصل على أكثر من 3 قطع؟ أي إما أن يحصل ألبِي على أكثر من 3 قطع، أو يحصل بيرتي على أكثر من 3 قطع، أو يحصل كلاهما على أكثر من 3 قطع.

(e)

كم طريقة لتوزيع قطع البسكويت إذا كان لا يحصل ألبِي ولا بيرتي على أكثر من 3 قطع؟

قسم فرعي: مبدأ الاحتواء والاستبعاد للمجموعات المتعددة

يمنحنا مبدأ الاحتواء والاستبعاد طريقةً لإيجاد عدد المجموعة (cardinality) لاتحاد مجموعاتٍ ليست بالضرورة متباعدة. وقد رأينا في القسم 3.3 كيف يعمل هذا مع ثلاث مجموعات. ولإيجاد عدد الأشياء الموجودة في مجموعة واحدة أو أكثر من المجموعات $A\text{,}$ $B\text{,}$ و$C\text{,}$ يكفي أن نجمع عدد الأشياء في كلٍّ من هذه المجموعات. لكن إن كان هناك أي تراكب بين المجموعات، فإن هذه العناصر تُعدّ مراتٍ متعددة. لذا نطرح الأشياء الموجودة في كل تقاطع بين زوج من المجموعات. لكن هذا الطرح يزيل عناصر موجودة في المجموعات الثلاث مجتمعةً مرةً أكثر مما ينبغي، فيلزم أن نعيدها. وبعبارات عدد المجموعة، لدينا $$\begin{equation*} |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A\cap B \cap C| \text{.} \end{equation*}$$

المثال 3.8.1.

ثلاثة أطفال، هم ألبرتو وبرناديت وكارلوس، يقرّرون تقاسم 11 قطعة من البسكويت. ويتساءلون في كم طريقة يمكنهم تقسيم قطع البسكويت، شريطة ألّا يحصل أي منهم على أكثر من 4 قطع (وأنّ أحدهم لا يحصل على أي قطع أمرٌ مقبول عند هؤلاء الأطفال لسبب ما).

الحل. لولاه قيد «لا أكثر من 4» لكانت الإجابة ${13 \choose 2}\text{,}$ باستخدام 11 حجرًا وعصايين (يفصلان بين الأطفال الثلاثة). والآن نعدّ عدد الطرق التي يخالف فيها طفل واحد أو أكثر الشرط، أي التي يحصل فيها الطفل على 4 قطع على الأقل.

لتكن $A$ مجموعة النتائج التي يحصل فيها ألبرتو على أكثر من 4 قطع. ولتكن $B$ مجموعة النتائج التي يحصل فيها برناديت على أكثر من 4 قطع. ولتكن $C$ مجموعة النتائج التي يحصل فيها كارلوس على أكثر من 4 قطع. إننا نبحث (من أجل الطرح) عن عدد عناصر المجموعة $A \cup B \cup C\text{.}$ وباستخدام مبدأ الاحتواء والاستبعاد، علينا إيجاد أعداد $|A|\text{,}$ $|B|\text{,}$ $|C|\text{,}$ $|A\cap B|$ وهكذا. وهذا ما نجده.

• $|A| = {8 \choose 2}\text{.}$ أعطِ ألبرتو 5 قطع أولًا، ثم وزّع القطع الستّ الباقية على الأطفال الثلاثة دون قيود، باستخدام 6 أحجار وعصايين.
• $|B| = {8 \choose 2}\text{.}$ تمامًا كما سبق، لكن برناديت هي التي تحصل على 5 قطع في البداية.
• $|C| = {8 \choose 2}\text{.}$ كارلوس يحصل على 5 قطع أولًا.
• $|A \cap B| = {3 \choose 2}\text{.}$ أعطِ ألبرتو وبرناديت 5 قطع لكلٍّ منهما، فيتبقّى 1 (حجر) لتوزيعه على الأطفال الثلاثة (عصايين).
• $|A \cap C| = {3 \choose 2}\text{.}$ ألبرتو وكارلوس يحصلان على 5 قطع أولًا.
• $|B \cap C| = {3 \choose 2}\text{.}$ برناديت وكارلوس يحصلان على 5 قطع أولًا.
• $|A \cap B \cap C| = 0\text{.}$ من المستحيل أن يحصل الأطفال الثلاثة كلهم على 4 قطع أو أكثر.

بجمع كل هذه القيم نرى أنّ $$\begin{equation*} |A \cup B \cup C| = {8 \choose 2} + {8 \choose 2} + {8 \choose 2} - {3 \choose 2} - {3 \choose 2} - {3 \choose 2} + 0 = 75 \text{.} \end{equation*}$$

ومن ثمّ فإن الإجابة على السؤال الأصلي هي ${13 \choose 2} - 75 = 78 - 75 = 3\text{.}$ وهذا منطقي بمجرد رؤيته. فالطريقة الوحيدة لضمان ألّا يحصل أي طفل على أكثر من 4 قطع هي منح طفلين 4 قطع وطفل 3 قطع؛ وهناك ثلاثة اختيارات للطفل الذي ينبغي أن يكون ذلك. كان بإمكاننا إيجاد الإجابة بسرعة أكبر بكثير من خلال هذه الملاحظة، لكن الغرض من المثال هو توضيح أنّ مبدأ الاحتواء والاستبعاد يعمل!

أما لأربع مجموعات أو أكثر، فلا نكتب صيغة لمبدأ الاحتواء والاستبعاد. بل نفكّر في المبدأ نفسه: نجمع كل العناصر في المجموعات المفردة، ثم نطرح ما عدناه مرتين (العناصر الموجودة في تقاطع زوج من المجموعات)؛ ثم نعيد ما أزلناه أكثر من اللازم (العناصر الموجودة في تقاطع مجموعات ثلاثية)؛ ثم نطرح ثانية ما أعدناه أكثر من اللازم (العناصر الموجودة في تقاطع مجموعات رباعية)؛ ثم نعيد، ونطرح، ونعيد، وهكذا. وسيكون هذا صعبًا جدًا لولا أنّه في هذه المسائل تكون أعداد المجموعات المفردة كلها متساوية، وكذلك أعداد تقاطعات المجموعات الثنائية، وتقاطعات المجموعات الثلاثية، وهكذا. ومن ثمّ يمكننا تجميع كل هذه معًا والضرب في عدد التوليفات المختلفة لمجموعات من 1 و2 و3 و… مجموعة.

المثال 3.8.2.

في كم طريقة يمكنك توزيع 10 قطع من البسكويت على 4 أطفال بحيث لا يحصل أي طفل على أكثر من قطعتين؟

الحل. هناك ${13 \choose 3}$ طريقة لتوزيع 10 قطع من البسكويت على 4 أطفال (باستخدام 10 أحجار و3 عصي). وسنطرح كل النتائج التي يحصل فيها طفل على 3 قطع أو أكثر. كم عدد النتائج من هذا النوع؟ يمكننا إجبار الطفل A على أكل 3 قطع أو أكثر بإعطائه 3 قطع قبل أن نبدأ. ويؤدي ذلك إلى اختصار المسألة إلى مسألة لدينا فيها 7 قطع نوزّعها على 4 أطفال دون أي قيود. في هذه الحالة لدينا 7 أحجار (القطع الباقية السبعة) و3 عصي (أقل بواحد من عدد الأطفال)، ومن ثمّ يمكننا توزيع القطع بـ ${10 \choose 3}$ طريقة.بالطبع يمكننا اختيار أي طفل من الأطفال الأربعة لنمنحه أكثر مما ينبغي من القطع، فيبدو أن لدينا ${4 \choose 1}{10 \choose 3}$ طريقة لتوزيع القطع بحيث يحصل طفل واحد على أكثر مما ينبغي. لكننا في الواقع قد حسبنا أكثر مما ينبغي.

ويجب أن نتخلّص من النتائج التي يحصل فيها طفلان على أكثر مما ينبغي من القطع. هناك ${4 \choose 2}$ طريقة لاختيار طفلين لنمنحهما قطعًا إضافية. ويحتاج ذلك إلى 6 قطع، فلا يتبقّى سوى 4 قطع. ولدينا بالتالي 4 أحجار وما زالت لدينا 3 عصي. ويمكن توزيع القطع الأربعة الباقية بـ ${7 \choose 3}$ طريقة (لكلٍّ من اختيارات ${4 \choose 2}$ لأي طفلين نمنحهما زيادة).

لكننا الآن أزلنا أكثر مما ينبغي. وعلينا أن نعيد كل طرق منح ثلاثة أطفال أكثر مما ينبغي من القطع. فهذا يستهلك 9 قطع، فلا يتبقّى سوى 1 لتوزيعها على الأطفال الأربعة بواسطة العصي والحصى، ويمكن ذلك بـ ${4 \choose 3}$ طريقة. ويجب أن نأخذ هذه النتيجة في الحسبان لكل اختيار ممكن لأي ثلاثة أطفال نمنحهم زيادة، وهناك ${4 \choose 3}$ طريقة لاختيار تلك المجموعة من الأطفال الثلاثة.

بعد ذلك سنطرح كل طرق منح أربعة أطفال أكثر مما ينبغي من القطع، لكن في هذه الحالة يكون ذلك العدد 0.

ومجتمعةً نحصل على أن عدد طرق توزيع 10 قطع من البسكويت على 4 أطفال دون منح أي طفل أكثر من قطعتين هو: $$\begin{equation*} {13 \choose 3} - \left[{4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3}\right] \end{equation*}$$ وهو $$\begin{equation*} 286 - [480 - 210 + 16] = 0 \text{.} \end{equation*}$$

وهذا منطقي: لا توجد أي طريقة لتوزيع 10 قطع من البسكويت على 4 أطفال مع ضمان ألّا يحصل أحدهم على أكثر من قطعتين. ومن المُفاجئ قليلًا أنّ $$\begin{equation*} {13 \choose 3} = \left[{4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3}\right] \text{,} \end{equation*}$$ لكن بما أنّ مبدأ الاحتواء والاستبعاد يعمل، فلا بدّ أن تتحقّق هذه المساواة.

وإلّا ظننت أنّ هذه المسائل لها دائمًا حلولٌ أسهل، فتأمّل المثال التالي.

المثال 3.8.3.

سبق (المثال 3.5.6) أن حسبنا عدد حلول المعادلة $$\begin{equation*} x_1 + x_2 + x_3 + x_4 + x_5 = 13 \text{,} \end{equation*}$$ حيث $x_i \ge 0$ لكل $x_i\text{.}$

كم من تلك الحلول يحقّق $0 \le x_i \le 3$ لكل $x_i\text{?}$

الحل. علينا أن نطرح عدد الحلول التي تكون فيها قيمة متغيّر واحد أو أكثر أكبر من 3. وسنحتاج إلى استخدام مبدأ الاحتواء والاستبعاد، لأن عدّ الحلول التي يكون فيها كلٌّ من المتغيّرات الخمسة منفصلًا أكبر من 3 يحسب الحلول مرّاتٍ متعددة. وهذا ما تحصل عليه:

• مجموع الحلول: ${17 \choose 4}\text{.}$
• الحلول التي يكون فيها $x_1 > 3\text{:}$ ${13 \choose 4}\text{.}$ أعطِ $x_1$ أربع وحدات أولًا؛ ثم وزّع الوحدات التسع الباقية على المتغيّرات الخمسة.
• الحلول التي يكون فيها $x_1 > 3$ و$x_2 > 3\text{:}$ ${9 \choose 4}\text{.}$ فبعد أن تعطي $x_1$ أربع وحدات وأخرى أربع لـ$x_2\text{,}$ لا يبقى لديك سوى 5 وحدات لتوزيعها.
• الحلول التي يكون فيها $x_1 > 3\text{,}$ $x_2 > 3$ و$x_3 > 3\text{:}$ ${5 \choose 4}\text{.}$
• الحلول التي يكون فيها $x_1 > 3\text{,}$ $x_2 > 3\text{,}$ $x_3 > 3\text{,}$ و$x_4 > 3\text{:}$ 0.

علينا أيضًا أن نأخذ في الحسبان أننا يمكننا اختيار أيٍّ من المتغيّرات الخمسة بدل $x_1$ أعلاه (وعندئذٍ سيكون هناك ${5 \choose 1}$ نتيجة من هذا النوع)، وأي زوج من المتغيّرات بدل $x_1$ و$x_2$ (${5 \choose 2}$ نتيجة) وهكذا. وبسبب هذا يحدث الازدواج في العدّ، فنحتاج إلى استخدام مبدأ الاحتواء والاستبعاد. ومجتمعةً لدينا أنّ عدد الحلول التي تحقّق $0 \le x_i \le 3$ هو $$\begin{equation*} {17 \choose 4} - \left[{5\choose 1}{13 \choose 4} - {5 \choose 2}{9 \choose 4} + {5 \choose 3}{5 \choose 4}\right] = 15 \text{.} \end{equation*}$$

قسم فرعي: عدّ التبديلات غير المطابقة

استكشف!

في مزحة ختّجك، تقرّر تبديل لوحات الأسماء على أبواب أساتذتك الخمسة المفضّلين لديك. وكي لا يشعر أيٌّ منهم بالإقصاء، تريد أن تتأكّد من أن جميع اللوحات تنتهي على الباب الخطأ. في كم طريقة يمكن إنجاز ذلك؟

وللاستخدام المتقدّم لمبدأ الاحتواء والاستبعاد تطبيقات تتجاوز العصي والحصى. فالتبادل غير المطابق (derangement) لعناصر $n$ وهي $\{1,2,3,\ldots, n\}$ هو تبديل لا يثبت فيه أي عنصر في موضعه. فمثلًا، هناك $6$ تبديلات للعناصر الثلاثة $\{1,2,3\}\text{:}$: $$\begin{equation*} 123 ~~ 132 ~~ 213 ~~ 231 ~~ 312 ~~ 321 \text{.} \end{equation*}$$ لكن معظم هذه التبديلات فيه عنصر واحد أو أكثر ثابت: $123$ فيه العناصر الثلاثة كلها ثابتة لأنّ العناصر الثلاثة كلها في مواضعها الأصلية، و$132$ فيه العنصر الأول ثابت (1 في موضعه الأصلي الأول)، وهكذا. وفي الواقع، التبادلات غير المطابقة الوحيدة لثلاثة عناصر هي $$\begin{equation*} 231 \text{ and } 312 \text{.} \end{equation*}$$

وإن صعدنا إلى 4 عناصر، فهناك 24 تبديلًا (لأنّ لدينا 4 خيارات للعنصر الأول، و3 خيارات للعنصر الثاني، وخيارين للعنصر الثالث، فلا يتبقّى سوى خيار واحد للعنصر الأخير). كم منها تبديلات غير مطابقة؟ فإن أكتبتَ جميعَ التبديلات الـ24 الـ24 واستبعدت منها التي ليست تبادلات غير مطابقة، فسيتبقّى لديك 9 تبادلات غير مطابقة فقط. ولنرَ كيف يمكننا الحصول على هذا العدد باستخدام مبدأ الاحتواء والاستبعاد.

المثال 3.8.4.

كم عدد التبديلات غير المطابقة لعناصر 4؟

الحل. نعدّ جميع التبديلات ونطرح منها التي ليست تبادلات غير مطابقة. هناك $4! = 24$ تبديلًا لعناصر 4. وحتى يكون التبديل ليس تبادلًا غير مطابق، فلا بدّ أن يكون أحد العناصر الأربعة ثابتًا على الأقل. وهناك ${4 \choose 1}$ خيارًا لأي عنصر مفرد نثبّته. وبعد تثبيته، علينا إيجاد تبديل للعناصر الثلاثة الأخرى. وهناك $3!$ تبديلًا على 3 عناصر.

لكننا الآن حسبنا عددًا أكبر من اللازم من التبديلات غير المطابقة، فيلزم أن نطرح تلك التبديلات التي تثبّت عنصرين. وهناك ${4 \choose 2}$ خيارًا لأي عنصرين نثبّتهما، ثم لكل زوج $2!$ تبديلًا للعناصر الباقية. لكن هذا يخصم أكثر مما ينبغي، فنضيف التبديلات التي تثبّت 3 عناصر، أي ${4 \choose 3}1!$ منها جميعًا. وأخيرًا نطرح التبديلات الـ${4 \choose 4}0!$ (تذكّر أنّ $0! = 1$) التي تثبّت العناصر الأربعة كلها. ومجتمعةً نحصل على أن عدد التبديلات غير المطابقة لعناصر 4 هو: $$\begin{equation*} 4! - \left[{4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4}0!\right] = 24 - 15 = 9 \text{.} \end{equation*}$$

وبالطبع يمكننا استخدام صيغة مشابهة لعدّ التبديلات غير المطابقة لأي عدد من العناصر. لكن كلما زاد عدد العناصر طالت الصيغة. وإليك مثالًا آخر:

المثال 3.8.5.

يحضر خمسة سادة حفلةً ويتركون قبّعاتهم عند الباب. وفي نهاية الحفلة، يأخذون القبّعات بسرعة وهم خارجون. في كم طريقة مختلفة يمكن أن يحدث ذلك بحيث لا يغادر أيٌّ من السادة بقبّته الخاصة؟

الحل. نحن نعدّ التبادلات غير المطابقة على 5 عناصر. هناك $5!$ طريقة للسادة ليأخذوا القبّعات بأي ترتيب — لكن كثيرًا من هذه التبديلات تنتهي بأن يحصل أحدهم على قبّته الخاصة. لذا نطرح كل الطرق التي يحصل فيها رجل واحد أو أكثر على قبّته الخاصة. وبعبارة أخرى، نطرح التبادلات غير المطابقة. ويتطلب ذلك مبدأ الاحتواء والاستبعاد. ومن ثمّ فإن الإجابة هي: $$\begin{equation*} 5! - \left[{5 \choose 1}4! - {5 \choose 2}3! + {5 \choose 3}2! - {5 \choose 4}1! + {5 \choose 5}0!\right] \text{.} \end{equation*}$$

قسم فرعي: عدّ الدوال

استكشف!

1. خذ جميع الدوال $f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\text{.}$ كم عدد الدوال إجمالًا؟ وكم منها أحادية (injective)؟ تذكّر أن الدالة أحادية إذا كان كل مُدخَل يُرسَل إلى مُخرَج مختلف.
2. خذ جميع الدوال $f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}\text{.}$ كم من الدوال الأحادية له الصفة $f(x) \ne x$ لأي $x \in \{1,2,3,4,5\}\text{?}$

يدّعي صديقك أن الإجابة هي: $$\begin{equation*} 5! - \left[ {5\choose 1}4! - {5 \choose 2}3! + {5\choose 3}2! - {5 \choose 4}1! + {5\choose 5}0! \right] \text{.} \end{equation*}$$

اشرح لماذا هذا صحيح. 3. تذكّر أنّ الدالة الشاملة (surjection) هي الدالة التي ينتمي كل عنصر من مجموعة قيمها إلى مداها. كم عدد الدوال $f: \{1,2,3,4,5\} \to \{1,2,3,4,5\}$ الشاملة؟ استخدم مبدأ الاحتواء والاستبعاد!

لقد رأينا في هذا الفصل كلّه أنّ كثيرًا من مسائل العدّ يمكن إعادة صياغتها كمسائل عدّ دوال ذات صفات معيّنة. وهذا منطقي، لأن كثيرًا من مسائل العدّ يمكن تصوّرها على صورة عدّ الطرق التي تُسند بها عناصر مجموعة إلى عناصر مجموعة أخرى.

المثال 3.8.6.

تقرّر التنازل عن مجموعة ألعاب الفيديو لديك لتتفرّغ بشكل أفضل لوقتك في دراسة الرياضيات المتقدّمة. في كم طريقة يمكنك ذلك، شريطة:

1. تريد توزيع ألعاب PS4 الثلاثة المختلفة لديك على 5 أصدقاء، بحيث لا يحصل أي صديق على أكثر من لعبة واحدة؟
2. تريد توزيع ألعاب 3DS الثماني المختلفة لديك على 5 أصدقاء؟
3. تريد توزيع ألعاب SNES الثماني المختلفة لديك على 5 أصدقاء، بحيث يحصل كل صديق على لعبة واحدة على الأقل؟

في كل حالة، صُغ سؤال العدّ بوصفه مسألة عدّ دوال.

الحل.

1. علينا استخدام الألعاب الثلاث (لنسمّها 1 و2 و3) بصفته النطاق، والأصدقاء الخمسة (a,b,c,d,e) كمجموعة القيم (وإلا فلم تكن الدالة معرّفة على النطاق كله حين لا يحصل صديق على أي لعبة). إذن كم عدد الدوال التي نطاقها $\{1,2,3\}$ ومجموعة قيمها $\{a,b,c,d,e\}\text{?}$ الإجابة لذلك هي $5^3=125\text{,}$ لأننا يمكننا إسناد أيٍّ من 5 عناصر لتكون صورة 1، وأيٍّ من 5 عناصر لتكون صورة 2، وأيٍّ من 5 عناصر لتكون صورة 3.

لكن هذه ليست الإجابة الصحيحة لمسألة العدّ لدينا، لأن إحدى هذه الدوال هي $f= \twoline{1\amp 2\amp 3}{a\amp a\amp a}\text{;}$ فيمكن لصديق واحد أن يحصل على أكثر من لعبة واحدة. وما نريده حقًا هو عدّ الدوال الأحادية. وهذا يعطي $P(5,3) = 60$ دالة، وهي الإجابة على مسألة العدّ لدينا. 2. مرة أخرى، علينا استخدام الألعاب الثماني بصفته النطاق، والأصدقاء الخمسة كمجموعة القيم. ونحن نعدّ جميع الدوال، إذن عدد طرق توزيع الألعاب هو $5^8\text{.}$ 3. هذا السؤال أصعب. استخدم الألعاب بصفته النطاق والأصدقاء كمجموعة القيم (والعكس لن يعطي دالة). إن ضمان حصول كل صديق على لعبة واحدة على الأقل يعني أن كل عنصر من مجموعة القيم ينتمي إلى المدى. وبعبارة أخرى، نحن نبحث عن دوال شاملة. فكيف تعدّ تلك؟

لقد رأينا في المثال 3.2.13 كيف نعدّ جميع الدوال (باستخدام مبدأ الضرب)، وفي المثال 3.4.7 تعلّمنا كيف نعدّ الدوال الأحادية (باستخدام التبديلات). أما الدوال الشاملة فليست سهلة العدّ إلى هذا الحدّ (إلا إذا كان حجم النطاق أصغر من مجموعة القيم، وعندئذٍ لا توجد أي منها).

الفكرة هي عدّ الدوال التي ليست شاملة، ثم طرح ذلك من العدد الكلي للدوال. وهذا يعمل جيدًا جدًا عندما تحتوي مجموعة القيم على عنصرين:

المثال 3.8.7.

كم عدد الدوال $f: \{1,2,3,4,5\} \to \{a,b\}$ الشاملة؟

الحل. هناك $2^5$ دالة إجمالًا، لكل عنصر من عناصر النطاق الخمسة خياران إلى أين يُرسَل. الآن من بين هذه الدوال، يجب أن تستبعد الدوال التي ليست شاملة عنصرًا واحدًا أو أكثر من مجموعة القيم من المدى. فابدأ أولًا بالنظر في الدوال التي لا ينتمي فيها $a$ إلى المدى. ولا يحدث هذا إلا بطريقة واحدة: يُرسَل كل شيء إلى $b\text{.}$ أو بدلًا من ذلك يمكننا استبعاد $b$ من المدى. عندئذٍ يُرسَل كل شيء إلى $a\text{,}$ فهناك دالة واحدة فقط من هذا النوع. وهذه هي الطرق الوحيدة التي يمكن أن تكون فيها دالة غير شاملة (لا توجد دالة تستبعد كليًا $a$ و$b$ من المدى)، ومن ثمّ هناك بالضبط $2^5 - 2$ دالة شاملة.

وعندما تكون هناك ثلاثة عناصر في مجموعة القيم، أصبح لدينا الآن ثلاثة خيارات لعنصر مفرد يُستبعد من المدى. وإضافة إلى ذلك، يمكننا اختيار أزواج من عنصرين لاستبعادهما من المدى، ويجب أن نتأكّد من عدم الازدواج في عدّها. لقد حان وقت مبدأ الاحتواء والاستبعاد!

المثال 3.8.8.

كم عدد الدوال $f: \{1,2,3,4,5\} \to \{a,b,c\}$ الشاملة؟

الحل. ابدأ من جديد بالعدد الكلي للدوال: $3^5$ (إذ يمكن لكلٍّ من عناصر النطاق الخمسة أن يُرسَل إلى أيٍّ من عناصر مجموعة القيم الثلاثة). والآن نعدّ الدوال التي ليست شاملة.

ابدأ باستبعاد $a$ من المدى. عندئذٍ لدينا خياران ($b$ أو $c$) إلى أين يُرسَل كل عنصر من عناصر النطاق الخمسة. ومن ثمّ هناك $2^5$ دالة تستبعد $a$ من المدى. وبالمثل، هناك $2^5$ دالة تستبعد $b\text{,}$ وأخرى $2^5$ تستبعد $c\text{.}$ الآن، هل حسبنا جميع الدوال التي ليست شاملة؟ نعم، لكننا في الواقع حسبنا بعضها أكثر من مرة. فمثلًا، الدالة التي تُرسِل كل شيء إلى $c$ كانت إحدى الدوال الـ$2^5$ التي حسبناها حين استبعدنا $a$ من المدى، وأيضًا إحدى الدوال الـ$2^5$ التي حسبناها حين استبعدنا $b$ من المدى. وعلينا أن نطرح كل الدوال التي تستبعد عنصرين تحديدًا من المدى. هناك دالة واحدة حين نستبعد $a$ و$b$ (فكل شيء يُرسَل إلى $c$)، ودالة واحدة حين نستبعد $a$ و$c\text{,}$ ودالة واحدة حين نستبعد $b$ و$c\text{.}$

نحن نستخدم مبدأ الاحتواء والاستبعاد: لعدّ الدوال التي ليست شاملة، جمعنا الدوال التي تستبعد $a\text{,}$ و$b\text{,}$ و$c$ على حدة؛ ثم طرحنا الدوال التي تستبعد أزواجًا من العناصر. ثم نضيف الدوال التي تستبعد مجموعات من ثلاثة عناصر، إلا أنه لا توجد دوال من هذا النوع. ونجد أن عدد الدوال التي ليست شاملة هو $$\begin{equation*} 2^5 + 2^5 + 2^5 - 1 - 1 - 1 + 0 \text{.} \end{equation*}$$

ولعلّ طريقة أكثر وصفًا لكتابة ذلك هي $$\begin{equation*} {3 \choose 1}2^5 - {3 \choose 2}1^5 + {3 \choose 3}0^5 \text{.} \end{equation*}$$ لأن كلًّا من الـ$2^5$ كان نتيجة اختيار عنصر واحد من عناصر مجموعة القيم الثلاثة لاستبعاده من المدى؛ وكلٌّ من الـ$1^5$ الثلاثة كان نتيجة اختيار عنصرين من عناصر مجموعة القيم الثلاثة لاستبعادهما. وكتابة $1^5$ بدلًا من 1 منطقية أيضًا: لدينا خيار واحد إلى أين يُرسَل كل عنصر من عناصر النطاق الخمسة.

والآن يمكننا أخيرًا عدّ عدد الدوال الشاملة: $$\begin{equation*} 3^5 - \left[{3 \choose 1}2^5 - {3 \choose 2}1^5\right] = 150 \text{.} \end{equation*}$$

قد يقلقك أن يكون عدّ الدوال الشاملة عندما تحتوي مجموعة القيم على أكثر من 3 عناصر مملًّا إلى حدّ كبير. فنحن بحاجة إلى استخدام مبدأ الاحتواء والاستبعاد، لكن مع أكثر من 3 مجموعات تكون صيغة المبدأ طويلة جدًا. غير أنّنا حالفنا الحظ. فكما رأينا في المثال أعلاه، فإن عدد الدوال التي تستبعد عنصرًا مفردًا من المدى هو نفسه أيًّا كان العنصر المفرد المستبعَد. وبالمثل، فإن عدد الدوال التي تستبعد زوجًا من العناصر سيكون نفسه لكل زوج. ومع مجموعات قيم أكبر، سنرى السلوك نفسه مع مجموعات من 3 و4 وعناصر أكثر مستبعدة. فبدلًا من جمع كل واحد من هذه وطرحه على حدة، يمكننا ببساطة أن نجمعها كلها أو نطرحها دفعةً واحدة، إذا كنت تعرف عددها. وهذا يعمل تمامًا كما عمل مع أنواع مسائل العدّ الأخرى في هذا القسم، إلا أنّ حجم التوليفات المختلفة من المجموعات أصبح عددًا أُسًّا أُسّ، بدلًا من معامل ثنائي أو مضروب. وإليك ما يحدث مع $4$ و$5$ عناصر في مجموعة القيم.

المثال 3.8.9.

1. كم عدد الدوال $f: \{1,2,3,4,5\} \to \{a,b,c,d\}$ الشاملة؟
2. كم عدد الدوال $f: \{1,2,3,4,5\} \to \{a,b,c,d,e\}$ الشاملة؟

الحل.

1. هناك $4^5$ دالة إجمالًا؛ وسنطرح الدوال التي ليست شاملة. يمكننا استبعاد أيٍّ من عناصر مجموعة القيم الأربعة، ويؤدي ذلك إلى إبقائنا مع $3^5$ دالة لكل عنصر مستبعَد. وهذا يحسب عددًا أكبر من اللازم، فنطرح الدوال التي تستبعد عنصرين من عناصر مجموعة القيم الأربعة، فيعطي كل زوجٍ $2^5$ دالة. لكن هذا يستبعد عددًا أكبر من اللازم، فنضيف الدوال التي تستبعد ثلاثة عناصر من عناصر مجموعة القيم الأربعة، فيعطي كل ثلاثيٍّ $1^5$ دالة. هناك ${4 \choose 1}$ مجموعة من الدوال تستبعد عنصرًا مفردًا، و${4 \choose 2}$ مجموعة من الدوال تستبعد زوجًا من العناصر، و${4 \choose 3}$ مجموعة من الدوال تستبعد ثلاثيًا من العناصر. وهذا يعني أن عدد الدوال التي ليست شاملة هو: $$\begin{equation*} {4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5 \text{.} \end{equation*}$$ ومن ثمّ يمكننا القول إن عدد الدوال الشاملة هو: $$\begin{equation*} 4^5 - \left[{4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5\right] \text{.} \end{equation*}$$
2. عدد الدوال الشاملة هو: $$\begin{equation*} 5^5 - \left[{5 \choose 1}4^5 - {5 \choose 2}3^5 + {5 \choose 3}2^5 - {5 \choose 4}1^5\right] \text{.} \end{equation*}$$ أخذنا العدد الكلي للدوال $5^5$ وطرحنا كل ما ليس شاملًا. هناك ${5 \choose 1}$ طريقة لاختيار عنصر مفرد من مجموعة القيم لاستبعاده من المدى، ولكلٍّ منها $4^5$ دالة. لكن هذا يسبّب ازدواجًا في العدّ، فنستخدم مبدأ الاحتواء والاستبعاد ونطرح الدوال التي تستبعد عنصرين من المدى: هناك ${5 \choose 2}$ خيارًا للعنصرين المستبعَدين، ولكل زوج $3^5$ دالة. وهذا يزيل عددًا أكبر من اللازم من الدوال، فنضيف الدوال التي تستبعد 3 عناصر من المدى: ${5 \choose 3}$ خيارًا لأي 3 نستبعدها، ثم $2^5$ دالة لكل اختيار للعناصر. وأخيرًا نطرح الدالة الواحدة التي تستبعد 4 عناصر لكلٍّ من خيارات ${5 \choose 4}$ للعناصر الأربعة.

وإذا حسبت هذا العدد بدقّة، ستحصل على 120 دالة شاملة. ويصدُف أن تكون هذه القيمة أيضًا هي قيمة $5!\text{.}$ وقد يبدو هذا تطابقًا مدهشًا حتى تدرك أن كل دالة شاملة $f:X \to Y$ لها $\card{X} = \card{Y}$ منتهية لا بدّ أن تكون تقابلية. وعدد الدوال التقابلية هو دائمًا $\card{X}!$ في هذه الحالة. وما لدينا هنا هو برهان تركيبي (combinatorial proof) للهوية التالية: $$\begin{equation*} n^n - \left[{n\choose 1}(n-1)^n - {n \choose 2}(n-2)^n + \cdots + {n \choose n-1}1^n \right] = n! \text{.} \end{equation*}$$

لقد رأينا أنّ عدّ الدوال الشاملة مثالٌ آخر جميل على الاستخدام المتقدّم لمبدأ الاحتواء والاستبعاد. كذلك يتبيّن أنّ عدّ الدوال الأحادية معادلٌ لعدد التبديلات، في حين إنّ عدّ جميع الدوال له حلٌّ يشبه مسائل العدّ التي يكون فيها الترتيب مهمًّا والتكرار مسموحًا (مثل عدّ عدد الكلمات التي يمكنك تكوينها من مجموعة أحرف معطاة).

وهذه ليست مجرّد أمثلة أخرى قليلة على التقنيات التي طوّرناها في هذا الفصل. بل على العكس تمامًا: كل ما تعلّمناه في هذا الفصل هو مثالٌ على عدّ الدوال!

المثال 3.8.10.

كم عدد الكلمات ذات الـ5 أحرف التي يمكنك تكوينها باستخدام الأحرف الثمانية $a$ إلى $h\text{?}$ وكم عددها التي لا تحتوي على أحرف مكرّرة؟

الحل. ليس مفاجئًا في هذه المرحلة أن هناك $8^5$ كلمة، و$P(8,5)$ كلمة بلا أحرف مكرّرة. والجديد هنا أننا نعدّ الدوال بالفعل. بالنسبة للمسألة الأولى، نعدّ جميع الدوال من $\{1,2,\ldots, 5\}$ إلى $\{a,b,\ldots, h\}\text{.}$ والأعداد في النطاق تمثّل موضع الحرف في الكلمة؛ ومجموعة القيم تمثّل الحرف الذي يمكن إسناده إلى ذلك الموضع. وإذا سألنا عن عدم تكرار الأحرف، فسنطلب دوال أحادية.

فإذا كانت $A$ و$B$ أيّ مجموعتين بحيث $|A| = 5$ و$|B| = 8\text{,}$ فإن عدد الدوال $f: A \to B$ هو $8^5$ وعدد الدوال الأحادية هو $P(8,5)\text{.}$ فإذا استطعت تمثيل مسألة العدّ لديك كمسألة عدّ دوال، فإن معظم العمل يكون قد أُنجز.

المثال 3.8.11.

كم عدد المجموعات الجزئية لـ$\{1,2,\ldots, 9\}\text{?}$ وكم عدد السلاسل الثنائية ذات 9 خانات (بأي وزن)؟

الحل. رأينا في القسم 3.1 أنّ الإجابة على كلا السؤالين هي $2^9\text{,}$ لأننا يمكننا أن نقول نعم أو لا (أو 0 أو 1) لكل عنصر من عناصر المجموعة التسعة (المواضع في السلسلة الثنائية). لكن $2^9$ أيضًا تبدو الإجابة التي تحصل عليها من عدّ الدوال. وفي الواقع، إن عددت جميع الدوال $f: A \to B$ بحيث $|A| = 9$ و$|B| = 2\text{,}$ فهذا بالضبط ما تحصل عليه.

هذا منطقي! لتكن $A = \{1,2,\ldots, 9\}$ و$B = \{y, n\}\text{.}$ فنحن نُسند لكل عنصر من عناصر المجموعة إجابة نعم أو لا. أو بصيغة السلاسل الثنائية، نأخذ المواضع التسعة في السلسلة الثنائية نطاقًا، والمجموعة $\{0,1\}$ كمجموعة قيم.

حتى الآن لم نستخدم الدالة بوصفها نموذجًا للمعاملات الثنائية (التركيبات). فكّر لحظة في العلاقة بين التركيبات والتبديلات، تحديدًا بين ${9 \choose 3}$ و$P(9,3)\text{.}$ نحن نملك بالفعل نموذجًا داليًا لـ$P(9,3)\text{.}$ وهذا هو عدد الدوال الأحادية من مجموعة حجمها 3 (قل $\{1,2,3\}$ إلى مجموعة حجمها 9 (قل $\{1,2,\ldots, 9\}$)، إذ هناك 9 خيارات إلى أين يُرسَل العنصر الأول من النطاق، ثم 8 خيارات فقط للعنصر الثاني، و7 خيارات للعنصر الثالث. فمثلًا، قد تبدو الدالة كالتالي: $$\begin{equation*} f(1) = 5 \qquad f(2) = 8 \qquad f(3) = 4 \text{.} \end{equation*}$$

وهذه دالة مختلفة عن: $$\begin{equation*} f(1) = 4 \qquad f(2) = 5 \qquad f(3) = 8 \text{.} \end{equation*}$$

والآن يعدّ $P(9,3)$ هاتين الدالتين كنافتين مختلفتين على نحو صحيح، لكن ${9\choose 3}$ سيعدّهما (وغيرهما) كنتيجة واحدة فقط. وفي الواقع، من منظور الدوال فإن ${9 \choose 3}$ لا يعدّ سوى عدد المدى الممكن للدوال الأحادية. ولا ينبغي أن يكون هذا مفاجئًا لأن المعاملات الثنائية تعدّ المجموعات الجزئية، والمدى مجموعة جزئية ممكنة من مجموعة القيم. 5 أما التفسير الأكثر رصانةً رياضيًا للتركيبات فهو أننا نعرّف دالتين أحاديتين بأنهما مكافئتان إذا كان لهما المدى نفسه، ثم نعدّ عدد أصناف التكافؤ بمفهوم التكافؤ هذا.

ورغم أنه من الممكن تفسير التركيبات بوصفها دوالًا، فإن النصيحة الأفضل هي أن تستخدم التركيبات (أو العصي والحصى) عندما لا تكون الدوال هي الطريقة المناسبة تمامًا لتفسير سؤال العدّ.