عدّ المجموعات المتعدّدة

القسم 3.5 عدّ المجموعات المتعدّدة

الأهداف

بعد إتمام هذا القسم، ينبغي أن تتمكّن من فعل ما يلي.

1. أن تميّز مسائل العدّ التي يمكن تمثيل نتائجها بمجموعات متعدّدة (multisets).
2. أن تمثّل نتائج مسائل العدّ باستخدام المجموعات المتعدّدة ومخططات العصي والحصى.
3. أن تحلّ مسائل العدّ باستخدام العصي والحصى.

معاينة القسم

استكشف!

تأتي حبّات «سكيتلز» بخمسة نكهات مختلفة. كم عدد الأكوام المختلفة الممكنة من 8 حبّات سكيتلز؟

لنفترض أنّك خبزت 8 كعكبات متطابقة لتوزيعها على أفضل خمسة معلّمي الرياضيات المتقطّعة الذين تفضّلهم. كم عدد طرق توزيع الكعكبات؟

لماذا إجابتا سؤالَي العدّ أعلاه متطابقتان؟

لقد تعلّمنا الآن كيف نحلّ أنواعًا كثيرة من مسائل العدّ. فإذا أمكن تمثيل كلّ ناتج في مجموعة النتائج التي نعدّها على صورة تتابع، فإنّنا نعدّه تبديلًا (permutation) (إذا لم تتكرّر الحدود في التتابع) أو نستعمل مبدأ الضرب (product principle) (إذا تكرّرت). وإذا كنّا نعدّ نتائج لا نميّز فيها بين الترتيبات المختلفة للحدود (إذا لم يكن الترتيب مهمًّا)، فإنّنا نتعامل مع الناتج على صورة مجموعة ونعدّه توافيق (combination). غير أنّ المجموعات لا تسمح أبدًا بتكرار عنصر؛ فكلّ عنصر إما في المجموعة أو ليس فيها.

وهكذا هناك ثغرة واضحة في ترسانتنا في العدّ. ماذا لو أردنا عدّ نتائج تكون مجموعات من حدود لا نميّز فيها بين الترتيب الذي تظهر به الحدود، لكن يمكن أن تحتوي على الحدود أكثر من مرّة؟ وبعبارات أخرى، كيف يمكننا إكمال الجدول التالي؟

	ترتيبات متمايزة؟
	نعم	لا
التكرار مسموح	تتابعات: مبدأ الضرب $n^k$
بلا تكرار	تتابعات: تبديلات $P(n,k)$	مجموعات: توافيق $\binom{n}{k}$

ما نريد عدّه هو بنية تشبه المجموعة نوعًا ما، لكنّها بنية تسمح فعلًا لعناصر المجموعة بأن تظهر أكثر من مرّة. وتُسمّى هذه البنى المجموعات المتعدّدة (multisets).

تعريف 3.5.1.

المجموعة المتعدّدة (multiset) هي مجموعة غير مرتّبة من العناصر، يمكن لكلّ عنصر فيها أن يظهر أيّ عدد من المرّات. ويُسمّى عدد مرّات ظهور العنصر تعدّده (multiplicity).

وتُكتب المجموعات المتعدّدة بالترميز نفسه المستعمل للمجموعات: قائمة مفصولة بفواصل داخل أقواس معقوفة، مثل $\{1, 2, 2, 5\}\text{.}$

في هذا القسم، سنستكشف كيف يمكن استعمال المجموعات المتعدّدة لتمثيل طيف واسع من مسائل العدّ. ثمّ سنضع طريقة لترجمة المجموعات المتعدّدة إلى نوع خاصّ من السلاسل الثنائية (bit-strings) حتى نتمكّن من استعمال الأعداد في مثلث باسكال (Pascal’s triangle) لعدّ عدد المجموعات المتعدّدة.

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

1.

اعثر على مجموعة من الأشياء المتطابقة، ربّما عملات معدنية أو مكعّبات سكّر. واحضر أيضًا بضعة فواصل،قد تكون أعوان أسنان، أو كبريت، أو أقلام.

رتّب العملات المعدنية في صفّ واحد. وسنقسم الصفّ إلى عدد من المجموعات بوضع أعواه الأسنان في الفراغات بين العملات المعدنية. وسنميّز بين الترتيب الذي تأتي به المجموعات. فمثلًا، تبديلان مختلفان لتقسيم 7 عملات معدنية إلى 4 مجموعات سيبدوان هكذا:

