البراهين التركيبيّة

القسم 3.6 البراهين التركيبيّة

الأهداف

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

1. أن تكتب مسائل عدّ لها إجابة معطاة.
2. أن تكتب حلّين مختلفين لمسألة عدّ.
3. أن تثبت المتطابقات الثنائية (binomial identities) بالبراهين التركيبيّة (combinatorial proofs).

معاينة القسم

استكشف!

انظر إلى أيّ خليّة في مثلث باسكال الداخليّة والأعداد الستّة التي تحيط بها. فمثلًا، يمكنك أن تنظر إلى هذه الخليّة:

وسنقسّم الأعداد الستّة المحيطة بالخلية التي اخترناها إلى مجموعتين من ثلاثة، بالتبادل بين المجموعتين. ففي هذا المثال، لدينا مجموعة فيها 4 و10 و15، ومجموعة ثانية فيها 5 و6 و20. لكن لاحظ ما يلي: $$\begin{equation*} 4\cdot 10 \cdot 15 = 600 = 5\cdot 6 \cdot 20\text{.} \end{equation*}$$ هل ينجح هذا مهما كانت الخلية الوسطى التي تختارها؟ ولماذا؟؟

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

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

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

لنستكشف بعض الأمثلة.

1.

فكّر في مجموعة السلاسل الثنائية (bit strings) ذات 7 خانات ذات الوزن (weight) 3. أي السلاسل المكوّنة من 0 و1 التي يبلغ طولها سبعة محارف وتحتوي بالضبط على ثلاثة 1. كم عدد هذه السلاسل؟

(a)

اكتب الإجابة بوصفها معاملًا ثنائيًّا (binomial coefficient) واحدًا.

(b)

والآن عُد فقط تلك السلاسل الثنائية ذات 7 خانات والوزن 3 التي تبدأ بالرمز 1. كم عددها؟

(c)

والآن عُد فقط تلك السلاسل الثنائية ذات 7 خانات والوزن 3 التي تبدأ بالرمز 01. كم عددها؟

(d)

والآن عُد فقط تلك السلاسل الثنائية ذات 7 خانات والوزن 3 التي تبدأ بالرمز 001. كم عددها؟

(e)

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

2.

فكّر في مسألة العدّ «كم عدد الطرق التي يمكنك بها تبديل حروف الكلمة STATISTICS؟» ولاحظ أنّ هذا ليس تبديلًا (permutation) فحسب، لأنّ هناك حروفًا مكرّرة.

(a)

كم عدد الطرق التي يمكنك بها اختيار ثلاثة من المواضع العشرة في التبادل الحرفي لتشغلها حروف S؟

(b)

كم عدد الطرق التي يمكنك بها اختيار ثلاثة من المواضع السبعة الباقية في التبادل الحرفي لتشغلها حروف T؟

(c)

واصل هذا الأسلوب حتى تجد تعبيرًا عن عدد طرق تبديل حروف STATISTICS بوصفه حاصل ضرب معاملات ثنائية. اكتب هذا الضرب.

(d)

والآن أجب عن مسألة العدّ مرّة أخرى، وهذه المرّة ابدأ بسؤال: كم عدد الطرق التي يمكنك بها اختيار مواضع حرف A. ثمّ تابع بالطريقة التي تشاء حتى تجد تعبيرًا مختلفًا عن عدد طرق تبديل حروف STATISTICS بوصفه حاصل ضرب معاملات ثنائية. اكتب هذا الضرب.

(e)

جرّب أسلوبًا آخر تمامًا. ما الخطأ في القول بأنّ الإجابة هي $10!\text{?}$ هذا كبير جدًّا، لكن يمكننا تصحيحه بالقسمة مراعاةً للنتائج المتكافئة. على ماذا نقسم؟

اكتب إجابتك على صورة ناتج قسمة مضاريب. هل تحصل على الإجابة نفسها التي حصلت عليها من قبل؟

قسم فرعي: الأنماط في مثلث باسكال

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

وهناك أنماط كثيرة مختفية داخل المثلّث، تكفي لملء كتاب متوسّط الحجم. وإليك بعض أوضحها فقط:

