مثلث باسكال الحسابي

القسم 3.1 مثلث باسكال الحسابي

الأهداف

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

1. استعمل مثلث باسكال للإجابة عن مسائل عدّ تتعلّق بالمسارات الشبكية والسلاسل الثنائية والمجموعات الجزئية.
2. اشرح كيف يُولَّد مثلث باسكال وكيف يرتبط بمسائل العدّ.
3. اشرح لماذا يرتبط مثلث باسكال بهذا العدد الكبير من أنواع مسائل العدّ المختلفة.

معاينة القسم

استكشف!

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

ويحتوي المربّع في الصفّ الثالث والعمود الثالث على العدد 6.

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

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

لنعثر على بعض أعداد المسارات التي يمكن أن يسلكها الرخ ليصل إلى مربّعات مختلفة في رقعة الشطرنج.

1. ستة مسارات.

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

2. المسارات المارّة عبر (4, 2).

كم عدد المسارات إلى المربّع في الصفّ 4 والعمود 2 (قُطرًا إلى الأسفل وإلى يسار العدد 6)؟ اكتب جميع المسارات في صورة سلاسل D/R.

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

3. المسارات المارّة عبر (4, 3).

لنعثر الآن على المسارات إلى المربّع في الصفّ 4 والعمود 3 (مباشرة أسفل العدد 6).

أوّلًا، اكتب جميع المسارات التي تنتهي بحرف R.

ثمّ اكتب جميع المسارات التي تنتهي بحرف D.

هل هناك أيّ مسارات أخرى؟ وإجمالًا، كم عدد المسارات إلى هذا المربّع؟

4. عدّ جميع المسارات.

تابع ملء رقعة الشطرنج، إمّا بعدّ سلاسل D/R مباشرة أو باستعمال ملاحظتك من المهمّة السابقة. ما العدد في الركن السفلي الأيمن من رقعة الشطرنج؟

في عام 1653 جمع بليز باسكال، وهو مهتمّ بالأسئلة التي ترسي أساس نظرية الاحتمالات، عدة حقائق عن مصفوفة مثلّثة من الأعداد في كتابه «المثلث الحسابي». وقد ظهر هذا الترتيب من الأعداد في الصين والهند وفارس منذ القرن العاشر الميلادي. وكان تعامل الصين وفارس مع المثلث في خدمة ما نعدّه اليوم جبرًا: إيجاد الجذور الـ$n$ث، أي حلّ المعادلات متعددة الحدود في جوهرها. أما أعداد المثلث فتظهر بوصفها حلولًا لمسائل عدّ في النصوص الهندية: من ستّ نكهات، كم عدد التوافيق (combinations) الممكنة من واحدة أو اثنتين أو ثلاث أو…؟ أمّا الرياضيون الأوروبيون في القرن الرابع عشر المثلث على هيئة جدول من الأعداد المتشكّلة (figurate numbers)، أي الأعداد التي يمكن ترتيبها في شكل هندسي، وكانت هذه الأعداد بدورها محور عمل فيثاغورس ومن تبعوه.

إذن فما هذا المثلث لافت النظر الذي يحوي أسرار مسائل رياضية مختلفة كثيرة؟ ها هو مثلث باسكال:

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

الشكل 3.1.1. مثلث باسكال.

اقضِ بعض الوقت في تأمّل جمال هذا المثلث. ماذا تلاحظ؟ وما الذي يدهشك؟ انظر على وجه التحديد إلى الصفّ الخامس (فنسمّي 1 في الصفّ العلوي بـ0، إذن الصفّ الخامس هو 1، 5، 10، 10، 5، 1). كيف ترتبط الأعداد في هذا الصفّ بالأعداد فوقها؟ لاحظ أنّ $5 = 1+4$ و$10 = 4+6\text{.}$ هل يحدث هذا في مكان آخر من المثلث؟

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

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

وقبل أن نبدأ، دعنا نكتب قليلًا من الرموز. لنعطِ كلّ عدد في مثلث باسكال اسمًا بحسب موضعه. تخيّل كلّ عدد واقعًا في صفٍّ وعمود: تُعدّ الصفوف نزولًا بدءًا من 0، وتُعدّ الأعمدة من اليسار بدءًا من 0 أيضًا. ويُرمز إلى المدخل في الصفّ $n$ والعمود $k$ بـ$\binom{n}{k}\text{.}$ على سبيل المثال، $\binom{6}{3} = 20\text{,}$ لأنّ هذه هي القيمة في الصفّ 6 والعمود 3. ولأسباب ستتضح قريبًا، فإنّنا ننطق بـ$\binom{n}{k}$ على النحو «$n$ اختر $k\text{.}$» (n choose k). يمكننا إعادة كتابة المثلث بهذه الأسماء:

قسم فرعي: المسارات الشبكية

الشبكة الصحيحة (integer lattice) هي مجموعة جميع النقاط في المستوى الديكارتي التي إحداثياتها $x$ و$y$ كلاهما عدد صحيح. فإن كنت تحبّ رسم الرسوم البيانية على ورق رسم بياني (graph paper)، فإنّ الشبكة هي مجموعة جميع تقاطعات خطوط الشبكة.

والمسار الشبكي (lattice path) هو أحد أقصر المسارات الممكنة التي تصل بين نقطتين على الشبكة، متحرّكًا أفقيًا ورأسيًا فقط. فمثلًا، إليك ثلاثة مسارات شبكية محتملة من النقطة $(0,0)$ إلى $(3,2)\text{:}$

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

وسؤال العدّ الذي سنطرحه هو: كم عدد المسارات الشبكية بين $(0,0)$ و$(3,2)\text{?}$ وفي هذه الحالة، لن يستغرق رسم كلّ المسارات وقتًا طويلًا. أو يمكننا سرد كلّ مسار في صورة سلسلة من «الاتجاهات» مثل $xxyyx\text{,}$ أو $yyxxx\text{,}$ أو $xyxxy\text{,}$ وفي هذه الحالة من $x$ تعني الانتقال وحدةً واحدة في اتجاه $x$، وكذلك تمامًا بالنسبة إلى $y\text{.}$ سنحصل عندئذٍ على المسارات العشرة التالية: $$\begin{gather*} xxxyy \qquad xxyxy \qquad xyxxy \qquad yxxxy\\ xxyyx \qquad xyxyx \qquad yxxyx \qquad xyyxx \qquad yxyxx \qquad yyxxx\text{.} \end{gather*}$$ وعندما تكون المسافة بين نقطة البداية ونقطة التوقّف أكبر، سنرغب في إيجاد طريقة أكثر كفاءة لعدّ المسارات.

لنأخذ ما تعلّمناه من مسارات الرخ (وهي، مع الأسف، مسارات شبكية في الواقع). انظر في الشبكة المبيّنة أدناه:

أيّ مسار شبكي من (0,0) إلى (3,2) لا بدّ أن يمرّ عبر واحدة بالضبط من $A$ و$B\text{.}$ فالنقطة $A$ تبعد أربع خطوات عن (0,0)، اثنتان منها في اتجاه $x$. والخطوة الأخيرة هي أيضًا في اتجاه $x$، لذا فإنّ المسارات من (0,0) إلى (3,2) التي تمرّ عبر $A$ هي على وجه الضبط السلاسل الستّ التي سردناها أعلاه والمنتهية بحرف $x\text{.}$ أما المسارات التي تمرّ عبر النقطة $B\text{,}$ فستكون خطوتها الأخيرة في اتجاه $y$، لذا فإنّ المسارات من (0,0) إلى (3,2) التي تمرّ عبر $B$ هي على وجه الضبط السلاسل الأربع التي سردناها أعلاه والمنتهية بحرف $y\text{.}$ إذن فإجمالي عدد المسارات إلى (3,2) هو ببساطة $6+4\text{.}$

والملاحظة العامّة هنا هي أنّه لإيجاد عدد المسارات التي تبدأ عند $(0,0)$ وتنتهي عند $(m,n)\text{,}$ يمكننا إيجاد عدد المسارات إلى النقطة الواقعة مباشرة يسار نقطة النهاية، أي $(m-1,n)$، ثمّ نضيف عدد المسارات إلى النقطة الواقعة مباشرة أسفل نقطة النهاية، أي $(m,n-1)\text{.}$ وهذه بالضبط هي الطريقة التي يُولَّد بها مثلث باسكال! وبالفعل، إذا دورنا الشبكة بالاتجاه المناسب بحيث تكون النقطة $(0,0)$ في أعلى المثلث وتكون المحاور على جانبي المثلث، فإنّنا نرى أنّ الأعداد في مثلث باسكال تعطينا على وجه الضبط عدد المسارات إلى كلّ نقطة شبكية.

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