وسنسمح لواحدة أو أكثر من المجموعات أن لا تحتوي على أيّ عملات معدنية (بوضع عودَي أسنان متجاورَين، أو قبل جميع العملات أو بعدها).

وبرصف العدد الصحيح من العملات المعدنية والعصي، عدّ عدد الطرق التي يمكنك بها تقسيم صفّ من العملات المعدنية إلى العدد المعطى من المجموعات.

(a)

إذا أردتَ تقسيم صفّ من العملات المعدنية إلى 4 مجموعات، فكم عدد أعواه الأسنان التي ستحتاجها؟

(b)

كم عدد الطرق لفصل صفّ من ثلاث عملات معدنية إلى مجموعتين؟

(c)

كم عدد الطرق لفصل صفّ من أربع عملات معدنية إلى مجموعتين؟

(d)

كم عدد الطرق لفصل صفّ من خمس عملات معدنية إلى مجموعتين؟

(e)

كم عدد الطرق لفصل صفّ من ثلاث عملات معدنية إلى ثلاث مجموعات؟

(f)

كم عدد الطرق لفصل صفّ من أربع عملات معدنية إلى ثلاث مجموعات؟

(g)

كم عدد الطرق لفصل صفّ من خمس عملات معدنية إلى ثلاث مجموعات؟

(h)

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

تلميح. ابحث في مثلث باسكال عن الأعداد التي وجدتَها في الأسئلة السابقة.

قسم فرعي: خذ بعض البسكويت

تأمّل مسألة العدّ التالية:

لديك 7 قطع بسكويت لتوزيعها على 4 أطفال. كم عدد الطرق التي يمكنك فعل ذلك بها؟

خذ لحظة لتفكّر في كيفية حلّ هذه المسألة. ويمكنك أن تفترض أنّه مقبول أن تعطي طفلًا لا بسكويت. كذلك، قطع البسكويت كلّها متطابقة، والترتيب الذي توزّع به لا يهمّ (فإعطاء البسكويت للطفل الثاني قبل الطفل الأوّل لا يُحسب ناتجًا منفصلًا عن العكس).

وقبل حلّ المسألة، إليك إجابة خاطئة: قد تخمّن أنّ الإجابة ينبغي أن تكون $4^7$ لأنّه لكلّ واحدة من قطع البسكويت السبع، هناك 4 خيارات للأطفال الذين يمكنك إعطاؤهم إيّاها. هذا منطقي، لكنه خاطئ. ولرؤية السبب، تأمّل بعض النتائج الممكنة: يمكننا أن نُسند القطع الستّ الأولى إلى الطفل A، والقطعة السابعة إلى الطفل B. ونتيجة أخرى تُسند القطعة الأولى إلى الطفل B والقطع الستّ الباقية إلى الطفل A. وكلتا النتيجتين مُدرَجتان في إجابة $4^7$. لكن في مسألة العدّ لدينا، النتيجتان في الواقع واحدة – يحصل الطفل A على ستّ قطع والطفل B على قطعة واحدة. وكانت هذه ستكون الإجابة الصحيحة لو كانت قطع البسكويت كلّها مختلفة، لكنها ليست كذلك.

فكيف تبدو النتائج في الواقع؟ وكيف يمكننا تمثيلها؟ وتتمثل إحدى الطرق في كتابة الناتج على صورة سلسلة من أربعة أعداد هكذا: $$\begin{equation*} 3112\text{,} \end{equation*}$$ وهي تمثّل النتيجة التي يحصل فيها الطفل الأوّل على 3 قطع، والطفلان الثاني والثالث على قطعة واحدة لكلٍّ منهما، والطفل الرابع على قطعتين. وبهذا التمثيل، يكون الترتيب الذي تظهر به الأعداد مهمًّا. فـ 1312 نتيجة مختلفة، لأن الطفل الأوّل يحصل على قطعة واحدة بدلًا من 3. ويمكن أن يكون كلّ عدد في السلسلة أيّ عدد صحيح بين 0 و7. لكنّ الإجابة ليست $7^4\text{.}$ فنحن بحاجة إلى أن يكون مجموع الأعداد هو 7.