1. جميع الحدود على حدود المثلّث تساوي 1.
2. أيّ حدّ ليس على حدود المثلّث هو مجموع الحدّين اللذين فوقه.
3. المثلّث متناظر. في أيّ صفّ، تنعكس الحدود الموجودة على الجانب الأيسر في الجانب الأيمن.
4. مجموع كلّ الحدود في صفّ معيّن هو أُسّ للعدد 2. (ينبغي أن تتحقّق من هذا!)

نودّ أن نصوغ هذه الملاحظات صياغة أدقّ، ثمّ نثبت صحّتها. والآن كلّ حدّ في مثلث باسكال هو في الحقيقة معامل ثنائي. فالـ1 في قمة المثلّث تمامًا هو $\binom{0}{0}\text{.}$ أمّا الصفّ التالي (الذي سنسمّيه الصفّ 1، رغم أنّه ليس الصفّ الأعلى) فيتكوّن من $\binom{1}{0}$ و$\binom{1}{1}\text{.}$ أمّا الصفّ 4 (الصفّ 1، 4، 6، 4، 1) فيتكوّن من المعاملات الثنائية $$\begin{equation*} \binom{4}{0} ~~ \binom{4}{1} ~~ \binom{4}{2} ~~ \binom{4}{3} ~~ \binom{4}{4}\text{.} \end{equation*}$$

وبناءً على هذا الوصف لعناصر مثلث باسكال، يمكننا إعادة صياغة الملاحظات أعلاه على الصورة التالية:

1. $\binom{n}{0} = 1$ و$\binom{n}{n} = 1\text{.}$
2. $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.}$
3. $\binom{n}{k} = \binom{n}{n-k}\text{.}$
4. $\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n\text{.}$

كلّ واحدة من هذه هي مثال على متطابقة ثنائية: أي متطابقة (أي معادلة) تتضمّن معاملات ثنائية.

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

وإليك كيف يمكنك فعل ذلك بالنسبة إلى المتطابقة الثانية أعلاه.

المثال 3.6.1.

أعطِ برهانًا جبريًّا للمتطابقة الثنائية $$\begin{equation*} \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.} \end{equation*}$$

الحل.

البرهان.

بحكم تعريف $\binom{n}{k}\text{,}$ لدينا $$\begin{equation*} \binom{n-1}{k-1} = \frac{(n-1)!}{(n-1-(k-1))!(k-1)!} = \frac{(n-1)!}{(n-k)!(k-1)!} \end{equation*}$$ و$$\begin{equation*} \binom{n-1}{k} = \frac{(n-1)!}{(n-1-k)!k!}\text{.} \end{equation*}$$

ومن ثمّ، بدءًا من الطرف الأيمن للمعادلة: $$\begin{align*} \binom{n-1}{k-1} + \binom{n-1}{k} \amp = \frac{(n-1)!}{(n-k)!(k-1)!}+ \frac{(n-1)!}{(n-1-k)!\,k!}\\ \amp = \frac{(n-1)!k}{(n-k)!\,k!} + \frac{(n-1)!(n-k)}{(n-k)!\,k!}\\ \amp = \frac{(n-1)!(k+n-k)}{(n-k)!\,k!}\\ \amp = \frac{n!}{(n-k)!\, k!}\\ \amp = \binom{n}{k}\text{.} \end{align*}$$

ويعمل السطر الثاني (حيث وُجد المقام المشترك) لأنّ $k(k-1)! = k!$ و$(n-k)(n-k-1)! = (n-k)!\text{.}$

وهذا بالتأكيد برهان صحيح، لكنّه عديم الفائدة تمامًا. فحتى لو فهمت البرهان فهمًا تامًّا، فهو لا يخبرك لماذا المتطابقة صحيحة. والأسلوب الأفضل هو أن تشرح ما الذي يعنيه $\binom{n}{k}$، ثمّ تقول إنّ $\binom{n-1}{k-1} + \binom{n-1}{k}$ يعني الشيء نفسه. ولنرَ كيف يعمل ذلك مع المتطابقات الأربع التي لاحظناها أعلاه.

المثال 3.6.2.

اشرح لماذا $\binom{n}{0} = 1$ و$\binom{n}{n} = 1\text{.}$