المثال 3.1.2.

كم عدد المسارات الشبكية من $(0,0)$ إلى $(4,7)\text{?}$

الحل. طول هذه المسارات هو $4+7 = 11\text{.}$ انظر في الصفّ الحادي عشر من مثلث باسكال: $$\begin{equation*} 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1\text{.} \end{equation*}$$ عُدّ حتى المركز السابع (مع التذكير بأنّ 1 في المركز 0)، فيعطينا ذلك $\binom{11}{7} = 330$ مسارًا مختلفًا.

قسم فرعي: السلاسل الثنائية

«البت» (bit) اختصار لكلمة «الخانة الثنائية» (binary digit)، لذا فإنّ السلسلة الثنائية (bit string) هي سلسلة من الخانات الثنائية. والخانات الثنائية ليست سوى العددين 0 و1. وكلّ ما يلي سلاسل ثنائية: $$\begin{equation*} 1001 \quad 0 \quad 1111 \quad 1010101010\text{.} \end{equation*}$$

عدد البتات (0 أو 1) في السلسلة هو طول السلسلة؛ والسلاسل أعلاه طولاتها 4 و1 و4 و10 على التوالي. ويمكننا أيضًا أن نسأل كم عدد البتات التي هي 1. وعدد 1ات في السلسلة الثنائية هو وزن السلسلة؛ وأوزان السلاسل أعلاه هي 2 و0 و4 و5 على التوالي.

تعريف 3.1.3. السلاسل الثنائية.

• السلسلة الثنائية ذات الـ$n$ بت هي سلسلة ثنائية طولها $n\text{.}$ أي أنّها سلسلة تحتوي $n$ رمزًا، كلّ رمز منها بت، إمّا 0 أو 1.
• وزن السلسلة الثنائية هو عدد 1ات فيها.
• $\B^n_k$ هي مجموعة جميع السلاسل الثنائية ذات الـ$n$ بت والوزن $k\text{.}$

فمثلًا، عناصر المجموعة $\B^3_2$ هي السلاسل الثنائية 011 و101 و110. فهذه هي السلاسل الوحيدة التي تحتوي ثلاث بتات، اثنتان منها بالضبط هما 1.

وأسئلة العدّ هي: كم عدد السلاسل الثنائية ذات الخمس بتات ذات الوزن 3؟ وبعبارة أخرى، فإنّنا نطلب عدد المجموعة (cardinality) $|\B^5_3|\text{.}$

لنسردها فحسب ولنرَ كم عددها. $$\begin{gather*} 11100 \qquad 11010 \qquad 10110 \qquad 01110\\ 11001 \qquad 10101 \qquad 01101 \qquad 10011 \qquad 01011 \qquad 00111\text{.} \end{gather*}$$ رائع. عشر منها. وفي الحقيقة، لي اعترافٌ لي: لم أكتب جميع هذه من الصفر. بل إنّني عدّلت فقط قائمة المسارات العشرة الشبكية من (0,0) إلى (3,2) التي وجدناها سابقًا. فكلّ $x$ صار 1 وكلّ $y$ صار 0. فبعد كلّ ما قلناه، فإنّ أيّ مسار شبكي طوله $n$ ويحتاج إلى $k$ خطوة في اتجاه $x$ يمكن تمثيله بسلسلة من $n$ رمزًا من نوعين، منها $k$ من نوع واحد. وسواء سمّينا الرمزين $x$ و$y$ أو سمّيناهما $1$ و$0$، فإنّ ذلك لن يغيّر عدد السلاسل التي نحصل عليها.

إذن ليس مدهشًا أنّ العلاقة نفسها بين مثلث باسكال والمسارات الشبكية تنطبق على السلاسل الثنائية. انظر في السلاسل العشرة أعلاه. يحتوي الصفّ الأول على جميع السلاسل الثنائية في $\B^5_3$ التي تنتهي بـ0. وقبل ذلك الصفر، لدينا سلسلة في $\B^4_3\text{,}$ لأنّها لا بدّ أن يكون طولها 4 ووزنها 3 (فـ0 يزيد الطول ولا يزيد الوزن). ويحتوي الصفّ الثاني على جميع السلاسل الثنائية في $\B^5_3$ التي تنتهي بـ1. وقبل ذلك الواحد، لدينا سلسلة في $\B^4_2\text{,}$ لأنّها لا بدّ أن يكون طولها 4 ووزنها 2 (فـ1 يزيد الطول والوزن معًا). إذن عدد السلاسل الثنائية ذات الخمس بتات ذات الوزن 3 هو مجموع عدد السلاسل الثنائية ذات الأربع بتات ذات الوزن 3 وعدد السلاسل الثنائية ذات الأربع بتات ذات الوزن 2. وبالرموز: $$\begin{equation*} |\B^5_3| = |\B^4_3| + |\B^4_2|\text{.} \end{equation*}$$

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