وهناك طريقة أخرى لتمثيل النتائج وهي كتابة سلسلة من سبعة أحرف: $$\begin{equation*} \text{ABAADCD}\text{,} \end{equation*}$$ وهي تمثّل أن القطعة الأولى تذهب إلى الطفل A، والثانية إلى الطفل B، والثالثة والرابعة إلى الطفل A، وهكذا. وفي الحقيقة، هذه النتيجة مطابقة للنتيجة السابقة—يحصل A على 3 قطع، ويحصل B وC على قطعة لكلٍّ منهما، ويحصل D على قطعتين. ويمكن أن يكون كلٌّ من الأحرف السبعة في السلسلة أيًّا من الأحرف الأربعة الممكنة (حرف واحد لكلّ طفل)، لكنّ عدد هذه السلاسل ليس $4^7\text{,}$ لأنّ الترتيب هنا لا يهمّ. وفي الحقيقة، هناك طريقة أخرى لكتابة النتيجة نفسها وهي $$\begin{equation*} \text{AAABCDD}\text{.} \end{equation*}$$

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

إذن لدينا الآن طريقتان مفيدتان للنظر في النتائج.

1. على صورة مجموعة متعدّدة تتضمّن 7 عناصر، كلٌّ منها أحد الأطفال الأربعة (أو حرف يمثّل اسمه). فمثلًا، $$\begin{equation*} \{A, A, A, B, C, D, D\}\text{.} \end{equation*}$$ وكلّما كان الطفل موجودًا في المجموعة المتعدّدة، فإنّ ذلك يعني أنّ ذلك الطفل يحصل على قطعة بسكويت، ومن ثمّ فإنّ تعدّد الطفل في المجموعة المتعدّدة هو عدد قطع البسكويت التي يحصل عليها.
2. على صورة سلسلة من 4 أعداد غير سالبة مجموعها 7. فمثلًا، $$\begin{equation*} 3112\text{.} \end{equation*}$$ ويمثّل موضع العدد في السلسلة الطفل، ويمثّل العدد نفسه عدد قطع البسكويت التي يحصل عليها ذلك الطفل.

وقبل أن نفكّر في كيفية عدّ عدد النتائج الممثَّلة بهذه الطريقة، إليك مثالَين إضافيَّين من مسائل العدّ يمكننا تمثيلهما بهاتين الطريقتين.

المثال 3.5.2.

تمسك بيدك حفنة من عشر حبّات حلوى من كيس يحتوي على ستّ نكهات. اكتب ثلاثة نتائج ممكنة باستخدام كلٍّ من المجموعات المتعدّدة والسلاسل العددية.

الحل. المجموعات المتعدّدة هي الطريقة الأكثر طبيعية في التفكير في هذه المسألة، إذ كلّ حفنة هي مجموعة متعدّدة من النكهات. فمثلًا يمكننا أن يكون لدينا، $$\begin{equation*} \{R, R, G, G, G, B, B, B, B, Y\} \end{equation*}$$ أي أنّك حصلت على حبّتين حمراوين، وثلاث خضراء، وأربع زرقاء، وحبة صفراء واحدة (ولا بنفسجية ولا برتقالية)، أو $$\begin{equation*} \{R, R, R, R, R, R, R, R, R, R\} \end{equation*}$$ أي أنّك حصلت على عشر حبّات حمراء. ويمكنك أيضًا أن تكون لديك $$\begin{equation*} \{R, G, B, Y, P, O, O, O, O, O\} \end{equation*}$$ أي أنّ لديك حبّة واحدة من كلٍّ من الأحمر والأخضر والأزرق والأصفر، وخمس حبّات برتقالية.

والتتابعات المقابلة المكوّنة من ستّة أعداد مجموعها 10 هي $$\begin{equation*} 2,3,4,1,0,0; \qquad 10,0,0,0,0,0; \qquad 1,1,1,1,1,5\text{.} \end{equation*}$$ (أضفنا فواصل بين الأعداد لأنّ ليس كلّ عدد رقمًا من رقم واحد.) ولاحظ أنّ هذا التمثيل يحتاج أن نتّفق على ترتيب ثابت للنكهات، وهو في هذه الحالة لم يكن أبجديًا، بل كان نفس الترتيب الذي استعملناه عند سرد المجموعات المتعدّدة.

المثال 3.5.3.

لديك 12 نسخة متطابقة من كتاب الرياضيات المتقطّعة المفضّل لديك، وتريد وضعها على 5 رفوف كتب. اكتب ثلاثة نتائج ممكنة باستخدام كلٍّ من المجموعات المتعدّدة والسلاسل العددية.

الحل. هنا تكون السلاسل العددية أكثر طبيعية، إذ يمكننا ببساطة أن نقول كم كتابًا يذهب إلى كلّ رفّ. وسنحتاج إلى 5 أعداد مجموعها 12. فمثلًا، يمكننا أن يكون لدينا