الحل. ماذا تخبرنا هذه المعاملات الثنائية؟ حسنًا، $\binom{n}{0}$ يعطي عدد الطرق لاختيار 0 عنصرًا من مجموعة من $n$ عنصرًا. ولا توجد سوى طريقة واحدة للقيام بذلك، وهي ألّا تختار أيًّا من العناصر. ومن ثمّ $\binom{n}{0} = 1\text{.}$ وبالمثل، يعطي $\binom{n}{n}$ عدد الطرق لاختيار $n$ عنصرًا من مجموعة من $n$ عنصرًا. ولا توجد سوى طريقة واحدة للقيام بذلك: اختر كلّ الـ$n$ عنصرًا. ومن ثمّ $\binom{n}{n} = 1\text{.}$

أو بطريقة أخرى، نعرف أنّ $\binom{n}{0}$ هو عدد السلاسل الثنائية ذات $n$ خانة ذات الوزن 0. فلا توجد سوى سلسلة واحدة من هذا النوع، وهي سلسلة كلّها أصفار. إذن $\binom{n}{0} = 1\text{.}$ وبالمثل، $\binom{n}{n}$ هو عدد السلاسل الثنائية ذات $n$ خانة ذات الوزن $n\text{.}$ فلا توجد سوى سلسلة واحدة بهذه الصفة، وهي سلسلة كلّها آحاد.

وطريقة أخرى: يعطي $\binom{n}{0}$ عدد المجموعات الجزئية (subsets) لمجموعة من الحجم $n$ التي تحتوي على 0 عنصر. فلا توجد سوى مجموعة جزئية واحدة من هذا النوع، وهي المجموعة الخالية. ويعطي $\binom{n}{n}$ عدد المجموعات الجزئية التي تحتوي على $n$ عنصرًا. والمجموعة الجزئية الوحيدة من هذا النوع هي المجموعة الأصلية (بكلّ عناصرها).

المثال 3.6.3.

اشرح لماذا $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.}$

الحل. إن أسهل طريقة لرؤية ذلك هي النظر في السلاسل الثنائية. فـ$\binom{n}{k}$ هو عدد السلاسل الثنائية ذات الطول $n$ التي تحتوي على $k$ آحاد. ومن بين كل هذه السلاسل، تبدأ بعضها بالرمز 1 ويبدأ الباقي بالرمز 0. لنبدأ أولًا بكل السلاسل الثنائية التي تبدأ بالرمز 1. وبعد الـ1 يجب أن تأتي $n-1$ بتات أخرى (لرفع الطول الكلي إلى $n$)، ويجب أن يكون منها بالضبط $k-1$ آحاد (لأنّ لدينا واحدًا بالفعل، ونحتاج إلى $k$ إجمالًا). كم عدد السلاسل من هذا النوع؟ هناك بالضبط $\binom{n-1}{k-1}$ سلسلة ثنائية من هذا النوع، ومن ثمّ فمن بين كل السلاسل الثنائية ذات الطول $n$ التي تحتوي على $k$ آحاد، $\binom{n-1}{k-1}$ منها تبدأ بالرمز 1. وبالمثل، هناك $\binom{n-1}{k}$ منها تبدأ بالرمز 0 (فلا يزال أمامنا $n-1$ بت، ويجب أن يكون منها $k$ آحاد). وبما أنّ هناك $\binom{n-1}{k}$ سلسلة ثنائية تحتوي على $n-1$ بت و$k$ آحاد، فإنّ ذلك هو عدد السلاسل الثنائية ذات الطول $n$ التي تحتوي على $k$ آحاد وتبدأ بالرمز 0. ومن ثمّ $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.}$

وطريقة أخرى: فكّر في السؤال التالي: كم عدد الطرق التي يمكنك بها اختيار $k$ مكوّنًا من قائمة تحتوي على $n$ خيارًا؟ إحدى الطرق للإجابة عن ذلك هي $\binom{n}{k}\text{.}$ وطريقة أخرى للإجابة عن السؤال نفسه هي أن تقرّر أولًا: هل تريد أنشوفيز (anchovies) أم لا. فإن أردت أنشوفيز، فما زال عليك أن تختار $k-1$ مكوّنًا، الآن من $n-1$ خيارًا فقط. ويمكن ذلك ب $\binom{n-1}{k-1}$ طريقة. وإن لم ترد أنشوفيز، فما زال عليك أن تختار $k$ مكوّنًا من $n-1$ خيارًا (فقد خرجت أنشوفيز من القوائم). ويمكنك ذلك ب $\binom{n-1}{k}$ طريقة. وبما أنّ الخيارات التي فيها أنشوفيز منفصلة عن الخيارات التي ليس فيها أنشوفيز، فإنّ إجمالي الخيارات هو $\binom{n-1}{k-1}+\binom{n-1}{k}\text{.}$ لكنّ انتبه. لقد أجبنا عن السؤال نفسه بطريقتين مختلفتين، إذن لا بدّ أن يكون الجوابان متساويين. ومن ثمّ $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.}$

