خلاصة الفصل

كمّ موكبًا من البسكويت على هيئة حيوانات، يحوي 6 قطع، تستطيع أن تصطفّه؟
كمّ موكبًا من 6 قطع بسكويت على هيئة حيوانات تستطيع أن تصطفّه بحيث تظهر الحيوانات بترتيب أبجدي؟
في كم طريقة تستطيع أن تصطفّ 6 حيوانات مختلفة بترتيب أبجدي؟
في كم طريقة تستطيع أن تصطفّ 6 حيوانات مختلفة إن كان ترتيبها كيفما اتّفق؟
في كم طريقة تستطيع أن تعطي 6 أطفال قطعةً واحدة من البسكويت على هيئة حيوان لكلٍّ منهم؟
في كم طريقة تستطيع أن تعطي 6 أطفال قطعةً واحدة من البسكويت على هيئة حيوان لكلٍّ منهم بحيث لا يحصل طفلان على الحيوان نفسه؟
في كم طريقة تستطيع أن توزّع 6 زرافات على 10 أطفال؟
اكتب سؤالًا عن إعطاء الأطفال بسكويت على هيئة حيوانات، يكون جوابه ${10\choose 6}\text{.}$

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

تذكّر أنّك تعدّ عدد العناصر في قائمة نتائج (list of outcomes). اكتب جزءًا من هذه القائمة. واكتب عنصرًا في منتصف القائمة – فعلى أيّ أساس تقرّر ما إذا كان عنصرك موجودًا في القائمة حقًّا؟ وهل يمكن أن تحصل على هذا العنصر أكثر من مرّة باستخدام إجابتك المقترحة؟
إذا كان توليد عنصر في القائمة يتضمّن انتقاء شيءٍ ما (مثلًا: انتقاء حرف، أو انتقاء موضعٍ لوضع حرف فيه، إلخ)، فهل يمكن تكرار الأشياء التي تنتقيها؟ تذكّر أنّ التبديلات (permutations) والتركيبات (combinations) تنتقي عناصرَ من مجموعة دون تكرار.
هل يهمّ الترتيب؟ كن حذرًا هنا، وتأكّد ممّا تعنيه إجابتك حقًّا. فعادةً نقول إنّ الترتيب يهمّ متى حصلت على نتائج مختلفة حين تُنتقى الأشياء نفسها بترتيبات مختلفة. أمّا التركيبات (combinations) و«العصي والحجارة» (sticks and stones) فتُستعمل حين لا يهمّ الترتيب.
هناك أربع حالاتٍ محتملة فيما يتعلّق بالترتيب والتكرار. فإن كان الترتيب مهمًّا وكان التكرار مسموحًا، بدا الجواب على صورة $n^k\text{.}$ وإن كان الترتيب مهمًّا ولم يكن التكرار مسموحًا، يكون لدينا $P(n,k)\text{.}$ وإن لم يكن الترتيب مهمًّا وكان التكرار مسموحًا، فاستعمل «العصي والحجارة» (sticks and stones). وإن لم يكن الترتيب مهمًّا ولم يكن التكرار مسموحًا، فاستعمل ${n\choose k}\text{.}$ واحذر: إنّ هذا لا ينطبق إلّا حين تنتقي أشياء، وينبغي أن تتأكّد من معرفتك الدقيقة لما تنتقيه قبل تحديد الحالة التي أنت فيها.
فكّر في كيفية تمثيل مسألة العدّ التي تتناولها بدلالة مجموعات (sets) أو دوالّ (functions). فنحن نعرف كيف نعدّ مختلف أنواع المجموعات ومختلف أصناف الدوالّ.
كما رأينا في البراهين التوافقية (combinatorial proofs)، فإنّك تستطيع غالبًا حلّ مسألة عدّ بأكثر من طريقة واحدة. افعل ذلك، وقارن بين إجاباتك العددية. فإن لم تتطابق، فهناك خلل ما.

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