المثال 3.1.4.

كم عدد السلاسل الثنائية ذات الـ11 بتًا ذات الوزن 5؟

الحل. سيكون هناك $\binom{11}{5}$ سلسلة من هذا النوع. ومن مثلث باسكال نرى أنّ $\binom{11}{5} = 462$

قسم فرعي: المجموعات الجزئية والبيتزا

المجموعة الجزئية (subset) من مجموعة $A$ هي أيّ مجموعة تكون جميع عناصرها في $A\text{.}$ أيضًا. تخيّل أنك تبدأ بالمجموعة $A$ ثمّ تحذف بعضها (أو لا تحذف أيًّا منها أو تحذفها كلّها): فالمجموعة الناتجة مجموعة جزئية من $A\text{.}$ (يمكن العثور على مزيد من المعلومات عن المجموعات في القسم 0.2 والقسم 5.1.)

لنفترض أننا ننظر في المجموعة $A = \{1,2,3,4,5\}\text{.}$ كم عدد المجموعات الجزئية من $A$ التي تحتوي بالضبط على 3 عناصر؟ لنسردها جميعًا: $$\begin{gather*} \{1,2,3\} \qquad \{1,2,4\} \qquad \{1,3,4\} \qquad \{2,3,4\}\\ \{1,2,5\} \qquad \{1,3,5\} \qquad \{2,3,5\} \qquad \{1,4,5\} \qquad \{2,4,5\} \qquad \{3,4,5\}\text{.} \end{gather*}$$

ومرةً أخرى نرى أنّ هناك عشرًا. وفي الحقيقة، لقد سردناها بالترتيب نفسه الذي سردنا به السلاسل الثنائية العشر ذات الخمس بتات ذات الوزن 3، والمسارات الشبكية العشرة من (0,0) إلى (3,2). لكن انتظر، هل لهذا أيّ معنى أصلًا؟ وبأيّ معنى تكون المجموعة الجزئية مساويةً لسلسلة ثنائية؟

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

المثال 3.1.5.

أيّ المجموعات الجزئية من $\{1,2,3,4,5,6\}$ تقابل السلاسل الثنائية أدناه؟ $$\begin{equation*} 101011 \quad 001000 \quad 111111 \quad 000000 \end{equation*}$$

الحل. هنا لا نثبّت وزن السلاسل، لذا لن تكون مجموعاتنا الجزئية كلّها بالحجم نفسه. وهذا هو المقابل:

$101011$	$\{1,3,5,6\}$
$001000$	$\{3\}$
$111111$	$\{1,2,3,4,5,6\}$
$000000$	$\emptyset$

المجموعة الجزئية الأخيرة هي المجموعة الخالية: المجموعة التي لا تحتوي على أيّ عناصر (وكنا يمكننا أن نكتب أيضًا $\{\}$). وهذه مجموعة جزئية من كل مجموعة!

ملاحظة 3.1.6.

ما فعلناه هنا هو إنشاء دالة تقابلية (bijection) بين مجموعة السلاسل الثنائية ذات الخمس بتات ذات الوزن 3 ومجموعة المجموعات الجزئية ذات الـ3 عناصر من $A\text{.}$ والدالة التقابلية هي دالة $f: X \to Y$ بحيث يكون كلّ عنصر من $Y$ صورة عنصر واحد بالضبط من $X\text{.}$ ويمكنك إثبات أنّه إذا كانت هناك دالة تقابلية بين مجموعتين، فإنّ لهما العدد نفسه من العناصر. وهذه تقنية عدّ شائعة سنستعملها في الأقسام القادمة.

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

المثال 3.1.7.

كم عدد المجموعات الجزئية من المجموعة $\{a,b,c,d,e,f,g\}$ التي لها بالضبط 4 عناصر؟