ويمكنك أيضًا شرح (إثبات) هذه المتطابقة بعدّ المجموعات الجزئية، بل وحتى المسارات الشبكية (lattice paths).

المثال 3.6.4.

أثبت المتطابقة الثنائية $\binom{n}{k} = \binom{n}{n-k}\text{.}$

الحل. لماذا هذا صحيح؟ فـ$\binom{n}{k}$ يعدّ عدد الطرق لاختيار $k$ شيئًا من $n$ خيارًا. ومن جهة أخرى، يعدّ $\binom{n}{n-k}$ عدد الطرق لاختيار $n-k$ شيئًا من $n$ خيارًا. هل هذان متساويان فعلًا؟ حسنًا، ماذا لو بدلًا من اختيار الأشياء الـ$n-k$ اخترتَ استبعادها. كم عدد الطرق لاختيار $n-k$ شيئًا لاستبعادها من $n$ خيارًا؟ ولاشكّ أنّ هذا هو $\binom{n}{n-k}$ أيضًا (فلا يهمّ ما إذا أدرجت الأشياء أو استبعدتها بعد أن اخترتها). وإذا استبعدتَ $n-k$ شيئًا، فإنّك تُدرج الأشياء الـ$k$ الأخرى. إذن ينبغي أن تكون مجموعة النتائج واحدة.

ولنجرّب مثال عدّ البيتزا كما فعلنا أعلاه. كم عدد الطرق لاختيار $k$ مكوّنًا من قائمة فيها $n$ خيارًا؟ من جهة، الجواب هو ببساطة $\binom{n}{k}\text{.}$ أو يمكنك، بطريقة أخرى، أن تكتب قائمة بكلّ المكوّنات التي لا تريدها. ولأن تنتهي إلى بيتزا تحتوي على $k$ مكوّنًا بالضبط، عليك أن تختار $n-k$ مكوّنًا لا تضعها على البيتزا. ولديك $\binom{n}{n-k}$ خيارًا للمكوّنات التي لا تريدها. وكلتا الطريقتين تعطيك بيتزا فيها $k$ مكوّنًا، بل في الواقع كلّ طرق الحصول على بيتزا فيها $k$ مكوّن. ومن ثمّ لا بدّ أن يكون الجوابان متساويين: $\binom{n}{k} = \binom{n}{n-k}\text{.}$

ويمكنك أيضًا إثبات (شرح) هذه المتطابقة باستعمال السلاسل الثنائية أو المجموعات الجزئية أو المسارات الشبكية. وحجّة السلاسل الثنائية جميلة: فـ$\binom{n}{k}$ يعدّ عدد السلاسل الثنائية ذات الطول $n$ التي فيها $k$ آحاد. وهذا أيضًا عدد السلاسل الثنائية ذات الطول $n$ التي فيها $k$ أصفار (استبدل كلّ 1 بـ 0 وكلّ 0 بـ 1). لكن إذا كانت سلسلة من الطول $n$ فيها $k$ أصفار، فلا بدّ أن يكون فيها $n-k$ آحاد. وهناك بالضبط $\binom{n}{n-k}$ سلسلة من الطول $n$ فيها $n-k$ آحاد.

المثال 3.6.5.

أثبت المتطابقة الثنائية $\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n\text{.}$

الحل. لنفعل «برهان بيتزا» مرّة أخرى. فنحن بحاجة إلى إيجاد سؤال عن مكوّنات البيتزا يكون جوابه $2^n$. فكيف بهذا: إذا كان هناك محلّ بيتزا يقدّم $n$ مكوّنًا، فكم عدد البيتزات التي يمكنك تكوينها باستعمال أيّ عدد من المكوّنات من صفر مكوّن إلى كلّ المكوّنات، مع استعمال كلّ مكوّن مرّة واحدة على الأكثر؟