وفي الفصل القادم، سنتعامل مع أسئلة العدّ من اتجاهٍ مختلفٍ تمامًا، وبذلك نُجيب في الوقت نفسه عن عددٍ لا نهائي من أسئلة العدّ. وسننشئ تتابعات (sequences) من الإجابات عن أسئلة متّصلة.

تمارين: مراجعة الفصل

1.

لديك 8 هدايا لتوزّعها على 4 من أطفالك. في كم طريقة يمكن تنفيذ ذلك إذا:

كانت الهدايا متطابقة، وحصل كلُّ طفل على هدية واحدة على الأقلّ؟
كانت الهدايا متطابقة، ولم يحصل بعض الأطفال على أي هدية؟
كانت الهدايا فريدة، ولم يحصل بعض الأطفال على أي هدية؟
كانت الهدايا فريدة وحصل كلُّ طفل على هدية واحدة على الأقلّ؟

2.

لكلّ من مسائل العدّ التالية، حدّد ما إذا كان الجواب هو ${10\choose 4}\text{,}$ أو $P(10,4)\text{,}$ أم لا شيء منهما. فإن كان جوابك «لا شيء منهما»، فاذكر ما ينبغي أن يكون عليه الجواب بدلًا من ذلك.

كمّ أقصر مسار شبكي (lattice path) يوجد من $(0,0)$ إلى $(10,4)\text{?}$
إن كانت لديك 10 ربطات عنق على شكل فراشة، وأردت انتقاء 4 منها للأسبوع القادم، فكم خيارًا لديك؟
لنفترض أنّ لديك 10 ربطات عنق على شكل فراشة، وأنّك سترتدي رابطةً مختلفة في كلٍّ من الأيام الأربعة القادمة. فكم خيارًا لديك؟
إن أردت أن ترتدي 4 من ربطات عنق العشر خاصّتك الأسبوع القادم (من الاثنين إلى الأحد)، في كم طريقة يمكن إنجاز ذلك؟
من بين مجموعةٍ من 10 زملاء صفّ، في كم طريقة يمكنك أن ترتّب أصدقاءك الأربعة الأوائل؟
إن جاء 10 طلاب إلى مكتب الأستاذ، ولا يتّسع في الوقت نفسه سوى 4 منهم، فكم تركيبة مختلفة (combination) من 4 طلاب يمكن أن يرى الأستاذ أوّلًا؟
كم كلمة ذات 4 أحرف يمكن تكوينها من أوّل 10 أحرف من الأبجدية؟
في كم طريقة يمكنك تكوين الكلمة «cake» من أوّل 10 أحرف من الأبجدية؟
كم طريقة هناك لتوزيع 10 تفاحات متطابقة على 4 أطفال؟
إن كان لديك 10 أطفال (وتعيش في حذاء) و4 أنواع من حبوب الإفطار، في كم طريقة يمكن لأطفالك أن يتناولوا وجبة الإفطار؟
في كم طريقة يمكنك ترتيب أربع خاناتٍ قيمتها 1 بالضبط في سلسلة من 10 خانات ثنائية؟
تريد انتقاء 4 أعداد متمايزة كلٌّ منها من خانة واحدة لتكون اختياراتك في يانصيب اللوتو. فكم خيارًا لديك؟
10 أطفال يريدون المثلجات، ولديك 4 أنواع. فكم طريقة هناك لتوفير للأطفال قدر المثلجات الذي يريدونه؟
كم دالة 1-1 (أحادية) (injective) من $\{1,2,\ldots, 10\}$ إلى $\{a,b,c,d\}\text{?}$
كم دالة مغطّية (surjective) من $\{1,2,\ldots, 10\}$ إلى $\{a,b,c,d\}\text{?}$
كلُّ واحدة من ربطات عنق العشر خاصّتك تتوافق مع 4 أزواج من حمّالات السروال. فكم تنكبة (outfit) يمكنك أن تكوّنها؟
بعد الحفل، يختار كلُّ واحد من الأطفال العشرة هديةً واحدة من بين 4 هدايا الحفل. فكم نتيجة هناك؟
كم مجموعة جزئية (subset) مؤلّفة من 6 عناصر لمجموعة $\{1,2,\ldots, 10\}$
في كم طريقة يمكنك تقسيم 11 طفلًا إلى 5 فرقٍ مسمّاة؟
كم حلًّا هناك للمعادلة $x_1 + x_2 + \cdots + x_5 = 6$ حيث يكون كلُّ $x_i$ عددًا صحيحًا غير سالب؟
فرقة الموسيقى التي تنتمي إليها تخرج في جولة. وهناك 10 مدنٍ تبعد بمسافةٍ يمكن قيادتها، لكنّ الوقت لا يكفي إلاّ للعزف في 4 منها. فكم خيارًا لديك لمدن جولتك؟
في كم طريقة مختلفة يمكنك أن تعزف في المدن الأربع التي اخترتها؟
من بين أنواع حبوب الإفطار العشرة المتوفّرة، تريد أن تتناول 4 أطباق. في كم طريقة يمكنك أن تفعل ذلك؟
هناك 10 أنواع من البسكويت متاحة. تريد أن تصنع كومةً من 4 قطع بسكويت. كم كومة مختلفة يمكنك أن تصنعها؟
من منزلك عند (0,0) تريد الذهاب إمّا إلى محلّ الكعك المحلّى عند (5,4) أو إلى المحلّ الآخر عند (3,6). كم مسارًا يمكنك أن تسلك؟
كم عددًا من 10 خانات لا يحتوي على سلسلة فرعية (sub-string) من 4 خاناتٍ متكرّرة؟