الحل. تحتوي المجموعة على 7 عناصر، لذا فإنّ عدد المجموعات الجزئية ذات الـ4 عناصر هو نفسه عدد السلاسل الثنائية ذات الـ7 بتات ذات الوزن 4، وهو $\binom{7}{4} = 35\text{.}$

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

آآه! إذن هذا هو سبب اهتمامنا بعدّ المجموعات الجزئية!! فكلّ اختيار بيتزا ليس سوى مجموعة جزئية من 3 عناصر من مجموعة الإضافات العشر. والآن نعرف كيف نعدّ ذلك: $\binom{10}{3} = 120$ بيتزا مختلفة.

وماذا لو أردنا مشروبًا إيطاليًا مع العشاء؟ لنقل إنّنا نريد إضافة شرابين مختلفين من بين 13 شرابًا متاحًا. كم عدد المشروبات المختلفة الممكنة؟ هذا ليس سوى عدد المجموعات الجزئية ذات الـ2 عنصر من مجموعة ذات 13 عنصرًا: $\binom{13}{2} = 78\text{.}$

وهذا هو سبب نطقنا بـ$\binom{n}{k}$ على النحو «$n$ اختر $k$». فهو عدد الطرق لاختيار $k$ عنصرًا من مجموعة من $n$ عنصرًا، بما أنّ اختيار $k$ عنصرًا هو بالضبط كيف تبني مجموعة جزئية من $k$ عنصر.

يمكننا أن نرى عدّ المسارات الشبكية على النحو نفسه لاختيار $k$ من $n$ شيءًا: من بين خطوات المسار الـ$n$، نختار $k$ منها لتكون في اتجاه $x$. ويمكن التفكير في السلاسل الثنائية على هذا النحو أيضًا: من بين البتات الـ$n$ في السلسلة، نختار $k$ منها لتكون 1ات.

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

عدّ المجموعات الجزئية.

عدد المجموعات الجزئية ذات الـ$k$ عنصرًا من مجموعة ذات الـ$n$ عنصرًا هو العدد في الصفّ $n\text{,}$ والعمود $k$ من مثلث باسكال: $\binom{n}{k}\text{,}$ وهو ما نقرؤه على النحو «$n$ اختر $k\text{.}$» وهو عدد الطرق لاختيار $k$ عنصرًا من مجموعة من $n$ عنصر.

قسم فرعي: الجبر؟

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

لنفترض أنّك توسّع التعبير ثنائي الحدّ (binomial) $(x+1)^6$ (أي أنّك تضرب ثنائي الحدّ $x+1$ في نفسه ستّ مرّات). قد يكون هذا مملًّا إذا فُعل باليد، لكنّ نظام جبر حاسوبي مثل SageMath يستطيع فعل ذلك بسهولة.

expand((x+1)^6) هل تبدو المعاملات مألوفة؟ انظر في الصفّ السادس من مثلث باسكال: $$\begin{equation*} 1 \quad 6 \quad 15 \quad 20 \quad 15 \quad 6 \quad 1\text{.} \end{equation*}$$ لماذا هذه هي المعاملات؟

جرّب 3.1.8.

عدّل شيفرة SageMath أعلاه لتوسيع $(x+1)^{10}\text{.}$ فما معامل $x^6\text{?}$

.

ولرؤية سبب أنّ هذا أكثر من مجرد تصادف، فلننظر في توسيع $(x+y)^3$ ولنفعله بكلّ دقّة. فنحن في الحقيقة نضرب $$\begin{equation*} (x+y)(x+y)(x+y)\text{.} \end{equation*}$$ وهذا يعني أنّنا سنوزّع ثنائيات الحدّ، ويبدو ذلك على النحو التالي. (سنستعمل خطًّا مختلفًا لكلّ صيغة من صيغ $x$ و$y$ حفاظًا على تتبّع مصدر كلّ شيء.) $$\begin{align*} (x+y)^3 = \amp (x+y)(\x+\y)(\X+\Y)\\ = \amp [(x+y)(\x+\y)]\X + [(x+y)(\x+\y)]\Y\\ = \amp [(x+y)\x + (x+y)\y]\X + [(x+y)\x+ (x+y)\y] \Y\\ = \amp [x\x + y\x + x\y + y\y]\X + [x\x + y\x + x\y + y\y]\Y \\ = \amp x\x\X + y\x\X + x\y\X + y\y\X + x\x\Y + y\x\Y + x\y\Y + y\y\Y\text{.} \end{align*}$$ ويؤدّي هذا التوزيع المكرّر إلى مجموع من الحدود، كلّ حدٍّ منها حاصل ضرب ثلاثة متغيّرات. ونرى أنّ كلّ حدٍّ هو نتيجة اختيار إمّا $x$ أو $y$ من كلّ ثنائي حدّ. فمثلًا، الحدّ $x\y\X$ هو نتيجة اختيار $x$ من ثنائي الحدّ الأول، و$\y$ من الثاني، و$\X$ من الثالث.

