التوافيق والتباديل

القسم 3.4 التوافيق والتباديل

الأهداف

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

1. أن تقرّر على الوجه الصحيح متى تستعمل توافيق ومتى تستعمل تباديل في حلّ مسألة عدّ.
2. أن تطبّق التوافيق أو التباديل الصحيحة لحلّ مسألة عدّ.
3. أن تشرح العلاقة بين التوافيق والتباديل ولماذا كانت صيغها صحيحة.

معاينة القسم

استكشف!

قرّرتَ أن تزيّن عصاك السحرية بشرائط من شريط لاصق ملوّن. لديك 10 ألوان مختلفة تختار من بينها، وستستخدم خمسة منها لتكوين خمسة خطوط ملوّنة مختلفة. كم عدد تصاميم العصا المختلفة الممكنة؟

ويُعطينا مبدأ الضرب طريقةً لعدّ عدد النتائج عندما يتكوّن كلّ ناتج من تجميع قطع أصغر. ومن الأمثلة النموذجية على ذلك عدّ عدد «الكلمات» ذات الأحرف الثلاثة؛ فكلّ ناتج (كلمة) نعدّه يتكوّن من تجميع ثلاث قطع أصغر (أحرف). وبما أنّ هناك 26 خيارًا لكلّ قطعة أصغر، فإنّ هناك $26\cdot 26\cdot 26 = 26^3$ ناتجًا ممكنًا.

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

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

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

لديك كومة من رقائق البوكر تأتي بخمسة ألوان مختلفة: الأحمر، والأزرق، والأخضر، والبنفسجي، والأصفر.

1.

كم عدد أكوام الرقائق ذات الرقيقتين الممكنة، على أن تكون الرقيقة السفلية حمراء أو زرقاء؟

(a)

اكتب جميع أكوام الرقائق ذات الرقيقتين الممكنة. فمثلًا، الكومة التي تكون فيها رقيقة حمراء في الأسفل ورقيقة خضراء في الأعلى يمكن كتابتها «RG».

(b)

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

(c)

وإذا استعملنا مبدأ الضرب، فهناك خيارات للرقيقة السفلية وخيارات للرقيقة العليا، فيكون هناك أكوام ممكنة.

2.

كم عدد الأكوام المختلفة ذات الرقائق الثلاث الممكنة إذا كانت الرقيقة السفلية حمراء أو زرقاء، والرقيقة العليا خضراء أو بنفسجية أو صفراء؟

تلميح. كيف يرتبط هذا السؤال بالسؤال السابق؟ هل هناك شيء يمكننا فعله بأكوام الرقائق العشر ذات الرقيقتين حتى نحوّلها إلى أكوام ذات ثلاث رقائق؟

3.

كم عدد الأكوام المختلفة ذات الرقائق الثلاث التي لا يتكرّر فيها أيّ لون؟

(a)

أوّلًا، كم عدد الأكوام ذات الرقائق الثلاث التي لا يتكرّر فيها لون، والتي يكون قاعها أزرق ووسطها أخضر؟

وكم عدد الأكوام ذات الرقائق الثلاث التي لا يتكرّر فيها لون، والتي يكون قاعها أزرق ووسطها أصفر؟

وفي الحقيقة، فإنّ أيّ كومة قاعها أزرق ووسطها لون آخر، تكون لها أكوام ممكنة.

(b)

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

وبالجمع بين هذا وجواب السؤال السابق، كم عدد الأكوام ذات الرقائق الثلاث التي لا يتكرّر فيها لون والتي قاعها أزرق؟

(c)

بالطبع، لم يكن علينا أن نبدأ بالأزرق في الأسفل. فكم عدد الخيارات التي لدينا للون الرققيقة السفلى؟

إذن كم عدد الأكوام المختلفة ذات الرقائق الثلاث التي لا يتكرّر فيها لون؟

(d)

كم عدد العصي المكوّنة من أربع رقائق التي لا يتكرّر فيها لون؟

4.

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

(a)

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

تلميح. مع هذه الألوان الثلاثة، كم عدد الخيارات لديك لأيّ رقيقة تكون في الأسفل؟ وفي الوسط؟ وفي الأعلى؟

(b)

كم عدد الأكوام المختلفة من الرقائق التي ينتج عنها التقاط الرقائق الحمراء والصفراء والخضراء؟

(c)

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

(d)

كم عدد الحصص المختلفة من الرقائق إذا أخذت أربع رقائق؟

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