من جهة، الجواب هو $2^n\text{.}$ فلكلّ مكوّن يمكنك أن تقول «نعم» أو «لا»، إذن لديك خياران لكلّ مكوّن.

ومن جهة أخرى، قسّم البيتزات الممكنة إلى مجموعات منفصلة: البيتزات التي بلا مكوّنات، والبيتزات ذات المكوّن الواحد، والبيتزات ذات المكوّنين، وهكذا. فإن أردنا صفر مكوّنات، فلا توجد سوى بيتزا واحدة من هذا النوع (البيتزا الفارغة إن شئت)، لكن من الأفضل أن ننظر إلى هذا العدد على أنه $\binom{n}{0}$ لأنّنا نختار 0 من المكوّنات الـ$n$. فكم عدد البيتزات ذات المكوّن الواحد؟ علينا أن نختار 1 من المكوّنات الـ$n$، إذن $\binom{n}{1}\text{.}$ ولدينا:

• بيتزات بلا مكوّنات: $\binom{n}{0}$
• بيتزات بمكوّن واحد: $\binom{n}{1}$
• بيتزات بمكوّنين: $\binom{n}{2}$
• $\displaystyle \vdots$
• بيتزات بـ$n$ مكوّنًا: $\binom{n}{n}\text{.}$

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

ومرةً أخرى، كان بإمكاننا إثبات المتطابقة باستعمال المجموعات الجزئية أو السلاسل الثنائية أو المسارات الشبكية (مع أنّ حجّة المسارات الشبكية أصعب قليلًا).

ولعلّ هذا يمنحنا فكرةً عمّا يمكن أن تكون عليه البراهين التفسيرية للمتطابقات الثنائية. ومن يجدر التنبيه إليه أنّ البراهين التقليدية قد تكون جميلة أيضًا. 4 أغلب المتطابقات الثنائية يمكن إثباتها بالحثّ الرياضي، باستعمال التعريف العودي لـ $\binom{n}{k}\text{.}$ وسنتناول الحثّ في القسم 4.5. فمثلًا، فكّر في هذا البرهان الأنيق للمتطابقة الأخيرة.

ثمّ فاكّ توسيع ثنائي الطرف $(x+y)^n\text{:}$ $$\begin{equation*} (x + y)^n = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + \cdots + \binom{n}{n-1}x\cdot y^{n-1} + \binom{n}{n}y^n\text{.} \end{equation*}$$

خذ $x = 1$ و$y = 1\text{.}$ فنحصل على: $$\begin{equation*} (1 + 1)^n = \binom{n}{0}1^n + \binom{n}{1}1^{n-1}1 + \binom{n}{2}1^{n-2}1^2 + \cdots + \binom{n}{n-1}1\cdot 1^{n-1} + \binom{n}{n}1^n\text{.} \end{equation*}$$

وبالطبع يبسّط هذا إلى: $$\begin{equation*} (2)^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n-1} + \binom{n}{n}\text{.} \end{equation*}$$

شيء ممتع لتجربته: خذ $x = 1$ و$y = 2\text{.}$ ألطيف، أليس كذلك؟

قسم فرعي: براهين أخرى

تُسمّى البراهين التفسيرية المعطاة في الأمثلة أعلاه عادةً بالبراهين التركيبيّة. على نحو عامّ، لإعطاء برهان تركيبي لمتطابقة ثنائية، ولنفرض أنّ $A = B\text{,}$ فإنّك تفعل ما يلي:

1. ابحث عن مسألة عدّ تستطيع الإجابة عنها بطريقتين.
2. اشرح لماذا إحدى الإجابتين عن مسألة العدّ هي $A\text{.}$
3. اشرح لماذا الإجابة الأخرى عن مسألة العدّ هي $B\text{.}$

وبما أنّ كلًّا من $A$ و$B$ هو جواب السؤال نفسه، فلا بدّ أن يكون لدينا $A = B\text{.}$

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

فمثلًا، فكّر في مسألة العدّ هذه:

كم عدد الكلمات ذات العشرة أحرف التي تستخدم بالضبط أربعة A وثلاثة B واثنين C وواحد D؟