1. $3,3,3,2,1\text{,}$ أي 3 كتب على الرفّ الأوّل، و3 على الثاني، و3 على الثالث، و2 على الرابع، وواحد على الخامس.
2. $0,0,12,0,0\text{,}$ أي أنّ الكتب الاثنَي عشر كلّها على الرفّ الأوسط.
3. $1,1,1,1,8\text{,}$ أي كتاب واحد على كلٍّ من الرفوف الأربعة الأولى و8 على الأخير.

والمجموعات المتعدّدة المقابلة هي

1. $\{1,1,1,2,2,2,3,3,3,4,4,5\}\text{,}$ أي أنّ الرفّ 1 يُسند إليه كتاب ثلاث مرّات، والرفّ 2 يُسند إليه كتاب ثلاث مرّات، وهكذا. ولاحظ أنّ هناك 12 عنصرًا في المجموعة المتعدّدة، عنصر واحد لكلّ كتاب. والأعداد هنا تمثّل الرفوف؛ وتعدّد العدد هو عدد الكتب على ذلك الرفّ.
2. $\{3,3,3,3,3,3,3,3,3,3,3,3\}\text{.}$ الرفّ الوحيد في المجموعة المتعدّدة هو الرفّ 3، بتعدّد 12، أي أنّ الرفّ 3 يحصل على 12 كتابًا.
3. $\{1,2,3,4,5,5,5,5,5,5,5,5\}\text{.}$ هنا يحصل الرفّ 1 على كتاب واحد، والرفّ 2 على كتاب واحد، والرفّ 3 على كتاب واحد، والرفّ 4 على كتاب واحد، والرفّ 5 على البقيّة.

يمكن أيضًا طرح هذا المثال الأخير بوصفه مسألة عن حلّ معادلات ذات حلول صحيحة غير سالبة. وبشكل خاصّ، كان يمكننا أن نطلب حلول المعادلة $a+b+c+d+e = 12\text{.}$ وتخيّل كلّ متغيّر على أنّه يحدّد عدد الكتب التي تذهب إلى كلّ رفّ. وسنطرح أسئلة مباشرة بهذا الأسلوب، لكنّ إدراك كيفية تمثيل الأسئلة الأخرى على صورة معادلة كهذه قد يكون مفيدًا.

قسم فرعي: تمثيل المجموعات المتعدّدة بالسلاسل الثنائية

لنعد الآن إلى مسألة توزيع 7 قطع بسكويت على 4 أطفال الأصلية، ولنعدّ فعلًا عدد النتائج.

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

وهذا في جوهره ما فعلناه مع المجموعات المتعدّدة، لكنّنا اضطررنا إلى استعمال سلاسل من أعداد غير سالبة تتجاوز 0 و1، إذ يمكن أن يظهر عنصر في المجموعة المتعدّدة أكثر من 0 أو 1 مرّة. لكن إذا استطعنا ترجمة تلك السلاسل العددية إلى نوع آخر من السلاسل الثنائية، لاستطعنا استعمال مثلث باسكال لعدّ عدد المجموعات المتعدّدة.

وإليك كيف يمكننا فعل ذلك. فمعطاة مجموعة متعدّدة مثل $$\begin{equation*} \{A, A, A, B, C, D, D\} \end{equation*}$$ لدينا تمثيل على صورة تتابع أعداد هو $$\begin{equation*} 3,1,1,2\text{.} \end{equation*}$$ إذن، بدلًا من الأعداد منفردة، نكتب كلّ عدد على صورة تتابع من ذلك العدد من الآحاد. فتصير هذه العبارة $$\begin{equation*} 111,1,1,11\text{.} \end{equation*}$$ وهذا مُربك بعض الشيء لأنّنا نستعمل الفواصل للفصل بين الأعداد. ولأجل توضيح الأمر أكثر، فلننتقل إلى رمزين مختلفين. سنسمّيهما العصي والحصى، حيث يمثّل الحجر الرقم 1 ويمثّل العصا الفاصلة. فتصير المتتابعة $$\begin{equation*} 111,1,1,11 \end{equation*}$$ هي $$\begin{equation*} \o\o\o|\o|\o|\o\o\text{.} \end{equation*}$$ وهذه سلسلة من عشرة رموز، 7 منها حصى و3 منها عصي.

هذا رائع! أيًّا كان الرمزان اللذان نستعملهما (قد تراهما أيضًا مسمّيين النجوم والحواجز أو الكرات والصناديق)، يمكننا استعمال مثلث باسكال لعدّ عدد طرق ترتيبها. وعدد السلاسل الثنائية ذات 10 خانات ذات وزن 3 (أو وزن 7) هو $\binom{10}{3} = 120\text{.}$