3.

تذكّر، أنّك تملك 4 ربطات عنق عادية و8 ربطات على شكل فراشة. وتدرك أنّه لا بأس أن ترتدي أكثر من ربطتين في مقابلتك مع كلية المهرّجين.

عليك انتقاء بعض ربطات عنق لارتدائها. وكلُّ شيء جائز، من عدم ارتداء أي رابطة إلى ارتداء الربطات كلّها. فكم خيارًا لديك؟
إن أردت ارتداء رابطة عادية واحدة على الأقلّ ورابطة فراشة واحدة على الأقلّ، مع استعدادك لارتداء كلّ ربطاتك، فكم خيارًا لديك في تحديد الربطات التي سترتديها؟
كم خيارًا لديك في تحديد الربطات التي سترتديها إن ارتديت 3 بالضبط من الـ 4 ربطات العادية و2 من الـ 8 ربطات الفراشة؟
بعد أن تنتقي 3 ربطات عادية و2 ربطات فراشة، في كم ترتيب يمكنك أن ترتدي الربطات، على اعتبار أنّ عليك أن تكون إحدى ربطات الفراشة في الأعلى؟

4.

اطرح مسألة عدّ يكون جوابها $8\cdot 3 \cdot 3 \cdot 5\text{.}$ ثمّ اطرح مسألة أخرى يكون جوابها $8 + 3 + 3 + 5\text{.}$

5.

Consider أعدادًا على الصورة $\alpha = a_1a_2a_3\dots a_n\text{,}$ من $n$ خانة، على نحوٍ تكون فيه كلُّ خانة من المجموعة ${\left\{1,2,3,4,5,6,7,8\right\}}\text{.}$ فمثلًا، إذا كان $n = 4\text{,}$ فإنّ العدد $\alpha = a_1a_2a_3a_4$ ذا 4 خانات من المجموعة ${\left\{1,2,3,4,5,6,7,8\right\}}\text{.}$

ولنفترض $n = 11\text{.}$

كم عددًا من هذا النوع؟
كم عددًا من هذا النوع يكون مجموع خاناته زوجيًّا؟
كم عددًا من هذا النوع يحتوي على خاناتٍ زوجية أكثر من الخانات الفردية؟