لنحاول حلّ هذه المسألة. لدينا 10 مواضع يمكن أن توضع فيها الحروف. أربعة منها تحتاج إلى A. يمكننا اختيار مواضع A الأربعة ب $\binom{10}{4}$ طريقة. الآن أين يمكننا وضع B؟ حسنًا لم يبقَ سوى 6 مواضع؛ فنحن أن نختار $3$ منها. ويمكن ذلك ب $\binom{6}{3}$ طريقة. يحتاج C الاثنان إلى موضعين من المواضع الثلاثة الباقية، فلدينا $\binom{3}{2}$ طريقة لفعل ذلك. ولا يبقى سوى موضع واحد لـ D، لكن يمكننا كتابة هذا الاختيار الواحد بوصفه $\binom{1}{1}\text{.}$ ومن ثمّ فإنّ الجواب هو: $$\begin{equation*} \binom{10}{4}\binom{6}{3}\binom{3}{2}\binom{1}{1}\text{.} \end{equation*}$$

لكنّ لماذا نتوقّف هنا؟ يمكننا إيجاد الجواب بطريقة أخرى أيضًا. لنبدأ أولًا بتحديد موضع D الواحد: لدينا 10 مواضع ونحتاج إلى اختيار واحد منها، فيمكن ذلك ب $\binom{10}{1}$ طريقة. ثمّ اختر إحدى $\binom{9}{2}$ طرق وضع C الاثنين. صار لدينا الآن $7$ مواضع، وثلاثة منها تحتاج إلى أن تُملأ بـ B. هناك $\binom{7}{3}$ طرق لفعل ذلك. وأخيرًا يمكن وضع A ب $\binom{4}{4}$ (أي، طريقة واحدة فقط) طريقة. إذن جواب آخر عن السؤال هو $$\begin{equation*} \binom{10}{1}\binom{9}{2}\binom{7}{3}\binom{4}{4}\text{.} \end{equation*}$$

هذا مثير للاهتمام. فهذا يعطينا المتطابقة الثنائية: $$\begin{equation*} \binom{10}{4}\binom{6}{3}\binom{3}{2}\binom{1}{1} = \binom{10}{1}\binom{9}{2}\binom{7}{3}\binom{4}{4}\text{.} \end{equation*}$$

وإليك بعض المتطابقات الثنائية الأخرى ذات البراهين التركيبيّة.

المثال 3.6.6.

أثبت المتطابقة $$\begin{equation*} 1 n + 2(n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = \binom{n+2}{3}\text{.} \end{equation*}$$

الحل. لإعطاء برهان تركيبي نحتاج إلى أن نُفكّر في سؤال نستطيع الإجابة عنه بطريقتين: إحدى الطريقتين تُعطي الطرف الأيسر من المتطابقة، والأخرى تُعطي الطرف الأيمن منها. ويأتِينا التلميح حول السؤال الذي نسأله من الطرف الأيمن: فـ$\binom{n+2}{3}$ يعدّ عدد الطرق لاختيار 3 أشياء من مجموعة من $n+2$ شيئًا. لنسمِّ الأشياء تلك $1, 2, 3, \ldots, n+2\text{.}$ بمعنى آخر، نريد إيجاد المجموعات الجزئية ذات الثلاثة عناصر من تلك الأعداد (ولأنّ الترتيب لا ينبغي أن يهمّ، فإنّ المجموعات الجزئية هي بالضبط الشيء المناسب للتفكير فيه). وسيتعين علينا أن نكون مبدعين نوعًا ما لشرح لماذا يعطي الطرف الأيسر أيضًا عدد هذه المجموعات الجزئية. وإليك البرهان.

البرهان.

فكّر في السؤال «كم عدد المجموعات الجزئية ذات الثلاثة عناصر لمجموعة $\{1,2,3,\ldots, n+2\}\text{?}$» ونجيب عن هذا بطريقتين:

الجواب 1: علينا اختيار 3 عناصر من مجموعة من $n+2$ عنصرًا. ويمكن ذلك ب $\binom{n+2}{3}$ طريقة.

الجواب 2: قسّم هذه المسألة إلى حالات حسب العدد الأوسط في المجموعة الجزئية. لنكتب كلّ مجموعة جزئية $\{a,b,c\}$ بترتيب متزايد. فنعدّ عدد المجموعات الجزئية لكلّ قيمة مميّزة من $b\text{.}$ وأصغر قيمة ممكنة لـ$b$ هي $2\text{,}$ وأكبرها هي $n+1\text{.}$

عندما يكون $b = 2\text{,}$ تكون هناك $1 \cdot n$ مجموعة جزئية: خيار واحد لـ $a$ و$n$ خيارًا (من 3 إلى $n+2$) لـ $c\text{.}$

عندما يكون $b = 3\text{,}$ تكون هناك $2 \cdot (n-1)$ مجموعة جزئية: خياران لـ $a$ و$n-1$ خيارًا لـ $c\text{.}$

عندما يكون $b = 4\text{,}$ تكون هناك $3 \cdot (n-2)$ مجموعة جزئية: 3 خيارات لـ $a$ و$n-2$ خيارًا لـ $c\text{.}$

وهكذا. عندما يكون $b = n+1\text{,}$ هناك $n$ خيارًا لـ $a$ وخيار واحد فقط لـ $c\text{,}$ ومن ثمّ هناك $n \cdot 1$ مجموعة جزئية.

ومن ثمّ فإنّ إجمالي عدد المجموعات الجزئية هو $$\begin{equation*} 1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1)2 + n 1\text{.} \end{equation*}$$

