---
title: "العدّ"
book: "الرياضيات الجامعية — السنة 1"
subject: math
language: ar
chapter: 2
exercises: 12
source: https://one-course.com/books/math/3/ar/chapter/2-counting
---

# الفصل 2 — العدّ

يبدو عدّ المجموعات [المنتهية](#def-b1-counting-card) أمرًا ابتدائيًا — ثم يصير دقيقًا سريعًا. يعرّف هذا الفصل [عدد العناصر](#def-b1-counting-card) تعريفًا سليمًا (عبر التقابلات، على نهج [الفصل 1](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#ch-b1-logic))، ويرسي مبادئ العدّ القليلة التي يتفرع عنها كل شيء، ثم يستخرج الأعداد الكلاسيكية: القوائم والتبديلات والأجزاء والمعاملات الثنائية.

## 2.1 عدد عناصر مجموعة منتهية

**تعريف 2.1 (المجموعة المنتهية، عدد العناصر).**

من أجل $n \in \N^*$، نكتب $\intint{1}{n} = \{1, 2, \dots,
n\}$. تكون [المجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $E$ *منتهية* عندما تكون $E = \emptyset$ أو يوجد تقابل من $\intint{1}{n}$ على $E$ من أجل $n \in \N^*$ ما؛ وهذا العدد $n$ وحيد ([المبرهنة 2.2](#thm-b1-counting-welldef)) وهو *عدد عناصر* $E$، ويُكتب $\abs{E}$ (مع $\abs{\emptyset} = 0$).

**مبرهنة 2.2 (عدد العناصر معرَّف تعريفًا سليمًا).**

إذا كان $m \neq n$ فلا يوجد تقابل من $\intint{1}{m}$ على $\intint{1}{n}$. وبدقة أكبر، إذا كان $m > n$ فلا يوجد [تطبيق متباين](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) من $\intint{1}{m}$ في $\intint{1}{n}$.

**برهان.** نبرهن بالاستقراء على $n$ على [العبارة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-statement) التالية: *لكل $m > n$ لا يوجد [تطبيق متباين](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) $\intint{1}{m} \to \intint{1}{n}$*. من أجل $n = 0$ تكون [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) الوصول خالية و $m \geq 1$: فلا وجود لأيّ [تطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) البتة. ولنفترض [العبارة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-statement) صحيحة من أجل $n$، ولنفترض أن $f \colon
\intint{1}{m} \to \intint{1}{n+1}$ [تطبيق متباين](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) مع $m > n + 1$. إذا لم تُبلغ القيمة $n + 1$ كان $f$ تطبيقًا [متباينًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) في $\intint{1}{n}$، وهذا يناقض فرض الاستقراء. وإلا فإن $f(a) = n + 1$ من أجل $a$ واحد بالضبط؛ فنبدّل بين $f(a)$ و $f(m)$ (وصوريًا: نركّب مع منقولة القيمتين)، فيصير [التطبيق المتباين](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) الجديد $g$ يحقق $g(m) = n + 1$. عندئذ يكون قصر $g$ على $\intint{1}{m-1}$ تطبيقًا [متباينًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) في $\intint{1}{n}$ مع $m - 1 > n$ — وهذا تناقض من جديد. ∎

**نتيجة 2.3 (مبدأ الأدراج).**

إذا كان $\abs{E} > \abs{F}$ فلا يكون أيّ [تطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) $f \colon E \to F$ [متباينًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj): أي أن عنصرين من $E$ يشتركان في صورتهما.

**برهان.** نكتب $\abs E = m$ و $\abs F = n$ مع $m > n$، ونختار تقابلين $u \colon \intint1m \to E$ و$v \colon F \to \intint1n$. لو كان $f$ [متباينًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) لكان $v \circ f \circ u$ تطبيقًا [متباينًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) من $\intint1m$ في $\intint1n$ (فهو تركيب تطبيقات متباينة، [القضية 1.26](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#prop-b1-logic-comp))، وهذا يناقض [المبرهنة 2.2](#thm-b1-counting-welldef). ∎

**ملاحظة 2.4 (استراحة: لماذا التبديل في برهان المبرهنة؟).**

يحوي برهان [المبرهنة 2.2](#thm-b1-counting-welldef) أولَ حركة بارعة حقًّا في الفصل، وهي جديرة بأن تُعاد ببطء. والعقبة هي: أننا نريد، [لتطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) فرض الاستقراء، أن نحذف النقطة الأخيرة $m$ من [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) التعريف *و* النقطة الأخيرة $n+1$ من [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) الوصول، لكن $f$ قد يرسل نقطة أخرى $a$ إلى $n
+ 1$، فيُفسد حذف نقطة الوصول عندئذ [التطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) في موضع آخر. والعلاج: أن نركّب $f$ مع منقولة *القيمتين* $f(a)$ و $f(m)$ — وهي تقابل [لمجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) الوصول، فيُحفظ التباين — وبعدها تستقر القيمة المزعجة $n + 1$ في الموضع غير المؤذي $m$، فيصير الحذفان نظيفين. وهذا النمط، «سوِّ أولًا ثم اقطع»، يتكرر: فهو الذي يعيد به تراجع الاضطرابات توجيه $\sigma^{-1}(n+1)$ في مسألة نهاية الأسبوع من هذا الفصل، وهو كيفية ترقيع التبديلات في مسألة الزمرة المتناظرة من [الفصل 7](https://one-course.com/books/math/3/ar/chapter/7-algebraic-structures#ch-b1-structures).

**قضية 2.5 (التطبيقات المتباينة والشاملة وعدد العناصر).**

لتكن $E, F$ مجموعتين منتهيتين حيث $\abs{E} = \abs{F}$، وليكن $f \colon E
\to F$. عندئذ

$$
f \text{ متباين} \iff f \text{ شامل} \iff f \text{ تقابليّ}.
$$

**برهان.** نفترض $f$ [متباينًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj). عندئذ يكون $f$ تقابلًا من $E$ على $f(E)$، ومنه $\abs{f(E)} = \abs{E} = \abs{F}$. ولو فات $f(E)$ نقطة $y_0$ من $F$ لكان $f$ تطبيقًا [متباينًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) من $E$ في $F \setminus \{y_0\}$، وهي [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) عدد عناصرها $\abs{F} - 1 < \abs{E}$ — وهذا مستحيل حسب مبدأ الأدراج. إذن $f(E) = F$: أي أن $f$ شامل، فهو إذن تقابليّ.

ونفترض $f$ [شاملًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj). نختار من أجل كل $y \in F$ سابقةً واحدة $s(y)
\in E$؛ عندئذ $f \circ s = \mathrm{id}_F$، فيكون $s$ [متباينًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) ([القضية 1.26](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#prop-b1-logic-comp)). وبتطبيق الفقرة السابقة على $s$ (فعددا العناصر متساويان) يكون $s$ [تقابليًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj). ومن $f \circ s =
\mathrm{id}_F$ نحصل على $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$، ومنه يكون $f$ [تقابليًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj). وأخيرًا فإن [التطبيق التقابلي](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) متباين وشامل معًا بحكم التعريف، وبهذا تُغلق دورة الاستلزامات. ∎

**مثال 2.6 (الانتهاء شرط جوهري).**

على [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) *[منتهية](#def-b1-counting-card)* تكون [القضية 2.5](#prop-b1-counting-injsur) اختصارًا قويًا: فأيّ [تطبيق متباين](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) من $E$ إلى نفسها هو تلقائيًا [تبديلة](#def-b1-counting-objects) في $E$ — أي أن نصف التقابلية يأتي مجانًا. وينهار الاستلزامان معًا على المجموعات اللانهائية: [فالتطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) $n \mapsto n + 1$ متباين من $\N$ إلى $\N$ لكنه يفوت $0$، [والتطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) $\N \to \N$ الذي يرسل $0 \mapsto 0$ و $n \mapsto n - 1$ من أجل $n \geq 1$ شامل وغير متباين. وكلما استُدعيت هذه القضية كان فرض الانتهاء يقوم بعمل حقيقي — وهو موضوع تستكشفه مسألة نهاية الأسبوع في [الفصل 1](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#ch-b1-logic) من الجهة المقابلة، حيث تكون المجموعات اللانهائية هي بالضبط تلك التي تقبل تطبيقات ذاتية كهذه.

**مثال 2.7 (نصف العمل، مجانًا).**

تأمّل [التطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) $f$ على $\{0, 1, \dots, 6\}$ الذي يرسل $k$ إلى باقي قسمة $3k$ على $7$؛ وجدول قيمه هو

$$
0,\ 3,\ 6,\ 2,\ 5,\ 1,\ 4 .
$$

هل $f$ تقابل؟ يكفي التباين وحده ([القضية 2.5](#prop-b1-counting-injsur)): فإذا كان للعددين $3k$ و $3k'$ الباقي نفسه قسم $7$ الفرق $3(k - k')$، وبما أن $7$ أوليّ ولا يقسم $3$ فإنه يقسم $k - k'$ (مبرهنة إقليدس المساعدة، المستعملة هنا على مستوى الثانوية والمبرهن عليها في [الفصل 6](https://one-course.com/books/math/3/ar/chapter/6-integer-arithmetic#ch-b1-arith))؛ ومع $\abs{k - k'} \leq 6$ يفرض هذا $k = k'$. ويأتي الشمول مجانًا — دون حاجة إلى حلّ $3k \equiv c$ من أجل كل $c$، وإن كان الجدول يؤكد ظهور كل قيمة مرة واحدة بالضبط. وهذا الاختصار عتيد: فهو يبرهن على قابلية الضرب الترديدي للقلب ([الفصل 6](https://one-course.com/books/math/3/ar/chapter/6-integer-arithmetic#ch-b1-arith))، وهو محرك الازدواج في مبرهنة ويلسون، ويعود في الجبر الخطي في صورة «تشاكل ذاتي لفضاء منته البُعد يكون [متباينًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) إذا وفقط إذا كان [شاملًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj)» ([الفصل 19](https://one-course.com/books/math/3/ar/chapter/19-finite-dimension#ch-b1-findim)).

## 2.2 مبادئ العدّ

**قضية 2.8 (قاعدتا الجمع والجداء).**

لتكن $E, F$ مجموعتين منتهيتين.

1. إذا كان $E \cap F = \emptyset$ فإن $\abs{E \cup F} = \abs{E} +  \abs{F}$ ؛ وبعمومية أكبر، من أجل تجزئة $E$ إلى قطع $E_1, \dots, E_k$ ، لدينا $\abs{E} = \sum_i \abs{E_i}$ .
2. وفي الحالة العامة، $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap  F}$ .
3. $\abs{E \times F} = \abs{E} \times \abs{F}$ .
4. [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) كل التطبيقات من $E$ إلى $F$ ، وهي $F^E$ ، تحقق $\abs{F^E} = \abs{F}^{\abs{E}}$ .
5. $\abs{\mathcal{P}(E)} = 2^{\abs{E}}$ .

**برهان.** (1) نصل التعدادين: إذا كانت $E = \{x_1, \dots, x_m\}$ و$F =
\{y_1, \dots, y_n\}$ دون تكرار فإن $x_1, \dots, x_m, y_1,
\dots, y_n$ تعدّد $E \cup F$ دون تكرار (بحكم الانفصال). ويمدّد الاستقراء ذلك إلى $k$ قطعة.

(2) [المجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $E \cup F$ اتحاد منفصل للمجموعتين $E$ و $F \setminus E$، و $F$ اتحاد منفصل للمجموعتين $F \cap E$ و $F \setminus E$؛ ومنه $\abs{E \cup F} = \abs{E} + \abs{F \setminus E} = \abs{E} + \abs{F} -
\abs{E \cap F}$.

(3) [المجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $E \times F$ اتحاد منفصل، على $x \in E$، للمجموعات $\{x\} \times F$ التي [عدد عناصر](#def-b1-counting-card) كلٍّ منها $\abs{F}$؛ فطبّق (1).

(4) [التطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) من $E = \{x_1, \dots, x_m\}$ إلى $F$ هو بالضبط اختيار المتتالية [المنتهية](#def-b1-counting-card) ذات $m$ حدًّا $(f(x_1), \dots, f(x_m)) \in F^m$؛ وهذا التقارن تقابل، و $\abs{F^m} = \abs{F}^m$ حسب (3) وبالاستقراء.

(5) أجزاء $E$ تقابل تطبيقات $E \to \{0, 1\}$ (أرسل $A$ إلى دالتها المميِّزة)؛ فطبّق (4). ∎

**مثال 2.9 (العدّ بالمتمّمة).**

كم عدد الرموز السرّية المكوَّنة من $4$ أرقام (الأرقام $0$–$9$، والترتيب مهمّ، والتكرار مسموح) التي تحوي رقمًا مكررًا *واحدًا على الأقل*؟ عدّها مباشرةً يعني التلاعب بالحالات «زوج واحد بالضبط، أو زوجان، أو ثلاثيّ، أو رباعيّ» — وهي خمس تشكيلات متداخلة. عُدَّ المتمّمة بدلًا من ذلك: عدد كل الرموز هو $10^4 = 10\,000$ (بقاعدة الجداء)، وعدد الرموز ذات الأرقام الأربعة المتمايزة هو $10 \times 9 \times 8 \times 7 = 5\,040$ (وهي الترتيبات من الرتبة $4$)، فيكون الجواب

$$
10^4 - 10 \cdot 9 \cdot 8 \cdot 7 = 10\,000 - 5\,040 = 4\,960 .
$$

أي إن قرابة نصف الرموز السرّية تكرّر رقمًا. والفكرة النافذة: كلما صيغ عدٌّ [بعبارة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-statement) «على الأقل» أو «ليس كلها» فجرّب المتمّمة أولًا — إذ تضمن قاعدة الجمع أن $\abs{A} = \abs{E} - \abs{\overline A}$، وكثيرًا ما تكون المتمّمة تشكيلة واحدة نظيفة.

**مثال 2.10 (مسارات الشبكة).**

عُدَّ أقصر المسارات من الزاوية $(0,0)$ إلى الزاوية $(4, 3)$ في شبكة، بالتحرك خطوةً واحدة نحو اليمين (ي) أو خطوةً واحدة نحو الأعلى (ف) في كل مرة. يقطع كل مسار كهذا $7$ خطوات، منها $4$ من النوع ي و $3$ من النوع ف؛ وبالعكس، فإن أيّ كلمة طولها $7$ من الحرفين ي و ف فيها أربعة أحرف ي تصف مسارًا واحدًا بالضبط. فالمسارات تقابل إذن اختيارات مواضع الحروف ي:

$$
\binom{7}{4} = 35 .
$$

والفكرة النافذة هي *الترميز*: فقد صار العدّ بديهيًا لحظة تُرجم كل مسار إلى كلمة، أي إلى جزء من المواضع — وهو مثال آخر على الشعار القائل إن كل عدّ صحيح تقابلٌ متنكّر ([الطريقة 2.19](#met-b1-counting-which)).

![أحد المسارات القصرى، وعددها 74 = 35، من (0,0) إلى (4,3): يرمّز المسار المرسوم الكلمة يفييفيف، أي اختيار المواضع \1,3,4,6\ للحرف ي من بين الخطوات السبع.](https://one-course.com/images/onecourse/chapters/math-3/b1-counting/fig-7a471b31a037.svg)

*أحد المسارات القصرى، وعددها $\binom74 = 35$، من $(0,0)$ إلى $(4,3)$: يرمّز المسار المرسوم الكلمة يفييفيف، أي اختيار المواضع $\{1,3,4,6\}$ للحرف ي من بين الخطوات السبع.*

## 2.3 القوائم والتبديلات والأجزاء

**تعريف 2.11 (الترتيبات والتبديلات والتوفيقات).**

لتكن $E$ [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) حيث $\abs{E} = n$ وليكن $0 \leq k \leq n$.

- *الترتيبة من الرتبة $k$* في $E$ هي متتالية [منتهية](#def-b1-counting-card) متباينة من $k$ عنصرًا من $E$ (أي اختيار مرتَّب دون تكرار)؛
- و *التبديلة* في $E$ هي تقابل من $E$ إلى نفسها — أي، على نحو مكافئ، ترتيبة من الرتبة $n$ ؛
- و *التوفيقة من الرتبة $k$* هي جزء من $E$ فيه $k$ عنصرًا (أي اختيار غير مرتَّب دون تكرار). ويُكتب عددها $\binom{n}{k}$ ، ويُقرأ « $n$ توفيق $k$ » .

**مبرهنة 2.12 (الأعداد الثلاثة).**

حيث $n = \abs{E}$ و $0 \leq k \leq n$:

1. عدد الترتيبات من الرتبة $k$ في $E$ هو $n (n-1) \cdots  (n-k+1) = \dfrac{n!}{(n-k)!}$ ؛
2. وعدد التبديلات في $E$ هو $n!$ ؛
3. و $\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ .

**برهان.** (1) نختار المركّبة الأولى ($n$ طريقة)، ثم الثانية ($n - 1$ اختيارًا متبقيًا)، …، ثم المركّبة ذات الرتبة $k$ ($n - k + 1$ اختيارًا). وصوريًا نستقرئ على $k$. من أجل $k = 1$ توجد $n$ متتالية متباينة ذات حدّ واحد. ولنفترض العدّ صحيحًا من أجل $k - 1$. كل ترتيبة $(x_1, \dots, x_k)$ من الرتبة $k$ تُستخرج من ترتيبة واحدة بالضبط من الرتبة $(k-1)$ — هي بترها $(x_1, \dots, x_{k-1})$ — بإلحاق مركّبة أخيرة خارج $\{x_1, \dots,
x_{k-1}\}$، ولها بالضبط $n - (k - 1)$ قيمة متاحة. فتنقسم الترتيبات من الرتبة $k$ إذن، بالبتر، إلى صفوف حجمها المشترك $n - k + 1$ مفهرسة بالترتيبات من الرتبة $(k-1)$، وتعطي قاعدة الجمع

$$
\frac{n!}{(n-k+1)!}\;(n - k + 1) = \frac{n!}{(n-k)!} .
$$

(2) هي (1) مع $k = n$.

(3) كل جزء من $k$ عنصرًا يُرتَّب في $k!$ ترتيبة متمايزة من الرتبة $k$، وكل ترتيبة من الرتبة $k$ تنشأ من جزء واحد بالضبط: ومنه $\frac{n!}{(n-k)!} = \binom nk \cdot k!$. ∎

**مثال 2.13 (الموائد المستديرة: القسمة على التناظر).**

بكم طريقة يجلس $n$ ضيفًا حول مائدة مستديرة، إذا اعتُبر جلوسان متطابقين عندما يكون لكل ضيف الجاران نفسهما عن يمينه ويساره — أي بغضّ النظر عن الدوران؟ كل جلوس دائري يقابل $n$ جلوسًا خطيًا بالضبط (اقطع الدائرة عند أيّ موضع من المواضع $n$)، فتنطوي الترتيبات الخطية $n!$ في مجموعات من $n$:

$$
\frac{n!}{n} = (n-1)! \quad\text{جلوسًا دائريًا.}
$$

وعلى نحو مكافئ: أجلس ضيفًا مميَّزًا حيث شئت (فتقتل الحرية الدورانية)، ثم رتّب الضيوف $n - 1$ الباقين باتجاه عقارب الساعة. ومن أجل $n = 6$: $120$ مائدة. ويوضح الحلّان العلاجين المعياريين للعدّ الزائد: إمّا القسمة على عدد التكرارات بالضبط، وإمّا *كسر التناظر* بتثبيت غرض واحد. ويقتضي كلاهما أن يكون حجم زمرة التكرارات نفسه في كل تشكيلة — وهو ما استعمله كذلك برهان الصيغة $\binom nk = \frac{n!}{k!\,(n-k)!}$ أعلاه، مع $k!$ بدل $n$.

**مثال 2.14 (إضافة قيد).**

ولنواصل مع المائدة المستديرة: من بين الموائد $(n-1)!$ ذات $n \geq
3$ ضيفًا، كم مائدة تجلس ضيفين معطيين $A$ و $B$ *متباعدين* (أي غير متجاورين)؟ عُدَّ المتمّمة. أمّا الموائد التي يجلس فيها $A$ و $B$ معًا: فألصقهما في كتلة واحدة — فيصير لدينا $n - 1$ غرضًا حول المائدة، أي $(n-2)!$ [ترتيبًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-order) دائريًا — ثم رتّب الضيفين داخل كتلتهما ($2$ طريقة): فيكون عدد الموائد المتجاورة $2\,(n-2)!$. ومنه

$$
(n-1)! - 2\,(n-2)! = (n-2)!\,\bigl((n - 1) - 2\bigr)
= (n-3)\,(n-2)!
$$

مائدةً تُبقيهما متباعدين. وللتحقق: $n = 3$ يعطي $0$ (فحول مثلث يلامس الجميعُ الجميعَ) و $n = 4$ يعطي $2$، ويسهل سردهما باليد. وحيلة الإلصاق — بمعاملة كتلة مفروضة كغرض واحد ثم عدّ ترتيباتها الداخلية — هي العلاج المعياري لقيود التجاور، خطيةً كانت أو دائرية.

**قضية 2.15 (متطابقات أساسية).**

من أجل $0 \leq k \leq n$:

$$
\binom{n}{k} = \binom{n}{n-k},
\qquad
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
\quad (1 \leq k \leq n-1),
\qquad
\sum_{k=0}^{n} \binom{n}{k} = 2^n .
$$

**برهان.** المتطابقة الأولى: [التطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) $A \mapsto E \setminus A$ تقابل بين الأجزاء ذات $k$ عنصرًا والأجزاء ذات $(n-k)$ عنصرًا. وأمّا قاعدة باسكال: فثبّت عنصرًا $a \in E$؛ تنقسم الأجزاء ذات $k$ عنصرًا إلى تلك التي تحتوي $a$ (فنختار العناصر $k - 1$ الأخرى: $\binom{n-1}{k-1}$) وتلك التي تتفادى $a$ ($\binom{n-1}{k}$). وأمّا المتطابقة الثالثة: فكلا الطرفين يعدّ جميع أجزاء $E$، مقسومةً بحسب الحجم في الطرف الأيسر ([القضية 2.8](#prop-b1-counting-rules) (1) و (5)). ∎

**مبرهنة 2.16 (مبرهنة ثنائي الحدّ).**

لكل $a, b$ في حلقة تبديلية (مثل $\R$ أو $\C$) ولكل $n \in \N$:

$$
(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{\,n-k} .
$$

**برهان.** نشر $(a+b)(a+b)\cdots(a+b)$ توزيعيًا يعطي حدًّا واحدًا لكل اختيار، في كل عامل، بين $a$ و $b$: فيظهر الحدّ $a^k b^{n-k}$ مرةً واحدة لكل طريقة لاختيار العوامل $k$ من بين العوامل $n$ التي تسهم بالمقدار $a$ — أي $\binom nk$ مرة. (وبطريقة أخرى: استقرِ على $n$ باستعمال قاعدة باسكال.) ∎

**مثال 2.17.**

تخصيصان كلاسيكيان: $a = b = 1$ يستعيد $\sum_k \binom nk
= 2^n$؛ و $a = -1$ و $b = 1$ يعطيان $\sum_{k} (-1)^k \binom nk = 0$ من أجل $n \geq 1$: أي إن نصف أجزاء [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) غير خالية بالضبط له [عدد عناصر](#def-b1-counting-card) زوجيّ.

**مثال 2.18 (متطابقة واحدة ببرهانين).**

التخصيص $a = 2$ و $b = 1$ في مبرهنة ثنائي الحدّ يعطي

$$
\sum_{k=0}^{n} \binom nk\,2^k = 3^n .
$$

وإليك المتطابقة نفسها دون أيّ جبر البتة. الطرف الأيمن يعدّ الكلمات ذات الطول $n$ على الأبجدية $\{0, 1, 2\}$ (بقاعدة الجداء). صنّف كل كلمة بحسب [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) المواضع $K$ التي تحمل حرفًا غير معدوم: فاختيار $K$ حيث $\abs K = k$ يكلّف $\binom nk$، ثم يحمل كل موضع من $K$ الحرف $1$ أو $2$ باستقلال: أي $2^k$ طريقة. وتعطي قاعدة الجمع على $k$ الطرف الأيسر. وإلى جانب متعة التوافق، لكلّ من البرهانين فضيلته: فالجبريّ يُعمَّم على أيّ قيمة للمقدار $a$، والتوفيقيّ *يشرح* الصيغة ويتكيّف مع قيود (كمنع الحرف $2$ في الموضع الأخير مثلًا) لا يلتقطها أيّ تعويض. والإبقاء على التقنيتين نشطتين هو المهارة العملية التي يدرّبها هذا الفصل.

**طريقة 2.19 (أيّ عدّ ينطبق؟).**

قبل الحساب، أجب عن سؤالين يخصّان الاختيار: هل *الترتيب* مهمّ، وهل *التكرار* مسموح؟

|  | الترتيب مهمّ | الترتيب غير مهمّ |
| --- | --- | --- |
| دون تكرار | $\dfrac{n!}{(n-k)!}$ | $\dbinom{n}{k}$ |
| [6pt] بتكرار مسموح | $n^k$ | ([التمرين 2.10](#exo-b1-counting-10)) |

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

**ملاحظة 2.20 (مزالق شائعة في العدّ).**

1. *جمع حالات غير منفصلة.* تقتضي قاعدة الجمع وجود تجزئة؛ فإذا كانت تشكيلة ما قد تحقق حالتين في آن واحد عُدَّت مرتين — والعلاج هو الاحتواء والاستبعاد ( [المبرهنة 2.24](#thm-b1-counting-inclexcl) ) أو تقسيم أدقّ للحالات.
2. *المرتَّب في مقابل غير المرتَّب.* اختيار «لجنة من اثنين» هو $\binom n2$ ، لا $n(n-1)$ : فقرّر *قبل الحساب* إن كان الاختيار يحمل [ترتيبًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-order) ، وإذا كان العدّ المرتَّب أسهل فاقسم في النهاية على عدد الترتيبات — لكن بشرط أن ينشأ كل غرض غير مرتَّب من العدد *نفسه* من الأغراض المرتَّبة.
3. *اختيارات على مراحل غير مستقلة.* تقتضي قاعدة الجداء أن يكون عدد الخيارات في كل مرحلة مستقلًا عن الاختيارات السابقة. فقولنا «اختر قائدًا ثم نائبًا مختلفًا عنه» سليم ( $n(n-1)$ )؛ أمّا «اختر لاعبين ينسجمان معًا» فليس جداءً على مرحلتين البتة.
4. *العدّ المزدوج بحكم الإنشاء.* بناء كل غرض مرتين — مثل عدّ الأيدي التي فيها آسٌ *واحد على الأقل* بحاصل (اختر آسًا) $\times$ (اختر $4$ أوراق أخرى) — يعدّ الأيدي ذات الآسين عدًّا زائدًا. [فعبارة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-statement) «على الأقل» تستدعي المتمّمة في كل الأحوال تقريبًا ( [المثال 2.9](#ex-b1-counting-complement) ).

**مثال 2.21 (عدٌّ على طريقة البوكر).**

من رزمة فيها $52$ ورقة، عدد الأيدي المكوَّنة من $5$ أوراق هو $\binom{52}{5} = 2\,598\,960$. وأمّا الأيدي التي تحوي آسًا واحدًا بالضبط: فاختر الآس ($4$ طرق) ثم $4$ أوراق من بين $48$ ورقة غير آس: $4 \binom{48}{4} = 778\,320$. وتنطبق قاعدة الجداء لأن الاختيار ينقسم إلى مراحل مستقلة.

**طريقة 2.22 (العدّ المزدوج).**

للبرهان على متطابقة بين تعبيرين عدديين، جد [مجموعة منتهية](#def-b1-counting-card) واحدة يعدّها الطرفان معًا — وهي عادةً [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) من *الأزواج* — ثم احسب عدد عناصرها بترتيبين مختلفين. والنموذج الأصلي هو *مبرهنة المصافحات* المساعدة: في حفل ما، عُدَّ الأزواج (شخص، يد صافحها). فالجمع على الأشخاص يعطي $\sum_p d_p$ (أي عدد مصافحات كل شخص $p$)؛ والجمع على المصافحات يعطي ضعف عدد المصافحات (إذ تضمّ كل مصافحة شخصين). ومنه فإن $\sum_p d_p$ زوجيّ — فعدد الأشخاص الذين صافحوا عددًا فرديًا من الأيدي زوجيّ دائمًا، وهو استنتاج غير بديهي حصلنا عليه دون أيّ صيغة البتة. والمحرك نفسه يشغّل [التمرين 2.12](#exo-b1-counting-12) وعدة أسئلة من مسألة نهاية الأسبوع أدناه.

**مثال 2.23 (الجزء المتوسط).**

ما متوسط [عدد عناصر](#def-b1-counting-card) جزء من [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $E$ فيها $n$ عنصرًا، إذا كانت الأجزاء $2^n$ جميعها متساوية الاحتمال؟ عُدَّ عدًّا مزدوجًا الأزواج $(A, a)$ حيث $a \in A$: فالجمع على الأجزاء يعطي $\sum_A \abs A$، وهو المجموع المطلوب؛ والجمع على العناصر يعطي $n \cdot 2^{n-1}$ (إذ يقع كلٌّ من العناصر $n$ في نصف الأجزاء بالضبط — فازدوج كل $A$ يحتوي $a$ مع $A
\setminus \{a\}$). ومنه

$$
\frac{1}{2^n}\sum_{A \subseteq E} \abs A
= \frac{n\,2^{n-1}}{2^n} = \frac n2 :
$$

أي إن الأجزاء نصف ممتلئة في المتوسط — كما يتنبأ به كذلك التناظر $A
\leftrightarrow \overline A$ (الذي يزدوج الحجمين $k$ و $n - k$). برهانان وجواب واحد، وكلاهما يتفادى الحساب المباشر $\sum_k k\binom nk$ في [التمرين 2.5](#exo-b1-counting-5): فكثيرًا ما يعوّض ازدواجٌ حسن الاختيار عن متطابقة.

## 2.4 الاحتواء والاستبعاد

**مبرهنة 2.24 (الاحتواء والاستبعاد).**

من أجل مجموعات [منتهية](#def-b1-counting-card) $A_1, \dots, A_p$:

$$
\Bigl|\, \bigcup_{i=1}^{p} A_i \,\Bigr|
= \sum_{\emptyset \neq I \subseteq \intint{1}{p}}
(-1)^{\abs{I}+1} \Bigl|\, \bigcap_{i \in I} A_i \,\Bigr| .
$$

ومن أجل $p = 3$: $\abs{A \cup B \cup C} = \abs A + \abs B + \abs C - \abs{A \cap B} -
\abs{A \cap C} - \abs{B \cap C} + \abs{A \cap B \cap C}$.

**برهان.** ثبّت عنصرًا $x$ من الاتحاد وعُدَّ إسهامه في الطرف الأيمن. لتكن $J = \{i : x \in A_i\}$، وعدد عناصرها $m \geq
1$. يُعدّ العنصر $x$ مرة واحدة في $\abs{\bigcap_{i \in I} A_i}$ تحديدًا عندما $\emptyset \neq I \subseteq J$، بالإشارة $(-1)^{\abs I + 1}$؛ فيكون إسهامه الكلي

$$
\sum_{k=1}^{m} \binom{m}{k} (-1)^{k+1}
= 1 - \sum_{k=0}^{m} \binom mk (-1)^k = 1 - 0 = 1
$$

حسب [المثال 2.17](#ex-b1-counting-binomial). إذن يُعدّ كل عنصر من الاتحاد مرة واحدة بالضبط. ∎

**مثال 2.25 (عدّ الأعداد الأولية فيما بينها).**

كم عددًا صحيحًا من $\intint1{120}$ يكون أوليًا مع $120 = 2^3
\times 3 \times 5$؟ يشترك عدد صحيح في عامل مع $120$ تحديدًا عندما يقبل القسمة على $2$ أو $3$ أو $5$، فعُدَّ متمّمة $A_2 \cup A_3 \cup A_5$، حيث تجمع $A_d$ مضاعفات $d$. وداخل $\intint1{120}$ يكون عدد مضاعفات $d$ هو $120/d$ كلما قسم $d$ العدد $120$ — دون حاجة إلى دوال الجزء الصحيح — ولدينا $A_2 \cap A_3 = A_6$ وهكذا. وبالاحتواء والاستبعاد:

$$
\abs{A_2 \cup A_3 \cup A_5}
= 60 + 40 + 24 - 20 - 12 - 8 + 4 = 88 ,
$$

ومنه فإن $120 - 88 = 32$ عددًا صحيحًا أوليّ مع $120$. ومن المفيد إعادة تجميع الحساب في صورة جداء:

$$
120 - 88 = 120\Bigl(1 - \frac12\Bigr)\Bigl(1 -
\frac13\Bigr)\Bigl(1 - \frac15\Bigr) = 120 \cdot \frac12 \cdot
\frac23 \cdot \frac45 = 32 :
$$

فنشر الأقواس الثلاثة يعيد إنتاج الحدود المؤشَّرة الثمانية للاحتواء والاستبعاد بالضبط، حدًّا لكل جزء من $\{2, 3,
5\}$. وهذه الصورة الجدائية تعرّف دالة أويلر المؤشِّرة، التي يظهر دورها الحسابي مع توافقات [الفصل 6](https://one-course.com/books/math/3/ar/chapter/6-integer-arithmetic#ch-b1-arith) ويُطوَّر في مجلد السنة 2.

**مثال 2.26 (الاضطرابات).**

*الاضطراب* [تبديلة](#def-b1-counting-objects) بلا نقطة صامدة. لتكن $A_i$ [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) تبديلات $\intint{1}{n}$ التي تصمد عندها $i$؛ عندئذ $\abs{\bigcap_{i \in I} A_i} = (n - \abs I)!$، ويعدّ الاحتواء والاستبعاد التبديلات ذات نقطة صامدة واحدة على الأقل؛ فيكون عدد الاضطرابات

$$
D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .
$$

وبما أن $\sum (-1)^k / k! \to \eu^{-1}$ (انظر [الفصل 17](https://one-course.com/books/math/3/ar/chapter/17-numerical-series#ch-b1-series))، فإن قرابة $37\%$ من جميع التبديلات اضطرابات، مهما تكن $n$.

**ملاحظة 2.27 (أين يُستعمل هذا الفصل).**

المعاملات الثنائية أكثر أغراض هذا الفصل إعادةَ استعمال: فهي تحرّك مبرهنة ثنائي الحدّ في [الفصل 8](https://one-course.com/books/math/3/ar/chapter/8-polynomials#ch-b1-poly) (نشر $(X + a)^n$)، وصيغة لايبنتز للمشتقة من الرتبة $n$ لجداء في [الفصل 14](https://one-course.com/books/math/3/ar/chapter/14-differentiation#ch-b1-derivative)، ومعاملات نشور تايلور في [الفصل 16](https://one-course.com/books/math/3/ar/chapter/16-taylor-formulas-and-asymptotic-expansions#ch-b1-taylor). وتعود التبديلات في صورة زمرة — مع الإشارة المبنية على عدّ الانقلابات — في [الفصل 7](https://one-course.com/books/math/3/ar/chapter/7-algebraic-structures#ch-b1-structures)، وتعرّف الإشارةُ بدورها المحدداتِ في [الفصل 22](https://one-course.com/books/math/3/ar/chapter/22-determinants-and-linear-systems#ch-b1-det). والاحتواء والاستبعاد ومبادئ العدّ هي العمود الفقري المنتهي للاحتمال المتقطع، الذي يُطوَّر في مجلد السنة 2؛ أمّا أعداد الاضطراب في [المثال 2.26](#ex-b1-counting-derangement) فتُدرس بعمق في مسألة نهاية الأسبوع أدناه.

## 2.5 تمارين

**تمرين 2.1 ★.**

تتكوّن لوحة الترقيم من حرفين (من A إلى Z)، ثم ثلاثة أرقام، ثم حرفين. كم لوحة ممكنة؟ وكم منها بلا حرف مكرر بين الحروف الأربعة؟

**حل التمرين 2.1.**

مراحل مستقلة وقاعدة الجداء: $26^2 \times 10^3 \times 26^2
= 26^4 \times 1000 = 456\,976\,000$ لوحة. وإذا كانت الحروف الأربعة متمايزة مثنى مثنى كوّنت مراحل الحروف ترتيبةً من الرتبة $4$ في الأبجدية: $26 \times 25 \times 24 \times 23 = 358\,800$ طريقة، ومنه $358\,800 \times 1000 = 358\,800\,000$ لوحة.

**تمرين 2.2 ★.**

كم قلبًا (أي إعادة ترتيب للحروف، ذا معنى أو بلا معنى) لكلمة برتقال ؟ وكم لكلمة بانانا ؟

**حل التمرين 2.2.**

لكلمة برتقال $6$ حروف متمايزة: أي $6! = 720$ قلبًا. ولكلمة بانانا $6$ حروف بتكرار ($3$ من الحرف ا، و $2$ من الحرف ن، و $1$ من الحرف ب): فكل قلب محدَّد بمواضع حروف ا ($\binom 63$ اختيارًا)، ثم بمواضع حروف ن من بين المواضع $3$ الباقية ($\binom 32$)، ويأخذ الحرف ب الموضع الأخير: $\binom{6}{3}\binom{3}{2} = 20 \times 3 = 60$ قلبًا (أي، على نحو مكافئ، $6!/(3!\,2!\,1!) = 60$).

**تمرين 2.3 ★.**

تُختار لجنة من $4$ أشخاص من بين $7$ نساء و $5$ رجال. كم لجنة: إجمالًا؟ وفيها $2$ من النساء بالضبط؟ وفيها رجل واحد على الأقل؟

**حل التمرين 2.3.**

الإجمالي: $\binom{12}{4} = 495$. وأمّا $2$ من النساء بالضبط: فنختارهما ($\binom 72 = 21$) ونختار $2$ من الرجال ($\binom 52 = 10$): أي $210$ لجنة. وأمّا رجل واحد على الأقل: فهي متمّمة «لا رجل فيها»، $\binom{12}{4} - \binom{7}{4} = 495 - 35 = 460$.

**تمرين 2.4 ★.**

برهن على أنه في أيّ [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) من $13$ شخصًا يشترك اثنان في شهر الميلاد؛ وعلى أنه من بين أيّ $n + 1$ عددًا صحيحًا مختارًا من $\intint{1}{2n}$ يوجد عددان متتاليان. *(مبدأ الأدراج في المرتين: سمِّ الأدراج.)*

**حل التمرين 2.4.**

*شهور الميلاد:* الأدراج هي الشهور $12$؛ و $13$ شخصًا في $12$ درجًا يفرضون وجود شخصين في الدرج نفسه ([النتيجة 2.3](#cor-b1-counting-pigeonhole)).

*الأعداد المتتالية:* الأدراج هي الأزواج $n$ $\{1,2\},
\{3,4\}, \dots, \{2n-1, 2n\}$، وهي تجزّئ $\intint{1}{2n}$. واختيار $n + 1$ عددًا صحيحًا يضع عددين في الزوج نفسه، وعنصرا الزوج الواحد متتاليان.

**تمرين 2.5 ★.**

احسب $\sum_{k=0}^{n} k \binom{n}{k}$. *إرشاد: اشتقّ $(1 + x)^n$، أو استعمل $k \binom nk = n \binom{n-1}{k-1}$ (وبرهن عليها).*

**حل التمرين 2.5.**

من أجل $1 \leq k \leq n$،

$$
k \binom nk = k\,\frac{n!}{k!\,(n-k)!}
= n\,\frac{(n-1)!}{(k-1)!\,(n-k)!} = n \binom{n-1}{k-1}.
$$

وبالجمع وإعادة الفهرسة بوضع $j = k - 1$:

$$
\sum_{k=0}^{n} k \binom nk = n \sum_{j=0}^{n-1} \binom{n-1}{j}
= n\, 2^{n-1}
$$

حسب [القضية 2.15](#prop-b1-counting-identities). (وبطريقة أخرى: اشتقّ $(1+x)^n = \sum_k \binom nk x^k$ وضع $x = 1$.)

**تمرين 2.6 ★★.**

كم تطبيقًا متزايدًا تمامًا يوجد من $\intint{1}{k}$ إلى $\intint{1}{n}$؟ استنتج عدد التطبيقات المتزايدة (لا بالضرورة تمامًا). *إرشاد للعدّ الثاني: [التطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) $f$ متزايد $\mapsto$ $g(i) = f(i) + i - 1$.*

**حل التمرين 2.6.**

[التطبيق](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-map) المتزايد تمامًا $f \colon \intint{1}{k} \to \intint{1}{n}$ محدَّد بصورته، وهي جزء من $\intint{1}{n}$ فيه $k$ عنصرًا (اسرد الجزء بترتيب تزايدي)؛ وبالعكس فإن كل جزء من $k$ عنصرًا يعطي تطبيقًا واحدًا بالضبط من هذا النوع. ومنه $\binom nk$ تطبيقًا متزايدًا تمامًا.

وإذا كان $f$ متزايدًا لا غير، فضع $g(i) = f(i) + i - 1$. عندئذ يكون $g$ متزايدًا تمامًا (فبين متغيرين متتاليين يربح $f$ مقدارًا $\geq 0$ ويربح $i - 1$ مقدار $1$) وقيمه في $\intint{1}{n + k - 1}$؛ و $f(i) = g(i) - i + 1$ يستعيد $f$ من أيّ $g$ متزايد تمامًا في $\intint{1}{n+k-1}$. وهذا تقابل، فيوجد إذن $\binom{n + k - 1}{k}$ تطبيقًا متزايدًا.

**تمرين 2.7 ★★.**

(فاندرموند) برهن، بعدّ الأجزاء ذات $k$ عنصرًا في [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) مقسومة إلى كتلتين حجمهما $m$ و $n$، على أن:

$$
\binom{m+n}{k} = \sum_{j=0}^{k} \binom{m}{j} \binom{n}{k-j} .
$$

واستنتج $\sum_{j=0}^{n} \binom nj^2 = \binom{2n}{n}$.

**حل التمرين 2.7.**

اقسم [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) $E$ فيها $m + n$ عنصرًا إلى كتلتين $M$ (وفيها $m$ عنصرًا) و $N$ (وفيها $n$ عنصرًا). كل جزء من $E$ فيه $k$ عنصرًا يحوي $j$ عنصرًا من $M$ (حيث $0 \leq j \leq k$) و $k - j$ عنصرًا من $N$؛ ومن أجل $j$ مثبَّت يوجد $\binom mj \binom{n}{k-j}$ جزءًا كهذا، وتجزّئ الحالات $j = 0, \dots,
k$ الأجزاء ذات $k$ عنصرًا. وتعطي قاعدة الجمع متطابقة فاندرموند.

ومع $m = n = k$: $\binom{2n}{n} = \sum_{j=0}^{n} \binom nj
\binom{n}{n-j} = \sum_{j=0}^{n} \binom nj^2$، باستعمال $\binom{n}{n-j} =
\binom nj$.

**تمرين 2.8 ★★.**

كم عددًا صحيحًا في $\intint{1}{1000}$ يقبل القسمة على $2$ أو $3$ أو $5$؟ (بالاحتواء والاستبعاد؛ والمقدار $\lfloor 1000/6 \rfloor$ يعدّ مضاعفات $6$، وهكذا.)

**حل التمرين 2.8.**

لتكن $A_d$ [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) مضاعفات $d$ في $\intint{1}{1000}$، ومنه $\abs{A_d} = \lfloor 1000/d \rfloor$. وبالاحتواء والاستبعاد ([المبرهنة 2.24](#thm-b1-counting-inclexcl)) مع $A_2, A_3, A_5$، مع ملاحظة أن $A_2 \cap A_3 = A_6$ وهكذا:

$$
500 + 333 + 200 - 166 - 100 - 66 + 33 = 734 .
$$

إذن يوجد $734$ عددًا صحيحًا يقبل القسمة على $2$ أو $3$ أو $5$.

**تمرين 2.9 ★★.**

عُدَّ التطبيقات الشاملة من [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) ذات $4$ عناصر على [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) ذات $2$ عنصرين؛ ثم على [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) ذات $3$ عناصر. *إرشاد: عُدَّ التطبيقات غير الشاملة بالاحتواء والاستبعاد على القيم الفائتة.*

**حل التمرين 2.9.**

على [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) ذات $2$ عنصرين: جميع التطبيقات $2^4 = 16$ عدا التطبيقين الثابتين $2$: أي $14$ تطبيقًا [شاملًا](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj).

وعلى [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) ذات $3$ عناصر: بالاحتواء والاستبعاد على القيم الفائتة، يكون عدد التطبيقات من [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) ذات $4$ عناصر إلى [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) ذات $3$ عناصر التي تفوتها قيمة واحدة على الأقل هو $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$؛ وعدد التطبيقات كلها $3^4 =
81$؛ فعدد الشاملة: $81 - 45 = 36$. (وللتحقق: [التطبيق الشامل](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-inj) من $4$ عناصر على $3$ عناصر يكرّر قيمة واحدة بالضبط: فاختر القيمة المكررة ($3$)، والزوج الذي يُرسل إليها ($\binom 42 = 6$)، وتقابلًا من أجل الباقي ($2$): $3 \times 6 \times 2 = 36$.)

**تمرين 2.10 ★★.**

(النجوم والعصيّ) برهن على أن عدد الاختيارات من الرتبة $k$ من $n$ غرضًا *بتكرار* مع إهمال الترتيب — أي، على نحو مكافئ، عدد المتتاليات $(x_1, \dots, x_n) \in \N^n$ التي تحقق $x_1 + \dots + x_n = k$ — هو $\binom{n + k - 1}{k}$. *إرشاد: رمّز حلًّا بصفّ من $k$ نجمة و $n - 1$ عصًا.*

**حل التمرين 2.10.**

حلّ المعادلة $x_1 + \dots + x_n = k$ في $\N^n$ يُرمَّز بصفّ من $k$ نجمة و $n - 1$ عصًا: اكتب $x_1$ نجمة، ثم عصًا، ثم $x_2$ نجمة، ثم عصًا، …، وانتهِ بعدد $x_n$ من النجوم. وهذا تقابل على كلمات الطول $k + n - 1$ المستعملة $k$ نجمة و $n - 1$ عصًا، وهذه الكلمات محدَّدة بمواضع النجوم: $\binom{n + k - 1}{k}$. والاختيارات بتكرار تقابل حلول المعادلة (حيث $x_i$ عدد نسخ الغرض $i$)، فيكون العدد نفسه.

**تمرين 2.11 ★★★.**

برهن على صيغة [المثال 2.26](#ex-b1-counting-derangement) الخاصة بالعدد $D_n$ بالتفصيل، واستنتج $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ (وبرهن كذلك على هذه المتطابقة مباشرةً بتصنيف التبديلات بحسب [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) نقاطها الصامدة).

**حل التمرين 2.11.**

مع $A_i = \{\sigma : \sigma(i) = i\}$، تصمد [التبديلة](#def-b1-counting-objects) من $\bigcap_{i \in I} A_i$ عند كل $i \in I$ وتبدّل النقاط $n - \abs I$ الأخرى بحرية: $\abs{\bigcap_{i \in I} A_i} =
(n - \abs I)!$. وبالاحتواء والاستبعاد:

$$
\Bigl|\bigcup_i A_i\Bigr|
= \sum_{k=1}^{n} (-1)^{k+1} \binom nk (n-k)!
= \sum_{k=1}^{n} (-1)^{k+1} \frac{n!}{k!} ,
$$

لأن عدد أجزاء $I$ ذات الحجم $k$ هو $\binom nk$. ومنه

$$
D_n = n! - \Bigl|\bigcup_i A_i\Bigr|
= n!\Bigl(1 - \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}\Bigr)
= n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} .
$$

وأمّا المتطابقة الثانية: فصنّف التبديلات $\sigma$ في $\intint{1}{n}$ بحسب [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) نقاطها الصامدة $F(\sigma)$. ومن أجل جزء $F$ مثبَّت فيه $k$ عنصرًا، تكون التبديلات التي تحقق $F(\sigma) = F$ هي بالضبط اضطرابات المتمّمة: أي $D_{n-k}$ [تبديلة](#def-b1-counting-objects). وبالجمع على اختيارات $F$ التي عددها $\binom nk$ من أجل كل $k$: $n! = \sum_{k=0}^{n} \binom nk D_{n-k}$.

**تمرين 2.12 ★★★.**

من أجل $n \in \N^*$، برهن بعدّ مزدوج للأزواج (جزء، عنصر مميَّز) على أن:

$$
\sum_{k=1}^{n} k \binom{n}{k} = n\, 2^{n-1},
\qquad\text{ثم}\qquad
\sum_{k=1}^{n} k^2 \binom{n}{k} = n(n+1)\, 2^{n-2} .
$$

*وأمّا الثانية: فعُدَّ أزواج العناصر المميَّزة، متساويةً كانت أو مختلفة.*

**حل التمرين 2.12.**

*المتطابقة الأولى.* عُدَّ الأزواج $(A, a)$ حيث $A \subseteq E$ (و $\abs E = n$) و $a \in A$. فبحسب حجم $A$: يوجد $\sum_k \binom nk k$ زوجًا. وباختيار العنصر المميَّز أولًا: يوجد $n$ اختيارًا للعنصر $a$، ثم أيّ جزء من العناصر $n - 1$ الباقية لإتمام $A$: أي $n\,2^{n-1}$ زوجًا.

*المتطابقة الثانية.* عُدَّ الثلاثيات $(A, a, b)$ حيث $a, b \in
A$ (ويجوز $a = b$). فبحسب الحجم: $\sum_k k^2 \binom nk$. ومباشرةً: إمّا $a = b$ (أي $n\,2^{n-1}$ ثلاثية، وهو العدّ السابق) وإمّا $a \neq b$ (أي $n(n-1)$ اختيارًا مرتَّبًا، ثم أيّ جزء من العناصر $n - 2$ الأخرى: $n(n-1)\,2^{n-2}$). والمجموع

$$
n\,2^{n-1} + n(n-1)\,2^{n-2} = n\,2^{n-2}\,(2 + n - 1)
= n(n+1)\,2^{n-2} .
$$

## 2.6 مسألة: الاضطرابات، أو الرسائل الخاطئة العناوين

**مسألة 2.1.**

يضع سكرتير $n$ رسالة في $n$ ظرفًا معنونًا عشوائيًا: فما احتمال ألا يتلقى *أحد* رسالته الصحيحة؟ يقود هذا السؤال الكلاسيكي (مونمور، 1708) إلى أعداد الاضطراب $D_n$ في [المثال 2.26](#ex-b1-counting-derangement). وصيغة الاحتواء والاستبعاد ليست إلا الحركة الافتتاحية: فهذه المسألة تطوّر التراجعات التي تحسب $D_n$، وبرهانين مستقلين آخرين على الصيغة، والمبرهنة اللافتة القائلة إن $D_n$ أقرب عدد صحيح إلى $n!/\eu$، والتوزيع الكامل للنقاط الصامدة في [تبديلة](#def-b1-counting-objects) عشوائية، والحساب الطريف للمتتالية $(D_n)$. وفي كل ما يلي، يرمز $D_n$ إلى عدد الاضطرابات (أي التبديلات الخالية من النقاط الصامدة) في $\intint1n$، مع الاصطلاح $D_0 = 1$ (إذ إن [التبديلة](#def-b1-counting-objects) الخالية بلا نقطة صامدة).

**الجزء 1 — الحالات الصغيرة وإحصاء النقاط الصامدة.**

1. احسب $D_1, D_2, D_3$ مباشرةً، و $D_4$ بسرد اضطرابات $\{1, 2, 3, 4\}$ مجمّعةً بحسب قيمة $\sigma(1)$ . (ينبغي أن تجد $D_4 = 9$ .)
2. من أجل $0 \leq k \leq n$ ، بيّن أن عدد التبديلات $P_k(n)$ في $\intint1n$ ذات $k$ نقطة صامدة *بالضبط* هو $\binom nk D_{n-k}$ .
3. تحقق من الإحصاء من أجل $n = 4$ : احسب $P_0(4), \dots,  P_4(4)$ وتأكّد أن مجموعها $4! = 24$ . وأيّهما أرجح من أجل أربع رسائل: ألا يوافق شيء، أم أن توافق رسالة واحدة بالضبط؟
4. بعدّ مزدوج ([الطريقة 2.22](#met-b1-counting-doublecount)) للأزواج $(\sigma, i)$ التي تحقق $\sigma(i) = i$، بيّن أن $$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$$ أي إن [للتبديلة](#def-b1-counting-objects) العشوائية، في المتوسط، نقطة صامدة *واحدة بالضبط*، مهما يكن $n \geq 1$.

**الجزء 2 — تراجعان وبرهانان جديدان على الصيغة.**

5. برهن توفيقيًا، من أجل $n \geq 1$، على أن: $$D_{n+1} = n\,(D_n + D_{n-1}) .$$ (صنّف اضطرابات $\sigma$ في $\intint1{n+1}$ بحسب $j = \sigma(n+1)$، ثم بحسب كون $\sigma(j) = n + 1$ أو لا؛ وفي حالة $\sigma(j) \neq n+1$، ابنِ تقابلًا مع اضطرابات $\intint1n$ بإعادة توجيه سابقة $n + 1$ إلى $j$.) وتحقق من التراجع عدديًا حتى $D_6$.
6. بوضع $u_n = D_n - n D_{n-1}$، استنتج من السؤال 5 أن $u_{n+1} = -u_n$، واستنتج التراجع الثاني: $$D_n = n D_{n-1} + (-1)^n \qquad (n \geq 1).$$
7. انطلاقًا من السؤال 6، برهن بالاستقراء على صيغة [المثال 2.26](#ex-b1-counting-derangement)، $$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},$$ — وهو برهان مستقل كل الاستقلال عن الاحتواء والاستبعاد.
8. (القلب الثنائي) لتكن $(a_n)$ و $(b_n)$ متتاليتين تحققان $a_n = \sum_{k=0}^n \binom nk b_k$ لكل $n$. برهن على أن $$b_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k  \qquad (n \in \N).$$ (أرسِ أولًا *المراجعة الثلاثية* $\binom nk \binom kj = \binom nj \binom{n-j}{k-j}$، ثم استعمل المجموع المتناوب لسطر [المثال 2.17](#ex-b1-counting-binomial).)
9. طبّق السؤال 8 على المتطابقة $n! = \sum_k \binom nk  D_{n-k}$ من [التمرين 2.11](#exo-b1-counting-11) للحصول على برهان *ثالث* على صيغة $D_n$ .

**الجزء 3 — أقرب عدد صحيح إلى $n!/\eu$.** اقبل في هذا الجزء — فالنظرية مبنيّة في [الفصل 17](https://one-course.com/books/math/3/ar/chapter/17-numerical-series#ch-b1-series) — أن $\eu^{-1} = \lim_{n \to \infty} s_n$ حيث $s_n = \sum_{k=0}^{n}
\frac{(-1)^k}{k!}$، مع الحاصر التام للمتسلسلة المتناوبة $\abs{\eu^{-1} - s_n} < \frac1{(n+1)!}$ من أجل كل $n$.

10. بيّن أن $\bigl| D_n - n!/\eu \bigr| < \frac1{n+1}$ من أجل كل $n \in \N$ .
11. استنتج المبرهنة الرئيسة: *من أجل كل $n \geq 1$، يكون $D_n$ أقرب عدد صحيح إلى $n!/\eu$* . ولماذا تحتاج الحجة إلى $n \geq 1$ ؟
12. عيّن إشارة الخطأ: بيّن أن $D_n > n!/\eu$ تحديدًا عندما يكون $n$ زوجيًا. (حدّد موضع أول حدّ مهمَل في المتسلسلة المتناوبة.)
13. احسب $D_7$ حتى $D_{10}$ بتراجع السؤال 5، ثم قارن $D_{10}$ بالمقدار $10!/\eu$ ( $10! = 3\,628\,800$ ، $\eu \approx 2.718281828$ ).
14. (احتمال حفظ القبعات) لتكن $p_n = D_n/n!$ احتمال أن تكون [تبديلة](#def-b1-counting-objects) عشوائية منتظمة اضطرابًا. بيّن أن $\abs{p_n - \eu^{-1}} < \frac1{(n+1)!}$ واحسب $p_6$ بخمسة أرقام عشرية. وعلّق: لماذا يكون جواب سؤال مونمور مستقلًا جوهريًا عن $n$ — منذ اثنتي عشرة رسالة أصلًا؟

**الجزء 4 — توزيع النقاط الصامدة.**

15. ثبّت $k \in \N$. بيّن أن نسبة التبديلات في $\intint1n$ ذات $k$ نقطة صامدة بالضبط تحقق $$\frac{P_k(n)}{n!} = \frac{s_{n-k}}{k!}  \;\xrightarrow[n \to \infty]{}\; \frac{\eu^{-1}}{k!} .$$ (وهذه القيم الحدّية، ومجموعها $1$، تكوّن *توزيع بواسون* ذا الوسيط $1$، وهو غرض محوري في درس الاحتمال من مجلد السنة 2.)
16. بعدّ مزدوج للثلاثيات $(\sigma, i, j)$ حيث $i  \neq j$ تصمد كلتاهما عند $\sigma$ ، بيّن أن $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}\,  (\abs{\mathrm{Fix}(\sigma)} - 1) = n!$ من أجل $n \geq 2$ . وبالجمع مع السؤال 4: يكون متوسط $\abs{\mathrm{Fix}}^2$ مساويًا $2$ ، فيكون «تشتت» (تباين) عدد النقاط الصامدة مساويًا $1$ — وهو مستقل عن $n$ من جديد، ومطابق لقانون بواسون من جديد.
17. احسب نسبة التبديلات ذات نقطة صامدة واحدة على الأقل من أجل $n = 4, 5, 6$ (في صورة كسور وبأربعة أرقام عشرية)، وقارنها بالمقدار $1 - \eu^{-1} \approx  0.6321$ .
18. بيّن مباشرة — دون حاجة إلى أيّ نهايات — أن $s_{n+2} - s_n  = (-1)^{n+1}\bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\bigr)$ ، واستنتج أن الاحتمالات $p_n = s_n$ من السؤال 14 تتذبذب: $p_0 > p_2 > p_4 > \dots$ و $p_1 < p_3 < p_5 < \dots$ ، فتتناقص القيم الزوجية وتتزايد القيم الفردية نحو النهاية المشتركة $\eu^{-1}$ .
19. (تبادل الهدايا السرّي) يسحب $n$ شخصًا اسمًا واحدًا من قبعة؛ فإذا سحب أحدهم اسمه أُعيد السحب *كله* من جديد. باستعمال الواقعة المعيارية القائلة إن حدثًا احتماله $p$ يقتضي في المتوسط $1/p$ محاولة، قدّر متوسط عدد السحوب الكاملة اللازمة، واستنتج أن هذا الإجراء يكلّف نحو $\eu \approx  2.72$ سحبة في المتوسط، وذلك باستقلال جوهري عن $n$ .

**الجزء 5 — حساب $D_n$، وتوليفة ختامية.**

20. صقّل السؤال 5: بيّن أنه من أجل $j \in  \intint2n$ مثبَّت، يكون عدد اضطرابات $\intint1n$ التي تحقق $\sigma(1) = j$ مساويًا $D_{n-1} + D_{n-2}$ بالضبط، باستقلال عن $j$ . واستنتج أن $n - 1$ يقسم $D_n$ من أجل كل $n \geq 2$ .
21. برهن على أن $D_n$ فرديّ إذا وفقط إذا كان $n$ زوجيًا. (اعمل بترديد $2$ في تراجع السؤال 6.)
22. برهن على أن $D_n \equiv (-1)^n \pmod n$ من أجل $n \geq 1$ ، وتحقق من التوافق على الرقم الأخير من $D_{10}$ .
23. بيّن انطلاقًا من السؤال 6 أن $\dfrac{D_n}{D_{n-1}} = n +  \dfrac{(-1)^n}{D_{n-1}}$ من أجل $n \geq 3$ ، فتكون نسبة عددي اضطراب متتاليين مساويةً *تقريبًا بالضبط* $n$ ؛ واشرح في جملة واحدة لماذا يتوافق ذلك مع $D_n \approx n!/\eu$ .
24. أين استعملت هذه المسألة بالضبط: (أ) قاعدتَي الجداء والجمع؛ (ب) العدّ المزدوج؛ (ج) مبرهنة ثنائي الحدّ؛ (د) الحاصر المقبول للمتسلسلة المتناوبة؟ جملة واحدة لكلٍّ منها.
25. توليفة. صار لصيغة $D_n$ الآن ثلاثة براهين (الاحتواء والاستبعاد، والتراجع مع الاستقراء، والقلب الثنائي). قارن في فقرة قصيرة ما *يشرحه* كل برهان: أيّها أسرع حسابًا، وأيّها يتعمّم على أعداد نقاط صامدة أخرى، وأيّها يكشف لماذا يظهر $\eu$ في مسألة عن الأظرفة.

**حل المسألة 2.1.**

**1.** $D_1 = 0$ ([فالتبديلة](#def-b1-counting-objects) الوحيدة تصمد عند $1$)، و $D_2 = 1$ (وهي التبديل)، و $D_3 = 2$ (بالترميز السطري: $231$ و $312$). ومن أجل $n = 4$، بالتجميع بحسب $\sigma(1)$: مع $\sigma(1) = 2$ تكون الاضطرابات $2143$ و $2341$ و $2413$؛ ومع $\sigma(1) = 3$: $3142$ و $3412$ و $3421$؛ ومع $\sigma(1) = 4$: $4123$ و $4312$ و $4321$. ثلاثة في كل [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets): أي $D_4 = 9$.

**2.** [التبديلة](#def-b1-counting-objects) ذات $k$ نقطة صامدة بالضبط محدَّدة باختيار [مجموعة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-sets) نقاطها الصامدة $F$ ($\binom nk$ طريقة) مع قصرها على المتمّمة، الذي يجب أن يكون [تبديلة](#def-b1-counting-objects) على $n - k$ نقطة *بلا* نقطة صامدة ($D_{n-k}$ طريقة). والاختياران مستقلان والتقارن تقابليّ: $P_k(n) = \binom nk D_{n-k}$.

**3.** لدينا $P_0(4) = D_4 = 9$؛ و$P_1(4) = \binom41 D_3 = 4 \times 2
= 8$؛ و$P_2(4) = \binom42 D_2 = 6$؛ و$P_3(4) = \binom43 D_1 = 0$ (إذ تفرض ثلاث نقاط صامدة نقطةً رابعة)؛ و $P_4(4) = 1$. والمجموع: $9 + 8 + 6
+ 0 + 1 = 24 = 4!$. فألا يوافق شيء ($9$ حالة) يفوق أن توافق رسالة واحدة بالضبط ($8$ حالات) — بفارق ضئيل.

**4.** عُدَّ الأزواج $(\sigma, i)$ التي تحقق $\sigma(i) = i$. ومن أجل $i$ مثبَّت، تكون التبديلات الصامدة عند $i$ هي تبديلات النقاط $n - 1$ الأخرى: أي $(n-1)!$ [تبديلة](#def-b1-counting-objects). ومنه فإن عدد الأزواج هو $n \cdot (n-1)! = n!$، وهذا العدد يساوي كذلك $\sum_\sigma \abs{\mathrm{Fix}(\sigma)}$. وبالقسمة على عدد التبديلات $n!$: يكون متوسط عدد النقاط الصامدة مساويًا $1$ بالضبط، من أجل كل $n \geq 1$.

**5.** ليكن $\sigma$ اضطرابًا في $\intint1{n+1}$ وليكن $j = \sigma(n+1) \in \intint1n$: أي $n$ قيمة ممكنة. *الحالة $\sigma(j) = n+1$:* تتبادل النقطتان $j$ و $n+1$، ويكون قصر $\sigma$ على النقاط $n - 1$ الباقية اضطرابًا كيفيًا فيها: أي $D_{n-1}$ إمكانًا. *الحالة $\sigma(j)
\neq n+1$:* لتكن $i_0 = \sigma^{-1}(n+1)$؛ عندئذ $i_0 \neq j$ و $i_0 \leq n$. نعرّف $\tau$ على $\intint1n$ بالعلاقتين $\tau(i) = \sigma(i)$ من أجل $i \neq i_0$ و $\tau(i_0) = j$. عندئذ يكون $\tau$ [تبديلة](#def-b1-counting-objects) في $\intint1n$ (إذ حلّت القيمة الفائتة $j$ محلّ القيمة $n+1$)، وهي اضطراب: إذ $\tau(i_0) = j \neq i_0$، و $\tau(i) = \sigma(i) \neq i$ في المواضع الأخرى. وبالعكس، من اضطراب $\tau$ في $\intint1n$ ومن القيمة $j$ نستعيد $\sigma$ بوضع $\sigma(n+1) = j$ و$\sigma(\tau^{-1}(j)) = n+1$ و $\sigma = \tau$ في المواضع الأخرى: وهو تقابل يعطي $D_n$ إمكانًا. وبالجمع على $j$: $D_{n+1} = n(D_n + D_{n-1})$. وعدديًا: $D_5 = 4(9 + 2) = 44$ و$D_6 = 5(44 + 9) = 265$.

**6.** من السؤال 5 لدينا $D_{n+1} = nD_n + nD_{n-1}$، ومنه

$$
u_{n+1} = D_{n+1} - (n+1)D_n = nD_n + nD_{n-1} - (n+1)D_n
= -(D_n - nD_{n-1}) = -u_n .
$$

وبما أن $u_1 = D_1 - 1 \cdot D_0 = -1$ فإن الاستقراء يعطي $u_n =
(-1)^n$، أي $D_n = nD_{n-1} + (-1)^n$ من أجل $n \geq 1$.

**7.** بالاستقراء على $n$. البداية: $D_0 = 1 = 0!\,s_0$. خطوة الانتقال: بافتراض $D_{n-1} = (n-1)!\,s_{n-1}$،

$$
D_n = nD_{n-1} + (-1)^n = n!\,s_{n-1} + (-1)^n
= n!\Bigl(s_{n-1} + \frac{(-1)^n}{n!}\Bigr) = n!\,s_n ,
$$

وهي الصيغة المطلوبة. ولم يُستعمل أيّ احتواء واستبعاد: بل التراجع التوفيقي من السؤال 5 وحده.

**8.** المراجعة الثلاثية، بالعوامل:

$$
\binom nk \binom kj
= \frac{n!}{k!\,(n-k)!} \cdot \frac{k!}{j!\,(k-j)!}
= \frac{n!}{j!\,(n-j)!} \cdot \frac{(n-j)!}{(k-j)!\,(n-k)!}
= \binom nj \binom{n-j}{k-j} .
$$

والآن عوّض $a_k = \sum_j \binom kj b_j$ وبادل بين المجموعين المنتهيين:

$$
\sum_{k=0}^{n} (-1)^{n-k} \binom nk a_k
= \sum_{j=0}^{n} b_j \binom nj
\sum_{k=j}^{n} (-1)^{n-k} \binom{n-j}{k-j}
= \sum_{j=0}^{n} b_j \binom nj
\sum_{i=0}^{n-j} (-1)^{(n-j)-i} \binom{n-j}{i} .
$$

والمجموع الداخلي هو نشر $(1 + (-1))^{n-j} = 0^{n-j}$ (بمبرهنة ثنائي الحدّ، [المبرهنة 2.16](#thm-b1-counting-binomial)): فهو ينعدم من أجل $j < n$ ويساوي $1$ من أجل $j = n$. فلا يبقى إلا $j = n$، ويكون الطرف الأيمن هو $b_n$، وهو المطلوب.

**9.** بالتناظر $\binom nk = \binom n{n-k}$، تُكتب متطابقة [التمرين 2.11](#exo-b1-counting-11) على الصورة $n! =
\sum_{k=0}^n \binom nk D_k$. وبتطبيق السؤال 8 مع $a_n = n!$ و $b_k = D_k$:

$$
D_n = \sum_{k=0}^{n} (-1)^{n-k} \binom nk k!
= \sum_{k=0}^{n} (-1)^{n-k} \frac{n!}{(n-k)!}
= n! \sum_{j=0}^{n} \frac{(-1)^j}{j!} ,
$$

وبإعادة الفهرسة بوضع $j = n - k$: نحصل على الصيغة مرة ثالثة.

**10.** لدينا $D_n = n!\,s_n$ (السؤال 7)، ومنه

$$
\Bigl| D_n - \frac{n!}{\eu} \Bigr|
= n!\,\abs{s_n - \eu^{-1}} < \frac{n!}{(n+1)!} = \frac1{n+1} .
$$

**11.** من أجل $n \geq 1$ لدينا $\frac1{n+1} \leq \frac12$، وتكون متراجحة السؤال 10 تامة: أي أن $D_n$ يقع على مسافة $< \frac12$ من $n!/\eu$، فهو إذن أقرب عدد صحيح إليه على نحو وحيد. ومن أجل $n = 0$ لا يعطي الحاصر إلا مسافة $< 1$، وتخفق الدعوى هناك بالفعل: إذ إن $0!/\eu \approx 0.368$ أقرب عدد صحيح إليه $0$، بينما $D_0 = 1$.

**12.** المقدار $\eu^{-1} - s_n = \sum_{k \geq n+1} (-1)^k/k!$ متسلسلة متناوبة حدودها متناقصة تمامًا، فإشارته إشارة حدّه الأول $(-1)^{n+1}/(n+1)!$. ومنه فإن إشارة $s_n -
\eu^{-1}$ هي إشارة $(-1)^n$: فمن أجل $n$ زوجيّ يكون $s_n > \eu^{-1}$ و$D_n = n!\,s_n > n!/\eu$؛ ومن أجل $n$ فرديّ يكون $D_n < n!/\eu$.

**13.** $D_7 = 6(265 + 44) = 6 \times 309 = 1854$؛ و$D_8 =
7(1854 + 265) = 7 \times 2119 = 14\,833$؛ و$D_9 = 8(14\,833 + 1854)
= 8 \times 16\,687 = 133\,496$؛ و$D_{10} = 9(133\,496 + 14\,833) =
9 \times 148\,329 = 1\,334\,961$. وللتحقق: $10!/\eu = 3\,628\,800 /
2.718281828 \approx 1\,334\,960.92$، وأقرب عدد صحيح إليه هو $1\,334\,961$ — ولدينا $D_{10} > 10!/\eu$، كما يتنبأ به السؤال 12 من أجل $n$ زوجيّ.

**14.** $\abs{p_n - \eu^{-1}} = \abs{s_n - \eu^{-1}} <
\frac1{(n+1)!}$. ومن أجل $n = 6$: $p_6 = 265/720 = 0.36806$ (بخمسة أرقام عشرية)، في مقابل $\eu^{-1} = 0.36788$؛ والفارق دون $1/7! =
1/5040 < 2 \times 10^{-4}$. ويتقلص الحاصر $1/(n+1)!$ بسرعة تجعل الاحتمال مثبَّتًا إلى أرقام عشرية كثيرة منذ اثنتي عشرة رسالة: فالجواب «نحو $36.8\%$» مستقل عن $n$ في كل غرض عملي — وهي مفاجأة المسألة الشهيرة.

**15.** حسب السؤال 2 ومع $D_m = m!\,s_m$:

$$
\frac{P_k(n)}{n!} = \frac{\binom nk D_{n-k}}{n!}
= \frac{D_{n-k}}{k!\,(n-k)!} = \frac{s_{n-k}}{k!}
\;\longrightarrow\; \frac{\eu^{-1}}{k!}
$$

عندما $n \to \infty$ مع $k$ مثبَّت، لأن $s_{n-k} \to \eu^{-1}$. والقيم الحدّية $\eu^{-1}/k!$ (حيث $k \in \N$) هي أوزان توزيع بواسون ذي الوسيط $1$.

**16.** عُدَّ الثلاثيات $(\sigma, i, j)$ حيث $i \neq j$ و $\sigma(i) = i$ و $\sigma(j) = j$. فباختيار الزوج المرتَّب أولًا: $n(n-1)$ طريقة؛ والتبديلات الصامدة عند $i$ و $j$ معًا هي تبديلات النقاط $n - 2$ الباقية: أي $(n-2)!$ [تبديلة](#def-b1-counting-objects). والمجموع: $n(n-1)(n-2)! = n!$. وأمّا الجمع على التبديلات $\sigma$ أولًا فيعدّ، من أجل كل $\sigma$، الأزواج المرتَّبة من النقاط الصامدة المتمايزة: $\abs{\mathrm{Fix}(\sigma)}(\abs{\mathrm{Fix}(\sigma)}-1)$. ومنه المتطابقة المذكورة؛ وبالقسمة على $n!$ يكون متوسط $\abs{\mathrm{Fix}}(\abs{\mathrm{Fix}} - 1)$ مساويًا $1$، فيكون متوسط $\abs{\mathrm{Fix}}^2$ مساويًا $1 + 1 = 2$ ويكون التباين $2 -
1^2 = 1$.

**17.** النسب $1 - p_n$: من أجل $n = 4$، $1 - \frac
9{24} = \frac{15}{24} = 0.6250$؛ ومن أجل $n = 5$، $1 - \frac{44}{120} =
\frac{76}{120} = 0.6333$؛ ومن أجل $n = 6$، $1 - \frac{265}{720} =
\frac{455}{720} = 0.6319$. وكلها في حدود واحد في المئة من $1 - \eu^{-1}
\approx 0.6321$، متذبذبةً حوله.

**18.** مباشرةً:

$$
s_{n+2} - s_n = \frac{(-1)^{n+1}}{(n+1)!} +
\frac{(-1)^{n+2}}{(n+2)!}
= (-1)^{n+1}\Bigl(\frac1{(n+1)!} - \frac1{(n+2)!}\Bigr),
$$

والقوس $> 0$. فمن أجل $n$ زوجيّ يكون الفرق سالبًا: أي $s_{n+2} < s_n$، ومنه $p_0 > p_2 > p_4 > \dots$؛ ومن أجل $n$ فرديّ يكون موجبًا: $p_1 < p_3 < p_5 < \dots$ وبالجمع مع السؤال 12 (فالزوجية فوق $\eu^{-1}$ والفردية تحته) والسؤال 14 (فالمسافة إلى $\eu^{-1}$ تؤول إلى $0$): يحصر السلّمان $\eu^{-1}$ بينهما.

**19.** السحبة الكاملة الواحدة [تبديلة](#def-b1-counting-objects) عشوائية منتظمة، وتصحّ عندما تكون اضطرابًا: أي باحتمال $p_n \approx \eu^{-1}$. وحسب الواقعة المذكورة، يكون متوسط عدد السحوب حتى النجاح $1/p_n$، ويعطي السؤال 14 أن $1/p_n \approx \eu$ بخطأ مهمَل منذ القيم الصغيرة للعدد $n$. إذن يكلّف تبادل الهدايا السرّي مع إعادات السحب نحو $\eu \approx 2.72$ سحبة كاملة في المتوسط — سواء أكان في المكتب $6$ أشخاص أم $600$.

**20.** ثبّت $j \geq 2$ وأجرِ تصنيف السؤال 5 على القيمة $\sigma(1) = j$. إذا كان $\sigma(j) = 1$: حملت النقاط $n - 2$ الباقية اضطرابًا كيفيًا، أي $D_{n-2}$ طريقة. وإذا كان $\sigma(j) \neq 1$: أعد توجيه السابقة $i_0 = \sigma^{-1}(1)$ إلى $j$ تمامًا كما في السؤال 5؛ وهذا تقابل مع اضطرابات النقاط $n - 1$ في $\{2, \dots, n\}$: أي $D_{n-1}$ طريقة. والمجموع $D_{n-1} + D_{n-2}$، وهو نفسه من أجل كل $j$. وبالجمع على قيم $j$ التي عددها $n - 1$: $D_n = (n-1)(D_{n-1} + D_{n-2})$، وهذا يُظهر العامل $n - 1$: أي $(n-1) \mid D_n$.

**21.** الدعوى: $D_n$ فرديّ إذا وفقط إذا كان $n$ زوجيًا. بالاستقراء باستعمال $D_n = nD_{n-1} + (-1)^n$، أي $D_n \equiv nD_{n-1} + 1 \pmod 2$. البداية: $D_1 = 0$ زوجيّ و $n = 1$ فرديّ: فتتحقق الدعوى. وإذا كان $n$ زوجيًا كان $nD_{n-1}$ زوجيًا و $D_n \equiv 1$: أي فرديّ، وهو المطلوب. وإذا كان $n$ فرديًا كان $n - 1$ زوجيًا، فيكون $D_{n-1}$ فرديًا بالفرض، ويكون $D_n \equiv D_{n-1} + 1 \equiv 0$: أي زوجيّ. وبهذا يُغلق الاستقراء.

**22.** إرجاع $D_n = nD_{n-1} + (-1)^n$ بترديد $n$ يُلغي الحدّ الأول: $D_n \equiv (-1)^n \pmod n$. ومن أجل $n = 10$: $(-1)^{10} = 1$، وينتهي $D_{10} = 1\,334\,961$ بالفعل بالرقم $1$.

**23.** من أجل $n \geq 3$ لدينا $D_{n-1} \geq 1$، وقسمة تراجع السؤال 6 على $D_{n-1}$ تعطي $D_n/D_{n-1} = n +
(-1)^n/D_{n-1}$، حيث $\abs{(-1)^n/D_{n-1}} \leq 1$ ويؤول بسرعة إلى $0$. والاتساق: إذا كان $D_n \approx n!/\eu$ فإن $D_n/D_{n-1} \approx n!/(n-1)! = n$ — إذ يختصر العامل $\eu$ في النسبة، ويؤكد التراجع ذلك بدقة $1/D_{n-1}$.

**24.** (أ) قاعدتا الجداء والجمع أساس كل عدّ: فالسؤالان 2 و 5 يجزّئان مجموعات التبديلات إلى مراحل مستقلة. (ب) وأعطى العدّ المزدوج المتوسط (السؤال 4) والتباين (السؤال 16) لعدد النقاط الصامدة دون أيّ صيغة للعدد $D_n$ البتة. (ج) وحسبت مبرهنة ثنائي الحدّ المجموع الداخلي المتناوب $(1-1)^{n-j}$ الذي يجعل القلب الثنائي يعمل (السؤال 8). (د) وحوّل حاصر المتسلسلة المتناوبة المجموعَ الدقيق لكن المعتم $n!\,s_n$ إلى [العبارة](https://one-course.com/books/math/3/ar/chapter/1-logic-sets-and-maps#def-b1-logic-statement) الشفافة «أقرب عدد صحيح إلى $n!/\eu$» (الأسئلة 10–14).

**25.** الاحتواء والاستبعاد ([المثال 2.26](#ex-b1-counting-derangement) و[التمرين 2.11](#exo-b1-counting-11)) هو البرهان المفهومي: فهو يشرح المجموع المتناوب بوصفه تصحيحات لعدٍّ زائد، ويتعمّم حرفيًا على عدّ العناصر التي تتفادى أيّ عائلة من المجموعات «السيئة». وأمّا طريق التراجع (الأسئلة 5–7) فهو الأسرع حسابًا — في زمن خطيّ، وبحساب صحيح مضبوط، وبلا عوامل — وهو مصدر الوقائع الحسابية في الجزء 5. وأمّا القلب الثنائي (السؤالان 8–9) فيضع الصيغة داخل تحويل عام سيعود كلما تقابل نسقان مثلثيان من المتطابقات. وأمّا ظهور $\eu$ فأحسن ما يشرحه الصيغة نفسها: إذ إن نسبة الاضطرابات هي المجموع الجزئي $s_n$ للمتسلسلة التي تعطي $\eu^{-1}$، فكانت أظرفة مونمور، قبل ترميز أويلر بثلاثة عقود، تحسب العدد $\eu$ فعلًا.