التبادل هو إعادة ترتيب (محتملة) لمجموعة من الأشياء. فمثلًا، هناك 6 تباديل للحروف a, b, c: $$\begin{equation*} abc, ~~ acb, ~~ bac, ~~bca, ~~ cab, ~~ cba\text{.} \end{equation*}$$ وبعبارات بُنى المتقطعة، كلّ تبادل هو في الحقيقة تتابع أو متعدّد (tuple) بطول ثابت.

ونحن نعرف أنّنا أدرجناها جميعًا أعلاه —فهناك 3 خيارات للحرف الذي نضعه أوّلًا، ثم خياران للحرف الذي يأتي تاليًا، فلم يبقَ إلّا خيار واحد للحرف الأخير. ويقول مبدأ الضرب إنّه علينا أن نضرب $3\cdot 2 \cdot 1\text{.}$

مثال 3.4.1.

كم عدد التتابعات (التباديل) للحروف a, b, c, d, e, f؟

الحل. لا نريد بطبيء الحال أن نحاول إدراج كلّ التتابعات ذات الطول 6 من هذه الأحرف. لكن لو فعلنا ذلك، لكان علينا أن نختار حرفًا نكتبه أوّلًا. وهناك 6 خيارات لذلك الحرف. ولكلّ خيار للحرف الأوّل، هناك 5 خيارات للحرف الثاني (لا يمكننا تكرار الحرف الأوّل؛ فنحن نعيد ترتيب الأحرف ولا نملك سوى واحد من كلّ نوع)، ولكلّ واحد من تلك، هناك 4 خيارات للحرف الثالث، و3 خيارات للرابع، و2 الخامس، وأخيرًا خيار واحد فقط للحرف الأخير. إذن هناك $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$ تبادلًا للأحرف الستة.

وتكون هنا قطعة رمز مفيدة: $n!\text{,}$ وتُقرأ «مضروب $n$»، وهي حاصل ضرب جميع الأعداد الصحيحة الموجبة الأصغر من $n$ أو المساوية لها (ولأسباب ملائمة، نعرّف أيضًا 0! بأنه 1). إذن عدد تباديل الأحرف الستة، كما رأينا في المثال السابق، هو $6! = 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\text{.}$ وهذا يتعمّم:

نظرية 3.4.2. تباديل $n$ عنصرًا.

هناك $n! = n\cdot (n-1)\cdot (n-2)\cdot \cdots \cdot 2\cdot 1$ تبادلًا لـ$n$ عنصرًا (متميزة).

مثال 3.4.3. عدّ الدوال التقابلية.

كم عدد الدوال $f:\{1,2,\ldots,8\} \to \{1,2,\ldots, 8\}$ التي تكون تقابلية (bijective)؟

الحل. تذكّر ما معنى أن تكون الدالة تقابلية: يجب أن يكون كلّ عنصر في مجموعة القيم هو صورة عنصر واحد بالضبط من النطاق. وباستخدام الرمز ثنائي السطر (two-line notation)، يمكننا كتابة أحد هذه التقابلات على النحو $$\begin{equation*} f = \twoline{1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \amp 8} {3 \amp 1 \amp 5 \amp 8 \amp 7 \amp 6 \amp 2 \amp 4}\text{.} \end{equation*}$$ وما نفعله في الحقيقة هو مجرّد إعادة ترتيب عناصر مجموعة القيم، فنُنشئ بذلك تبادلًا لثمانية عناصر. وفي الواقع، مصطلح «التبادل» (permutation) مصطلح آخر يُستخدم لوصف الدوال التقابلية من مجموعة منتهية إلى نفسها.

وإن كنت تصدّق هذا، فإنّك ترى أنّ الجواب لا بدّ أن يكون $8! = 8 \cdot 7 \cdot\cdots\cdot 1 = 40320\text{.}$ ويمكنك أن ترى ذلك مباشرة أيضًا: فلكلّ عنصر من النطاق، علينا أن نختار عنصرًا متمايزًا من مجموعة القيم نُرسِل إليه. وهناك 8 خيارات لأين نُرسِل 1، ثم 7 خيارات لأين نُرسِل 2، وهكذا. ونضرب مستخدمين مبدأ الضرب.

وأحيانًا لا نريد أن نبدّل كلّ الأحرف/الأعداد/العناصر المعطاة لنا.

مثال 3.4.4.

كم عدد «الكلمات» ذات الأحرف الأربعة التي يمكنك صنعها من الأحرف a إلى g، من دون أحرف متكرّرة؟