وبما أنّ الجواب 1 والجواب 2 هما جوابان عن السؤال نفسه، فلا بدّ أن يكونا متساويين. ومن ثمّ $$\begin{equation*} 1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = \binom{n+2}{3}\text{.} \end{equation*}$$

المثال 3.6.7.

أثبت المتطابقة الثنائية $$\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n}\text{.} \end{equation*}$$

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

البرهان.

فكّر في السؤال: «كم عدد البيتزات التي يمكنك صنعها باستعمال $n$ مكوّنًا عندما يكون هناك $2n$ مكوّنًا للاختيار منها؟»

الجواب 1: هناك $2n$ مكوّنًا، يجب أن تختار منها $n\text{.}$ ويمكن ذلك ب $\binom{2n}{n}$ طريقة.

الجواب 2: قسّم المكوّنات إلى مجموعتين من $n$ مكوّنًا (ربما $n$ من اللحوم و$n$ من الخضار). فأيّ اختيار لـ$n$ مكوّنًا لا بدّ أن يحتوي على عدد ما من المجموعة الأولى وعدد ما من المجموعة الثانية. فلننظر في كلّ عدد ممكن لمكوّنات اللحوم على حدة:

صفر لحم: $\binom{n}{0}\binom{n}{n}\text{,}$ لأنّك تحتاج إلى اختيار 0 من الـ$n$ لحمًا و$n$ من الـ$n$ خضارًا.

لحم واحد: $\binom{n}{1}\binom{n}{n-1}\text{,}$ لأنّك تحتاج إلى 1 من $n$ لحم، إذن $n-1$ من $n$ خضار.

لحمان: $\binom{n}{2}\binom{n}{n-2}\text{.}$ اختر لحمين، ثمّ المكوّنات الـ$n-2$ الباقية من الـ$n$ خضار.

وهكذا. والحالة الأخيرة هي $n$ لحمًا، ويمكن ذلك ب $\binom{n}{n}\binom{n}{0}$ طريقة.

ومن ثمّ فإنّ إجمالي عدد البيتزات الممكنة هو $$\begin{equation*} \binom{n}{0}\binom{n}{n} + \binom{n}{1}\binom{n}{n-1} + \binom{n}{2}\binom{n}{n-2} + \cdots + \binom{n}{n}\binom{n}{0}\text{.} \end{equation*}$$

وهذا ليس الطرف الأيسر تمامًا … بعد. لاحظ أنّ $\binom{n}{n} = \binom{n}{0}$ و$\binom{n}{n-1} = \binom{n}{1}$ وهكذا، بحكم المتطابقة في المثال 3.6.4. ومن ثمّ نحصل فعلًا على $$\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2\text{.} \end{equation*}$$

وبما أنّ هذين الجوابين جوابان عن السؤال نفسه، فلا بدّ أن يكونا متساويين، ومن ثمّ $$\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n}\text{.} \end{equation*}$$