وبعبارات البسكويت، يمكننا تفسير مخطط العصي والحصى هذا على أنّه يقول: بعد كم قطعة من البسكويت نتوقّف عن إعطاء الطفل الأوّل ونبدأ بإعطاء الطفل الثاني. ثمّ بعد كم ننتقل إلى الطفل الثالث؟ وبعد كم ننتقل إلى الرابع؟ إذن $$\begin{equation*} \o\o\o|\o|\o|\o\o \end{equation*}$$ يعني أنّ ثلاث قطع تذهب إلى الطفل الأوّل؛ ثمّ ننتقل ونعطي قطعة واحدة إلى الطفل الثاني، ثمّ ننتقل، وواحدة إلى الطفل الثالث، ثمّ ننتقل، واثنتين إلى الطفل الرابع. ولاحظ أنّنا نحتاج إلى 7 حصى و3 عصي – حجر واحد لكلّ قطعة بسكويت، وعصا واحدة لكلّ انتقال بين الأطفال، ومن ثمّ عدد عصٍ أقلّ بواحد من عدد الأطفال (فلا نحتاج إلى الانتقال بعد الطفل الأخير – فقد انتهينا).

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

وطريقة أخرى (وأعمّ) للتعامل مع هذه المسألة المعدَّلة هي أن تعطي كلّ طفل قطعة بسكويت أوّلًا. والآن يمكن توزيع قطع البسكويت الثلاث الباقية على الأطفال الأربعة دون قيود. فلدينا 3 حصى و3 عصي، أي ما مجموعه 6 رموز، 3 منها يجب أن تكون حواجز. فمرة أخرى نرى أنّ هناك ${6 \choose 3}$ طرق لتوزيع البسكويت.

ويمكن استعمال العصي والحصى في مسائل عدّ غير الأطفال والبسكويت. وإليك بعض الأمثلة:

المثال 3.5.4.

مقهى المثلجات الرياضي المفضّل لديك يقدّم 10 نكهات. كم عدد المخفوقات التي يمكنك صنعها باستخدام 6 كرات بالضبط، من غير أن تكون بالضرورة متمايزة؟ فالترتيب الذي تضيف به النكهات لا يهمّ (فستُدمج على أيّ حال)، لكن يُسمح لك بالتكرار. فمثلًا، أحد المخفوقات الممكنة هو ثلاث كرات شوكولاتة وكارتان كرز وكرة نعناع بالشوكولاتة.

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

والآن بعد أن اطمأنّنا إلى أنّ لدينا العدد الصحيح من العصي والحصى، نُجيب عن السؤال ببساطة: هناك 6 حصات و9 حواجز، أي 15 رمزًا. وعلينا اختيار 9 منها لتكون حواجز، إذن عدد المخفوقات الممكنة هو $$\begin{equation*} \binom{15}{9}\text{.} \end{equation*}$$

المثال 3.5.5.

كم عدد أرقام الهواتف المكوّنة من 7 خانات والتي تكون أرقامها غير متزايدة؟ أي أنّ كلّ رقم أصغر أو مساوٍ للذي يسبقه.

الحل. علينا اتّخاذ قرار بشأن 7 أرقام، إذن سنستعمل 7 حصى. وستمثّل العصي انتقالًا من كلّ رقم من رقم واحد ممكن إلى الرقم الأصغر الذي يليه. فرقم الهاتف 866-5221 يمثّله مخطط العصي والحصى التالي $$\begin{equation*} |\o||\o\o|\o|||\o\o|\o|\text{.} \end{equation*}$$

وهناك 10 خيارات لكلّ رقم (0-9)، إذن علينا الانتقال بين الخيارات تسع مرّات. ولدينا 7 حصى و9 حواجز، إذن العدد الكلي لأرقام الهواتف هو $$\begin{equation*} {16 \choose 9}\text{.} \end{equation*}$$

المثال 3.5.6.

كم عدد الحلول الصحيحة للمعادلة $$\begin{equation*} x_1 + x_2 + x_3 + x_4 + x_5 = 13\text{.} \end{equation*}$$

(الحلّ الصحيح للمعادلة هو حلٌّ يجب أن تكون فيه المجهولات ذات قيم صحيحة.)