الحل. هذا مثل مسألة تبديل أربعة أحرف تمامًا، غير أنّ لدينا الآن خيارات أكثر لكلّ حرف. بالنسبة إلى الحرف الأوّل، هناك 7 خيارات. ولكلّ واحد من تلك، هناك 6 خيارات للحرف الثاني. ثم هناك 5 خيارات للحرف الثالث و4 خيارات للحرف الأخير. وإجمالي عدد الكلمات هو $7\cdot 6\cdot 5 \cdot 4 = 840\text{.}$

وهذا ليس $7!$ لأنّنا لم نضرب قطّ في 3 أو 2 أو 1. لكن يمكننا كتابته باستخدام $7!$ إن شئنا، إذا ألغينا 3 و2 و1. وبذلك يمكننا كتابة الجواب على النحو $$\begin{equation*} \frac{7!}{3!} = \frac{7\cdot 6\cdot 5\cdot 4 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{\cancel{3} \cdot \cancel{2} \cdot \cancel{1}} = 7 \cdot 6 \cdot 5 \cdot 4\text{.} \end{equation*}$$

وبوجه عام، يمكننا أن نسأل: كم عدد التباديل الموجودة لـ$k$ من الأشياء عند اختيار تلك الأشياء من مجموعة أكبر من $n$ من الأشياء. (في المثال أعلاه، $k = 4\text{,}$ و$n = 7\text{.}$) ونكتب هذا العدد $P(n,k)$ ونسمّيه أحيانًا تبادل $k$ من $n$ عنصرًا.

ومن المثال أعلاه نرى أنّ لحساب $P(n,k)$ علينا تطبيق مبدأ الضرب على $k$ عددًا، بدءًا من $n$ والعدّ إلى الخلف. فمثلًا $$\begin{equation*} P(10, 4) = 10\cdot 9 \cdot 8 \cdot 7\text{.} \end{equation*}$$

ولاحظ أنّ $P(10,4)$ يبدو في البداية مثل $10!\text{,}$ لكنّنا نتوقّف بعد 7. ويمكننا محاسبة هذا «التوقّف» رسميًا بإلغاء الجزء الذي لا نريده من المضروب (factorial) بالقسمة: $$\begin{equation*} P(10,4) = \frac{10\cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{10!}{6!}\text{.} \end{equation*}$$

انتبه: المضروب في المقام ليس $4!$ بل هو $(10-4)!\text{.}$

تعريف 3.4.5. تباديل $k$ من $n$ عنصرًا.

$P(n,k)$ هو عدد تباديل $k$ من $n$ عنصرًا، أي عدد الطرق إلى ترتيب $k$ من الأشياء المختارة من $n$ عنصرًا متمايزًا.

نظرية 3.4.6.

عدد تباديل $k$ من $n$ عنصرًا هو $$\begin{equation*} P(n,k) = \frac{n!}{(n-k)!} = n(n-1)(n-2)\cdots (n-(k-1))\text{.} \end{equation*}$$

ولاحظ أنّه عندما $n = k\text{,}$ لدينا $P(n,n) = \frac{n!}{(n-n)!} = n!$ (لأنّنا عرّفنا $0!$ بأنه 1). وهذا منطقي —فقد سبق أن عرفنا أنّ $n!$ يعطي عدد تباديل الأشياء الـ$n$ جميعًا.

مثال 3.4.7. عدّ الدوال الأحادية.

كم عدد الدوال $f:\{1,2,3\} \to \{1,2,3,4,5,6,7,8\}$ التي تكون أحادية (injective)؟

الحل. لاحظ أنّه لا معنى لسؤالنا عن عدد التقابلات (bijections) هنا، إذ لا توجد منها (لأنّ مجموعة القيم أكبر من النطاق، فلا توجد دوال onto (surjections)). لكن كي تكون الدالة أحادية، لا يمكننا إلّا أن نستخدم عنصرًا من مجموعة القيم مرّة واحدة على الأكثر.

علينا أن نختار عنصرًا من مجموعة القيم ليكون صورة 1. وهناك 8 خيارات. ثم علينا أن نختار واحدًا من العناصر السبعة الباقية ليكون صورة 2. وأخيرًا، يجب أن يكون واحدٌ من العناصر الستة الباقية هو صورة 3. إذن إجمالي عدد الدوال هو $8\cdot 7 \cdot 6 = P(8,3)\text{.}$

وما تُظهره هذه الحالة على وجه العموم هو أنّ عدد الدوال الأحادية (injections) $f:A \to B\text{,}$ حيث $\card{A} = k$ و$\card{B} = n\text{,}$ هو $P(n,k)\text{.}$

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

لننظر في طريقة أخرى لعدّ التتابعات: أوّلًا نعدّ المجموعات، ثم نرتّبها.

مثال 3.4.8.

فريق كرة السلة لديك فيه 12 لاعبًا. وبافتراض أنّه يمكن للجميع اللعب في أيّ مركز، فكم عدد الطرق التي يمكنك بها اختيار 5 لاعبين ليكونوا في الملعب في الوقت نفسه؟

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

أوّلًا، إن أردنا فقط تحديد خمسة من الـ12 لاعبًا، فهذا مثل اختيار خمسة من 12 نوعًا من مكوّنات البيتزا (وإن كان أقلّ لذًا). نعرف أنّ عدد طرق ذلك هو $\binom{12}{5}$، ومن مثلث باسكال نعرف أنّ هذا العدد هو 792.

ومن جهة أخرى، إن أردنا اختيار خمسة لاعبين للمراكز الخمسة المختلفة، ... حسنًا، يمكننا أن نبدأ باختيار إحدى الـ792 مجموعة مختلفة من خمسة لاعبين، ثم نبدّلهم على المراكز الخمسة. فمن بين اللاعبين الخمسة على الملعب، نختار واحدًا ليكون نقطة الحماية، ثم واحدًا من الأربعة الباقين ليكون حارس التسديد، وهكذا. وهذا يعطينا $5\cdot 4\cdot 3\cdot 2\cdot 1 = 5!$ طريقة لترتيب اللاعبين. إذن فإنّ إجمالي عدد طرق اختيار خمسة لاعبين للمراكز الخمسة هو $$\begin{equation*} \binom{12}{5}\cdot 5! = 792\cdot 120 = 95,040\text{.} \end{equation*}$$

لحظة. كان بإمكاننا إيجاد ذلك العدد مباشرةً. فبدون اختيار اللاعبين الخمسة أوّلًا، لدينا 12 خيارًا لنقطة الحماية، ثم 11 خيارًا لحارس التسديد، وهكذا. إذن فإنّ إجمالي عدد طرق اختيار خمسة لاعبين للمراكز الخمسة هو ببساطة التبادل $$\begin{equation*} P(12,5) = 12\cdot 11\cdot 10\cdot 9\cdot 8 = 95,040\text{.} \end{equation*}$$ الحمد لله أنّ الجواب هو نفسه!

يبيّن المثال أعلاه طريقة ثانية لحساب عدد تبادلات $k$ عنصرًا من $n$ عنصرًا: أوّلًا نحدّد أيّ $k$ عنصرًا ستكون في التبادل، ثم نعدّ كم طريقة لترتيبها. فبعد أن اخترت مجموعة الـ$k$ عنصرًا، نعرف أنّ هناك $k!$ طريقة لترتيبها (تبادلها). لكن كيف تختار $k$ عنصرًا من الـ$n\text{?}$ لديك $n$ عنصرًا، وتحتاج إلى اختيار $k$ منها. ويمكنك ذلك بـ$\binom{n}{k}$ طريقة.

وباستعمال مبدأ الضرب للدمج بين الخطوتين، نحصل على صيغة أخرى لـ$P(n,k)\text{:}$ $$\begin{equation*} P(n,k) = \binom{n }{ k}\cdot k!\text{.} \end{equation*}$$

هذا هائل!

ولدينا أصلًا صيغة مغلقة لـ$P(n,k)$. ويمكننا التعويض بها: $$\begin{equation*} \frac{n!}{(n-k)!} = \binom{n}{k} \cdot k!\text{.} \end{equation*}$$

وإذا قسمنا بعد ذلك الطرفين على $k!\text{,}$ نحصل على صيغة مغلقة لـ$\binom{n}{k}\text{.}$

نظرية 3.4.9. الصيغة المغلقة لـ$\binom{n}{k}$.

$$\begin{equation*} \binom{n}{k} = \frac{n!}{(n-k)!k!} = \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k(k-1)(k-2)\cdots 1}\text{.} \end{equation*}$$

الاسم الآخر لمجموعات الأشياء التي يعدّها $\binom{n}{k}$ هو التوافيق. نقول إنّ $\binom{n}{k}$ يعدّ عدد التوافيق المكوّنة من $k$ عنصرًا من $n$ عنصرًا. وأحيانًا نستخدم حتى الرمز $C(n,k)$ بدلًا من $\binom{n}{k}\text{.}$

ومن الواضح أنّ التوافيق والتباديل مترابطة إلى حدٍّ كبير. فصيغتا عدّهما متشابهتان جدًا؛ إنّ الفرق هو وجود $k!$ إضافية في مقام $\binom{n}{k}\text{.}$ وهذه الـ$k!$ الإضافية تفسّر أنّ $\binom{n}{k}$ لا يميّز بين الترتيبات المختلفة التي يمكن أن تظهر بها العناصر الـ$k$. فنحن نكتفي بتحديد (أو اختيار) الـ$k$ عنصرًا، لا بترتيبها.

مثال 3.4.10.

قرّرتَ تنظيم أمسيّة عشاء. فرغم أنّك شديد المشهورة ولديك 14 صديقًا مختلفًا، فإنّ لديك عددًا من الكراسي يكفي لدعوة 6 منهم فقط.

1. كم عدد الخيارات المتاحة لديك لأيّ 6 أصدقاء ستدعوهم؟
2. وماذا لو احتجتَ إلى تحديد ليس فقط أيّ الأصدقاء ستدعوهم بل أيضًا أين تجلسهم على طاولتك الطويلة؟ فكم عدد الخيارات المتاحة لديك عندئذٍ؟

الحل.

1. عليك ببساطة اختيار 6 أصدقاء من مجموعة من 14. ويمكن ذلك بـ$\binom{14}{6}$ طريقة. يمكننا إيجاد هذا العدد إمّا باستعمال مثلث باسكال أو بالصيغة المغلقة: $\frac{14!}{8!\cdot 6!} = 3003\text{.}$
2. هنا عليك أن تعدّ جميع الطرق التي يمكنك بها تبديل 6 أصدقاء مختارين من مجموعة من 14. إذن الجواب هو $P(14, 6)\text{,}$ ويمكن حسابه بـ$\frac{14!}{8!} = 2162160\text{.}$

ولاحظ أنّنا يمكننا رؤية مسألة العدّ هذه كسؤال عن عدّ الدوال: كم عدد الدوال الأحادية من مجموعة كراسيك الستّة إلى مجموعة أصدقائك الأربعة عشر (الدوال أحادية لأنّه لا يمكن أن يكون كرسيّ واحد يخصّ صديقين)؟

كيف يرتبط هذان العددان؟ لاحظ أنّ $P(14,6)$ أكبر بكثير من $\binom{14}{6}\text{.}$ وهذا منطقي. فـ$\binom{14}{6}$ يختار 6 أصدقاء، لكن $P(14,6)$ يرتّب الأصدقاء الستّة كما يختارهم. وفي الواقع يمكننا أن نقول بعينه كم يكون $P(14,6)$ أكبر. في مسألةَي العدّ كليهما نختار 6 من 14 صديقًا. في المسألة الأولى نتوقّف عند ذلك، عند 3003 طريقة. لكن في مسألة العدّ الثانية، كلّ واحد من تلك الخيارات الـ3003 للأصدقاء الستّة يمكن ترتيبه بـ$6!$ طريقة بالضبط. إذن لدينا الآن $3003\cdot 6!$ خيارًا، وهذا بالضبط $2162160\text{.}$

وبدلًا من ذلك، فلننظر إلى المسألة الأولى بطريقة أخرى. نريد اختيار 6 من 14 صديقًا، لكنّنا لا نهتمّ بالترتيب الذي اختيروا به. لاختيار 6 من 14 صديقًا، يمكننا أن نجرّب هذا: $$\begin{equation*} 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \text{.} \end{equation*}$$

وهذا تخمين معقول، إذ لدينا 14 خيارًا للضيف الأوّل، ثم 13 للثاني، وهكذا. لكنّ التخمين خطأ (في الواقع، ذلك الحاصل هو بالضبط $2162160 = P(14,6)$). فهو يميّز بين الترتيبات المختلفة التي يمكن أن ندعو بها الضيوف. ولتصحيح ذلك، يمكننا القسمة على عدد الترتيبات المختلفة للضيوف الستّة (بحيث لا تُحسب جميع هذه إلّا بوصفها نتيجة واحدة). وهناك بالضبط $6!$ طريقة لترتيب 6 ضيوف، إذن الجواب الصحيح للسؤال الأوّل هو $$\begin{equation*} \frac{14 \cdot 13 \cdot 12 \cdot 11\cdot 10 \cdot 9}{6!} \text{.} \end{equation*}$$

ولاحظ أنّ طريقة أخرى لكتابة ذلك هي $$\begin{equation*} \frac{14!}{8!\cdot 6!}\text{.} \end{equation*}$$ وهو ما كنا قد وصلنا إليه أوّلًا.

ربما تكون تسمية «توافيق» مضلِّلة. فنحن لا نقصد بها مثل قفل التوافيق (حيث يهمّ الترتيب بالتأكيد). وربما استعارة أفضل هي توليفة من النكهات — إذ لا عليك إلّا أن تقرّر أيّ النكهات ستخلط، لا الترتيب الذي ستخلطها به.

إذن كيف تعرف متى تستعمل توافيق ومتى تستعمل تباديل؟

هل يهمّ الترتيب؟

كلّ مصدر تقريبًا تقرأه عن التوافيق والتباديل سيذكر صورةً ما من الادّعاء التالي.

استعمل التبادل عندما يهمّ الترتيب، واستعمل التوافيق عندما لا يهمّ الترتيب.

وماذا يعني هذا أصلًا؟ ولماذا هو طريقة فظيعة تمامًا للتمييز بين تقنيتي العدّ هاتين؟ لنستكشف ذلك بمثال.

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

وبطبيء الحال نريد معرفة احتمالات الفوز في هذه اللعبة، وهذا يتطلّب أن نعرف كم عدد النتائج المختلفة الموجودة. فالكرات تطلع من الآلة عشوائيًا، فقد تكون إحدى النتائج أن تطلع الكرات $$\begin{equation*} 26, 5, 42, 17, 33\text{.} \end{equation*}$$ فإذا كنت تحمل التذكرة التي تحمل الأرقام $5, 17, 26, 33, 47\text{,}$ فهل تتوقّع أن تكون قد فزت؟ لقول معظم ألعاب اليانصيب إنّك فزت، لأنّ لديك الأرقام نفسها لكن بترتيب مختلف.

وبهذا المعنى فإنّ ترتيب الأرقام لا يهمّ. وطريقة أفضل لقول ذلك إنّ أيّ ترتيب لنفس الأرقام يُعدّ النتيجة نفسها، ولا يُعدّ إلّا مرّة واحدة. إذن نحن في الواقع نعدّ مجموعات الأرقام الخمسة، لا تتابعات خمسة أرقام. وكلّ نتيجة هي توافيق، إذن ينبغي أن يكون عدد النتائج هو $C(52,5) = \binom{52}{5}\text{.}$

ومن جهة أخرى، إن كان علينا أن نختار الأرقام بالترتيب نفسه الذي تخرج به من الآلة، فإنّنا في الواقع نطابق تتابع أرقام بتتابع أرقام. وعدد التتابعات هو $P(52,5)\text{.}$ وفي هذه الحالة نقول إنّ الترتيب يهمّ.

حسنًا، إلى الآن كلّ شيء على ما يرام. لكن ماذا عن المثال التالي؟

مثال 3.4.11.

كم عدد «الكلمات» ذات الأحرف الثلاثة التي

1. تظهر أحرفها بالترتيب الأبجدي؟
2. يمكن أن يأتي أحرف الكلمة بأيّ ترتيب؟

الحل. هل «يهمّ الترتيب» في السؤال الأوّل؟ في معنًى ما، بالتأكيد! فنحن لا نريد إلّا عدّ الكلمات التي تكون أحرفها بالترتيب الصحيح. لكن، بالمعنى المعتاد لمقارنة التوافيق بالتباديل، فإنّ الترتيب لا يهمّ.

الأفضل بكثير أن نسأل أنفسنا: هل ينبغي أن نُمثّل كلّ نتيجة كمجموعة من الأحرف أم كتتابع من الأحرف؟ صحيح أنّ الكلمات تتابع من الأحرف، لكن هل نحن نعدّ جميع التتابعات الممكنة؟ لا، بل تتابع واحد فقط لكل مجموعة أحرف. آه، نعم، مجموعة أحرف. كلّ نتيجة تقابل مجموعة واحدة بالضبط من ثلاثة أحرف. نحن نعدّ المجموعات، إذن نعدّ التوافيق. وعدد النتائج هو $C(26,3) = \binom{26}{3}\text{.}$

أمّا السؤال الثاني، فقد يبدو أنّ الترتيب لا ينبغي أن يهمّ. حسنًا، فهو لا يهمّ الآلة التي تطلّق الأحرف، لكنّه سيهمّ لو كنا نحاول مطابقة الأحرف. لا، لنفكّر في الأمر هكذا: هل نحن نعدّ كلّ تتابع ممكن من الأحرف؟ نعم! إذن هذه تباديل، وعدد النتائج هو $P(26,3)\text{.}$

ويظهر استعمال مضلّل آخر للترتيب عند عدّ السلاسل الثنائية. تذكّر أنّ السلسلة الثنائية ذات $n$ بت وبوزن $k$ هي سلسلة من $n$ بت (أصفار ووحدات) يكون فيها $k$ من البتات تساوي 1. فمثلًا، السلاسل الثنائية ذات 4 بتات وبوزن 2 هي $$\begin{equation*} 1100, ~~ 1010, ~~ 1001, ~~ 0110, ~~ 0101, ~~ 0011\text{.} \end{equation*}$$ هل يهمّ الترتيب في السلاسل الثنائية؟ بالتأكيد! فهو الشيء الوحيد الذي يهمّ. فكلّ السلاسل أعلاه تحتوي على العدد نفسه تمامًا من الأصفار والواحدات؛ إنّما يميّزها ترتيب البتات.

ومع ذلك، فإنّ عدد السلاسل الثنائية ذات $n$ بت وبوزن $k$ هو $\binom{n}{k}$ وليس تبادلًا. فما الذي يجري هنا؟

لا شيء معطوب؛ إنّما نحن لا نفكّر في الأشياء الصحيحة التي نبحث عن الترتيب فيها. فعندما نختار $k$ من $n$ شيئًا من أجل سلسلة ثنائية، فإنّما نختار المواضع (لنملأها بالواحدات مثلًا). ولا يهمّنا في أيّ ترتيب نختار تلك المواضع، بل أيّ مجموعة من المواضع نختار. أي أنّ السلسلة الثنائية 1001 هي نتيجة اختيار الموضعين 1 و4 لوضع الواحدات فيهما. ولو اخترنا الموضع 4 ثم الموضع 1، لانتهينا إلى السلسلة الثنائية نفسها.

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

قسم فرعي: مبدأ القسمة

لدينا طريقتان لكتابة العلاقة العددية بين أعداد التوافيق والتباديل. فباستعمال مبدأ الضرب، لدينا $$\begin{equation*} P(n,k) = \binom{n}{k} \cdot k! \end{equation*}$$ ويمكن إعادة كتابتها على الصورة $$\begin{equation*} \binom{n}{k} = \frac{P(n,k)}{k!}\text{.} \end{equation*}$$ وتوحي هذه الصيغة الثانية بأنّه قد يوجد مبدأ قسمة يمكننا استعماله لتبريرها.

فلنتأمّل في معنى القسمة. فإحدى طرائق التفكير في مسألة القسمة $24 \div 6 = 4\text{,}$ مثلًا، هي القول إنّ لديك 24 شيئًا تقسمها إلى مجموعات حجم كلّ منها 6، فسيكون عدد المجموعات 4. 3 أمّا التفسير الآخر لعبارة كهذه، فهو أنّك إذا قسّمت 24 شيئًا إلى ستّ مجموعات، فإنّ كلّ مجموعة يكون حجمها 4، لكنّ هذا أقلّ نفعًا فيما سنفعله.

والآن فلننظر في جميع تبادلات 3 عناصر لمجموعة حجمها 4: أي جميع طرق صنع كلمات ذات ثلاثة أحرف باستخدام الأحرف $a, b, c, d\text{.}$ ونعرف أنّ عدد هذه الكلمات هو $P(4,3) = 4\cdot 3 \cdot 2 = 24\text{.}$ ومن المفيد أن نكتبها جميعًا هنا.

$abc$	$acb$	$bac$	$bca$	$cab$	$cba$
$abd$	$adb$	$bad$	$bda$	$dab$	$dba$
$acd$	$adc$	$cad$	$cda$	$dac$	$dca$
$bcd$	$bdc$	$cbd$	$cdb$	$dbc$	$dcb$

انظر إلى الصفّ الأوّل. ما الذي يشترك فيه جميع هذه التباديل؟ إنّها هي بالضبط التباديل التي تستخدم الأحرف $a, b, c$ بتراتيب مختلفة. وليس مفاجئًا وجود 6 منها، لأنّ عدد طرق ترتيب ثلاثة عناصر هو $3! = 6\text{.}$ وبالمثل، في الصفّ الثاني 6 تباديل تستخدم الأحرف $a, b, d$ بتراتيب مختلفة، وهكذا.

والأمر المهمّ هو، لو أردنا فقط عدّ كم عدد مجموعات من ثلاثة من الأحرف الأربعة التي لدينا، لكانت كلّ مجموعة تقابل بالضبط أحد صفوف الجدول. في الجدول 24 عنصرًا، وفي كلّ صفّ 6 عناصر، إذن لا بدّ من وجود $24 \div 6 = 4$ صفوف. وبطبيء الحال لا نندهش لأنّ $\binom{4}{3} = 4\text{.}$

أمّا التفسير الأكثر رصانةً رياضيًا لهذه الظاهرة فهو استعمال لغة علاقات التكافؤ والتقسيمات من القسم 2.6. فنحن نبدأ بالتباديل، ثم نعرّف علاقة تكافؤ على التباديل بأن نقول إنّ تبادلَين متكافئان إذا احتويا على العناصر نفسها تمامًا. ومن علاقة التكافؤ نحصل على تقسيم لمجموعة تباديلنا إلى أصناف تكافؤ. والتوافيق التي نريد عدّها هي بالضبط أصناف التكافؤ. وبما أنّ كلّ صنف تكافؤ له الحجم نفسه، يمكننا إيجاد عدد الأصناف بقسم عدد التباديل على حجم كلّ صنف.

وهذا النوع من مبدأ القسمة مفيد أيضًا لحلّ الأسئلة التي لا يكون فيها الجواب بوضوح تبادلًا ولا توافيق.

مثال 3.4.12.

قرّرتَ أن تزيّن عصاك السحرية بشرائط من شريط لاصق ملوّن. لديك 10 ألوان مختلفة تختار من بينها، وستستخدم خمسة منها لتكوين خمسة خطوط ملوّنة مختلفة. كم عدد تصاميم العصا المختلفة الممكنة؟

الحل. قد تكون محاولتنا الأولى لحلّ هذه المسألة أن نفكّر في كلّ نتيجة نحاول عدّها بوصفها تبادلًا لـ5 عناصر من 10 ألوان. وسيعطينا ذلك جوابًا قدره $P(10,5) = 10\cdot 9\cdot 8\cdot 7\cdot 6 = 30,240\text{.}$ فلماذا هذا ليس صحيحًا؟ لنبدأ بصنع قائمة بالنتائج الممكنة.

1. الأحمر، والأزرق، والأخضر، والأصفر، والبرتقالي.
2. الأحمر، والأزرق، والأخضر، والأصفر، والبنفسجي.
3. الأزرق، والأخضر، والأحمر، والأصفر، والبرتقالي.
4. البرتقالي، والأصفر، والأخضر، والأزرق، والأحمر.
5. وهكذا.

وبينما كنّا نبدأ هذه القائمة، ربما سألنا أنفسنا ما إذا كان ينبغي أن يكون في القائمة الأحمر، والأحمر، والأزرق، والأزرق، والأحمر، وتبيّن أنّه لا ينبغي. ومن الأشياء الأخرى التي ربما فكّرنا فيها ما إذا كان البندان 1 و3 مختلفان فعلًا. فهما كذلك، لأنّ إحدى العصاَيْن يكون بها الأحمر لونًا خارجيًا بينما الأخرى لا.

وماذا عن البندين 1 و4؟ فلهما الألوان الخمسة نفسها، لكن بترتيب مختلف. لكن، إن قمتَ بإدوير العصا السحرية حول نفسها، كما يحبّ السحرة أن يفعلوا، من السهل تمامًا أن تنتقل من العصا 1 إلى العصا 4. آه! نرى أنّ كلّ عصا تُعدّ مرّتين بالضبط في قائمة التباديل لدينا: فتبادلان متكافئان إذا كان أحدهما معكوس الآخر.

وبما أنّ يمكننا تجميع التباديل في مجموعات حجمها 2، وأنّ كلّ مجموعة تقابل عصا واحدة، نرى أنّ الجواب الصحيح هو $$\begin{equation*} \frac{P(10,5)}{2} = \frac{10\cdot 9\cdot 8\cdot 7\cdot 6}{2} = 15,120\text{.} \end{equation*}$$ أحسنت!

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

1.

صح أم خطأ: عدد التتابعات المكوّنة من رقمين مختلفين من 0-9 هو ضعف عدد المجموعات المكوّنة من رقمين مختلفين من 0-9. اشرح بإيجاز.

2.

صح أم خطأ: عدد التتابعات المكوّنة من ثلاثة أرقام مختلفة من 0-9 هو 3 أضعاف عدد المجموعات المكوّنة من ثلاثة أرقام مختلفة من 0-9. اشرح بإيجاز.

3.

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