ولبرهان بديل، نستعمل المسارات الشبكية. ومن المعقول التفكير في ذلك لأنّ الطرف الأيمن من المتطابقة يذكّرنا بعدد المسارات من $(0,0)$ إلى $(n,n)\text{.}$

البرهان.

فكّر في السؤال: كم عدد المسارات الشبكية من $(0,0)$ إلى $(n,n)\text{?}$

الجواب 1: علينا قطع $2n$ خطوة، ولا بدّ أن تكون $n$ منها في الاتجاه العمودي. ومن ثمّ هناك $\binom{2n}{n}$ مسارًا.

الجواب 2: لاحظ أنّ أيّ مسار من $(0,0)$ إلى $(n,n)$ لا بدّ أن يعبر المستقيم $x + y = n\text{.}$ بمعنى، لا بدّ أن يمرّ أيّ مسار بواحدة تمامًا من النقاط التالية: $(0,n)\text{,}$ $(1,n-1)\text{,}$ $(2,n-2)\text{,}$ …، $(n, 0)\text{.}$ فمثلًا، هذا ما يحدث في الحالة $n = 4\text{:}$

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

وماذا عن المسارات التي تمرّ بـ$(1,n-1)\text{?}$ هناك $\binom{n}{1}$ مسارًا للوصول إلى هناك ($n$ خطوة، واحدة إلى اليمين) و$\binom{n}{1}$ مسارًا لإكمال الرحلة إلى $(n,n)$ ($n$ خطوة، $1$ عمودية). ومن ثمّ هناك $\binom{n}{1}\binom{n}{1}$ مسارًا من $(0,0)$ إلى $(n,n)$ عبر $(1,n-1)\text{.}$

وعلى نحو عامّ، للوصول إلى $(n,n)$ عبر النقطة $(k,n-k)$ لدينا $\binom{n}{k}$ مسارًا إلى المنتصف ثمّ $\binom{n}{k}$ مسارًا من المنتصف إلى $(n,n)\text{.}$ ومن ثمّ هناك $\binom{n}{k}\binom{n}{k}$ مسارًا من $(0,0)$ إلى $(n,n)$ عبر $(k, n-k)\text{.}$

ومن ثمّ جميعًا، فإنّ إجمالي المسارات من $(0,0)$ إلى $(n,n)$ المارّة بواحدة تمامًا من هذه المنتصفات هو $$\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2\text{.} \end{equation*}$$

وبما أنّ هذين الجوابين جوابان عن السؤال نفسه، فلا بدّ أن يكونا متساويين، ومن ثمّ $$\begin{equation*} \binom{n}{0}^2 + \binom{n}{1}^2 + \binom{n}{2}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n}\text{.} \end{equation*}$$

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

1.

أيّ ممّا يلي يصف الاستراتيجية العامة للبرهان التركيبي؟

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

2.

اكتب مسألة عدّ يمكنك استعمالها لإثبات المتطابقة: $$\begin{equation*} \binom{x+y}{x} = \binom{x+y}{y}\text{.} \end{equation*}$$

3.

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

ولتأخذ السؤال: «كم عددًا من الأعداد ذات الخانتين يبدأ بـ 3 أو يبدأ بـ 4؟»
---
ولتأخذ السؤال: «كم عددًا من البيتزا ذات إضافتين يمكنك صنعه من بين 10 إضافات؟»
---
وأوّل طريقة للإجابة عن هذا هي \(10+10\text{.}\)
---
ويُعزى ذلك إلى أنّ هناك 10 أعداد تبدأ بـ 3، و10 أخرى تبدأ بـ 4.
---
ويُعزى ذلك إلى أنّ أمام الإضافة الأولى 10 اختيارات، وأمام الإضافة الثانية 10 اختيارات.
---
وثانية إجابةٍ عن السؤال هي \(2\cdot 10\text{.}\)
---
ويُعزى ذلك إلى أنّ أمام الخانة الأولى اختياران، وأمام الخانة الثانية 10 اختيارات.
---
ويُعزى ذلك إلى أنّ عليك إمّا أن تختار إضافتين متطابقتين أو إضافتين مختلفتين.
---
ولأنّ التعبيرين يجيبان عن السؤال نفسه، فلا بدّ أن يكونا متساويين. ومن ثمّ \(10+10 = 2\cdot 10\text{.}\)