1. حيث $x_i \ge 0$ لكلّ $x_i\text{?}$
2. حيث $x_i > 0$ لكلّ $x_i\text{?}$
3. حيث $x_i \ge 2$ لكلّ $x_i\text{?}$

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

1. إذا كان $x_i$ يساوي 0 أو أكثر، فإنّنا في الحالة القياسية بلا قيود. ومن ثمّ يمكن ترتيب 13 حجرًا و4 عصي بـ${17 \choose 4}$ طريقة.
2. والآن يجب أن يكون كلّ متغيّر 1 على الأقلّ. إذن أعطِ كلّ متغيّر وحدة واحدة لاستيفاء ذلك القيد. والآن تبقّى 8 حصى، وما زالت هناك 4 حواجز، إذن عدد الحلول هو ${12 \choose 4}\text{.}$
3. والآن يجب أن يكون كلّ متغيّر 2 أو أكثر. إذن قبل أيّ عدّ، أعطِ كلّ متغيّر وحدتين. ولدينا الآن 3 حصى باقية و4 حواجز، إذن هناك ${7 \choose 4}$ حلولًا.

العدّ باستخدام الدوال.

كثير من مسائل العدّ في هذا القسم قد تبدو أوّل الأمر أمثلة على عدّ الدوال (functions). فبعد كلّ شيء، عندما نحاول عدّ عدد طرق توزيع البسكويت على الأطفال، فإنّنا نُسند كلّ قطعة بسكويت إلى طفل، تمامًا كما تُسند عناصر نطاق الدالة إلى عناصر مجموعة قيمها. غير أنّ عدد طرق إسناد 7 قطع بسكويت إلى 4 أطفال هو ${10 \choose 7} = 120\text{,}$ في حين أنّ عدد الدوال $f: \{1,2,3,4,5,6,7\} \to \{a,b,c,d\}$ هو $4^7 = 16384\text{.}$ فما الذي يحدث هنا؟

فحين نعدّ الدوال، فإنّنا نعتبر الدالتين التاليتين، على سبيل المثال، مختلفتين: $$\begin{equation*} f = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{a \amp b \amp c \amp c \amp c \amp c \amp c} \qquad g = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{b \amp a \amp c \amp c \amp c \amp c \amp c}\text{.} \end{equation*}$$ لكنّ هاتين الدالتين ستقابلان توزيع البسكويت نفسه: يحصل كلٌّ من الطفلين $a$ و$b$ على قطعة بسكويت واحدة، ويحصل الطفل $c$ على البقيّة (ولا شيء للطفل $d$).

والمقصود: عناصر النطاق متمايزة، أمّا قطع البسكويت فغير متمايزة. وهذا يماثل التمييز بين التبديلات (مثل عدّ الدوال) والتوافيق (لا شيء من ذلك).

أسئلة القراءة

1.

أيّ من أسئلة العدّ التالية ليس مثالًا على سؤال كنت ستستعمل العصي والحصى لحلّه؟

• كم عدد الطرق التي يمكنك بها توزيع ستّ هدايا فريدة على ثلاثة أصدقاء؟
• صحيح. لأنّ الهدايا متمايزة، لدينا ثلاثة خيارات للهدية الأولى، وثلاثة للثانية، وهكذا، فيكون الجواب $3^6\text{.}$
• كم عدد الطرق التي يمكنك بها توزيع ستّ هدايا متطابقة على ثلاثة أصدقاء؟
• يمكنك هنا استعمال العصي والحصى: استعمل عصين لفصل أصدقائك الثلاثة، وستّ حصات للهدايا.
• كم عدد التوليفات المختلفة من الأعداد التي يمكنك الحصول عليها إذا رميت ثلاث قطع نرد متطابقة ذات 6 أوجه؟
• استعمل خمس عصٍّ لفصل القيم الستّ على قطع النرد. ويمثّل كلّ حجر إحدى قطع النرد المتطابقة.
• كم عدد مخفوقات الثلاث كرات المختلفة التي يمكنك صنعها عندما يمكن أن تكون كلّ كرة آيس كريم إحدى ستّ نكهات مختلفة؟
• استعمل خمس عصٍّ وثلاث حصات!

2.

حين تعدّ النتائج باستعمال العصي والحصى، هل الترتيب مهمّ؟ هل تسمح بالتكرار؟ وماذا تقصد بإجاباتك (ترتيب ماذا، تكرار ماذا)؟

3.

ما الأسئلة التي تدور في ذهنك بعد قراءة هذا القسم؟ اكتب على الأقلّ سؤالًا واحدًا عن محتوى هذا القسم يثير فضولك.