لنقل إنّنا نريد إيجاد معامل الحدّ $x^2y$. فنجمع الحدود المتشابهة، ونجمع كلّ الحدود التي اخترنا فيها $x$ مرّتين (و$y$ في المرة الباقية). أو بشكل بديل، يأتي الحدّ $x^2y$ من جميع السلاسل التي فيها $x$ اثنتان وواحدة $y\text{,}$ تمامًا مثل السلسلة الثنائية أو المسار الشبكي. وبغضّ النظر عن الطريقة التي تفكّر بها، فإنّ النتيجة هي أنّ لدينا $\binom{3}{2} = 3$ حدود على الصورة $x^2y\text{.}$

وأرجو أن يكون واضحًا أنّ هذا يعمّم على توسيع $(x+y)^n$ لأيّ عدد صحيح موجب $n\text{.}$ وتُسمّى هذه نظرية ذات الحدّين (binomial theorem).

نظرية 3.1.9. نظرية ذات الحدّين.

يعطي الصفّ الـ$n$ث من مثلث باسكال معاملات توسيع $(x+y)^n\text{.}$ أي أنّه، لأيّ عدد صحيح موجب $n\text{,}$ $$\begin{equation*} (x+y)^n = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \cdots + \binom{n}{n-1}xy^{n-1} + \binom{n}{n}y^n.\text{,} \end{equation*}$$ إذن فإنّ معامل $x^ky^{n-k}$ هو $\binom{n}{k}\text{.}$

ولهذا السبب تُسمّى أعداد مثلث باسكال في الغالب المعاملات الثنائية (binomial coefficients).

المثال 3.1.10.

من دون ضرب ثنائي الحدّ، أعطِ توسيع $(x+y)^5\text{.}$

الحل. نأخذ الصفّ الخامس من مثلث باسكال: $1, 5, 10, 10, 5, 1\text{.}$ ويكون التوسيع عندئذٍ، $$\begin{equation*} (x+y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5. \end{equation*}$$

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

1.

لماذا يكون عدد المسارات الشبكية من $(0,0)$ إلى $(3,5)$ هو نفسه عدد السلاسل الثنائية ذات الـ$8$ بتًا ذات الوزن 5؟

2.

أيّ من أسئلة العدّ التالية إجابتها $\binom{11}{5}\text{?}$ اختر كلّ ما ينطبق.

• كم عدد المسارات الشبكية من $(0,0)$ إلى $(11,5)\text{?}$
• انتبه، فإنّ المسارات من $(0,0)$ إلى $(11,5)$ سيكون طولها $11+5 = 16\text{,}$ لذا ستكون الإجابة عن هذا السؤال هي $\binom{16}{5}\text{.}$
• كم عدد المجموعات الجزئية من $\{1,2,\ldots, 11\}$ التي تحتوي بالضبط على 5 عناصر؟
• صحيح. علينا اختيار 5 عناصر من أصل 11.
• كم عدد السلاسل الثنائية ذات الـ11 بتًا ذات الوزن 5؟
• بالضبط. من بين البتات الإحدى عشرة في السلسلة، علينا اختيار 5 لتكون 1ات.
• كم عدد الطرق التي يمكنك بها اختيار 5 نكهات آيس كريم لكوب آيس كريم ضخم من بين 11 نكهة متاحة؟
• نعم. هذا هو نفسه اختيار 5 عناصر من مجموعة من 11 عنصرًا.

3.

عدد المجموعات الجزئية من $\{1,2,\ldots, 8\}$ ذات الحجم 3 هو نفسه عدد المجموعات الجزئية من $\{1,2,\ldots, 7\}$ ذات الحجم إمّا $2$ أو $3\text{.}$ اشرح لماذا يبدو هذا منطقيًا.

4.

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