6.

في استطلاعٍ صغيرٍ حديثٍ لمسافري الطيران، قال 27 مسافرًا إنّهم سافروا على American خلال العام الماضي، وسافر 22 على Jet Blue، وسافر 30 على Continental. ومن بين هؤلاء، أفاد 13 مسافرًا بأنّهم سافروا على American وJet Blue، و12 بأنّهم سافروا على Jet Blue وContinental، و11 بأنّهم سافروا على American وContinental. وكان 4 مسافرين قد سافروا على الخطوط الجوية الثلاث جميعًا.

كم مسافرًا شملهم الاستطلاع؟ (افترض أنّ النتائج أعلاه تمثّل الاستطلاع بأكمله.)

7.

تذكّر، إنّنا نقصد بـ $11$ -سلاسل البِت (bit strings) السلاسل المكوّنة من الخانات الثنائية، طولها 11.

كم سلسلةً $11$ -بت توجد إجمالًا؟
كم سلسلةً $11$ -بت وزنها (weight) 4؟
كم مجموعة جزئية (subset) من المجموعة {1,2,3,4,5,6,7,8,9,10,11} تحتوي على 4 عناصر بالضبط؟

8.

ما معامل $x^{11}$ في تمدّد (expansion) $(x+3)^{16} + x^3(x+5)^{20}\text{?}$

9.

كم كلمة ذات 11 حرفًا تحتوي على 3 حروفٍ مدّية بالضبط؟ (فمثلًا، كلمةٌ ذات 8 أحرف فيها 5 حروف مدّية هي «aaioobtt»؛ ولا تعتبر «y» حرفًا مدّيًا في هذا التمرين.)

وماذا لو لم يُسمح بتكرار الأحرف؟

10.

لكلٍّ ممّا يأتي، ابحث عن عدد أقصر المسارات الشبكية (lattice paths) من $(5,5)$ إلى $(10,10)$ بحيث:

تمرّ بالنقطة $(7,6)\text{.}$
تتجنّب (لا تمرّ) بالنقطة $(9,9)\text{.}$
تمرّ إمّا بالنقطة $(7,6)$ أو بالنقطة $(9,9)$ (أو كليهما).

11.

تقيم في مدينة الشبكة (Grid-Town) عند تقاطع الشارع الثاني مع الرابع، وتعمل في مبنى واقع عند تقاطع الشارع العشرين مع السادس عشر. فكم مسارًا هناك ينقلك من المنزل إلى العمل ثمّ يعيدك إلى المنزل، لكن عبر مسارٍ مختلف؟

12.

كم سلسلةً 5-بت تبدأ بـ $101$ أو تنتهي بـ $10$ أو كليهما؟

13.

كم سلسلةً 9-بت وزنها 7 تبدأ بـ $101$ أو تنتهي بـ $10$ أو كليهما؟

14.

نُصنّع كلماتٍ ذات 9 أحرف من مجموعة الحروف $a,b,c,d,e,f \dots\text{,}$ على نحوٍ لا نملك فيه إلّا أوّل 9 أحرف من الحروف، بحيث نستخدم جميع الأحرف.

كم كلمة ذات 9 أحرف يمكننا تكوينها من الحروف دون تكرار، ولا تحتوي على الكلمة الفرعية (sub-word) «bad» في مواضع متتالية من الحروف؟
كم كلمة لا تحتوي على الكلمة الفرعية «bad» في أحرفٍ ليست بالضرورة متتالية (لكنها بالترتيب)؟

15.

اشرح، باستعمال المسارات الشبكية، لماذا $\sum_{k=0}^n {n \choose k} = 2^n\text{.}$

16.

لنفترض أنّ لديك 19 ورقةً من فئة الدولار لتوزّعها كجوائزٍ لأفضل 6 طلاب في الرياضيات المتقطّعة. في كم طريقة يمكنك أن تفعل ذلك إذا:

حصل كلٌّ من الطلاب الستّة على دولار واحد على الأقلّ؟
لم يحصل بعض الطلاب على شيء؟
حصل كل طالب على دولار واحد على الأقلّ لكن لا يزيد على 8 دولارات؟

تلميح. استعمل «النجوم والأعمدة» (stars and bars).

17.

كم دالة $f: {\left\{1,2,3,4,5,6\right\}} \to {\left\{1,2,3,4,5,6\right\}}$ تحقّق الشروط التالية؟

$f(1) = 1$ أو $f(2) = 2$ (أو كلاهما)؟
$f(1) \ne 1$ أو $f(2) \ne 2$ (أو كلاهما)؟
$f(1) \ne 1$ و $f(2) \ne 2\text{,}$ و $f$ أحادية (injective)؟
$f$ مغطّية (surjective)، لكن $\forall x \in \{1,2,\dots, 6 \} \text{, } f(x) \ne x\text{?}$

18.

كم دالة تصوّر (map) ${\left\{1,2,3,4,5,6\right\}}$ onto ${\left\{1,2,3,4,5\right\}}$ (أي، كم دالة مغطّية (surjection) توجد)؟

19.

لشكر أستاذك في الرياضيات على عمله المذهل طوال الفصل الدراسي، قرّرت أن تخبز لأستاذك البسكويت. وأنت تعرف كيف تصنع 15 نوعًا مختلفًا من البسكويت.

إن أردت أن تعطي أستاذك 8 أنواعٍ مختلفة من البسكويت، فكم تركيبة مختلفة (combination) من أنواع البسكويت يمكنك أن تنتقي؟ اشرح إجابتك.
وحفاظًا على الأمر شائقًا، قرّرت أن تصنع عددًا مختلفًا من كل نوع من البسكويت. فإن أردت مرّة أخرى انتقاء 8 أنواعٍ من البسكويت، فكم طريقة يمكنك أن تنتقي بها أنواع البسكويت وتقرّر أيّها سيكون الأكثر، ثمّ الثاني الأكثر، إلخ؟ اشرح إجابتك.
لقد غيّرت رأيك مرّة أخرى. وهذه المرّة تقرّر أن تصنع ما مجموعه 22 قطعة بسكويت. ويمكن أن تكون كلُّ قطعة أيًّا من الأنواع الخمسة عشر التي تعرف كيف تخبزها (ويجوز أن تترك بعض الأنواع دون استعمال). فكم خيارًا لديك؟ اشرح.
وتدرك أنّ الخطة السابقة لم تراعِ مسألة العرض (presentation). وهذه المرّة، تريد مرّة أخرى أن تصنع 22 قطعة بسكويت، ويمكن أن تكون كلُّ قطعة أيًّا من أنواع البسكويت الخمسة عشر. لكنّك تخطّط الآن أن تشكّل البسكويت على صورة الأرقام 1، 2، ...، 22. فكم خيارًا لديك في تحديد أيّ أنواع البسكويت تُخبز في أيّ الأرقام؟ اشرح.
والخلل الوحيد في الخطة الأخيرة هو أنّ أستاذك قد لا يتاح له تذوّق الأنواع الخمسة عشر كلّها من البسكويت. فكم خيارًا لديك في تحديد أيّ أنواع البسكويت تُصنع في أيّ الأرقام، على اعتبار أنّ كل نوع من البسكويت ينبغي أن يكون حاضرًا مرّة واحدة على الأقلّ؟ اشرح.

20.

في أيّ أجزاء المسألة السابقة (التمرين 3.9.19) يكون من المعقول تأويل مسألة العدّ على أنّها عدُّ عددٍ ما من الدوالّ؟ اذكر ينبغي أن يكون النطاق (domain) وقيم الدوالّ (codomain)، وبيّن ما إذا كنت تعدّ كلَّ الدوالّ أم الدوالّ الأحادية (injections) أم المغطّية (surjections) أم شيئًا آخر.

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