الرياضيات الجامعية — السنة 1 · Bachelor Year 1

2العدّ

يبدو عدّ المجموعات المنتهية أمرًا ابتدائيًا — ثم يصير دقيقًا سريعًا. يعرّف هذا الفصل عدد العناصر تعريفًا سليمًا (عبر التقابلات، على نهج الفصل 1)، ويرسي مبادئ العدّ القليلة التي يتفرع عنها كل شيء، ثم يستخرج الأعداد الكلاسيكية: القوائم والتبديلات والأجزاء والمعاملات الثنائية.

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

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

من أجل $n \in \N^*$ ، نكتب $\intint{1}{n} = \{1, 2, \dots, n\}$ . تكون المجموعة $E$ منتهية عندما تكون $E = \emptyset$ أو يوجد تقابل من $\intint{1}{n}$ على $E$ من أجل $n \in \N^*$ ما؛ وهذا العدد $n$ وحيد (المبرهنة 2.2) وهو عدد عناصر $E$ ، ويُكتب $\abs{E}$ (مع $\abs{\emptyset} = 0$ ).

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

إذا كان $m \neq n$ فلا يوجد تقابل من $\intint{1}{m}$ على $\intint{1}{n}$ . وبدقة أكبر، إذا كان $m > n$ فلا يوجد تطبيق متباين من $\intint{1}{m}$ في $\intint{1}{n}$ .

برهان. نبرهن بالاستقراء على $n$ على العبارة التالية: لكل $m > n$ لا يوجد تطبيق متباين $\intint{1}{m} \to \intint{1}{n}$ . من أجل $n = 0$ تكون مجموعة الوصول خالية و $m \geq 1$ : فلا وجود لأيّ تطبيق البتة. ولنفترض العبارة صحيحة من أجل $n$ ، ولنفترض أن $f \colon \intint{1}{m} \to \intint{1}{n+1}$ تطبيق متباين مع $m > n + 1$ . إذا لم تُبلغ القيمة $n + 1$ كان $f$ تطبيقًا متباينًا في $\intint{1}{n}$ ، وهذا يناقض فرض الاستقراء. وإلا فإن $f(a) = n + 1$ من أجل $a$ واحد بالضبط؛ فنبدّل بين $f(a)$ و $f(m)$ (وصوريًا: نركّب مع منقولة القيمتين)، فيصير التطبيق المتباين الجديد $g$ يحقق $g(m) = n + 1$ . عندئذ يكون قصر $g$ على $\intint{1}{m-1}$ تطبيقًا متباينًا في $\intint{1}{n}$ مع $m - 1 > n$ — وهذا تناقض من جديد. ∎

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

إذا كان $\abs{E} > \abs{F}$ فلا يكون أيّ تطبيق $f \colon E \to F$ متباينًا: أي أن عنصرين من $E$ يشتركان في صورتهما.

برهان. نكتب $\abs E = m$ و $\abs F = n$ مع $m > n$ ، ونختار تقابلين $u \colon \intint1m \to E$ و $v \colon F \to \intint1n$ . لو كان $f$ متباينًا لكان $v \circ f \circ u$ تطبيقًا متباينًا من $\intint1m$ في $\intint1n$ (فهو تركيب تطبيقات متباينة، القضية 1.26)، وهذا يناقض المبرهنة 2.2. ∎

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

يحوي برهان المبرهنة 2.2 أولَ حركة بارعة حقًّا في الفصل، وهي جديرة بأن تُعاد ببطء. والعقبة هي: أننا نريد، لتطبيق فرض الاستقراء، أن نحذف النقطة الأخيرة $m$ من مجموعة التعريف و النقطة الأخيرة $n+1$ من مجموعة الوصول، لكن $f$ قد يرسل نقطة أخرى $a$ إلى $n + 1$ ، فيُفسد حذف نقطة الوصول عندئذ التطبيق في موضع آخر. والعلاج: أن نركّب $f$ مع منقولة القيمتين $f(a)$ و $f(m)$ — وهي تقابل لمجموعة الوصول، فيُحفظ التباين — وبعدها تستقر القيمة المزعجة $n + 1$ في الموضع غير المؤذي $m$ ، فيصير الحذفان نظيفين. وهذا النمط، «سوِّ أولًا ثم اقطع»، يتكرر: فهو الذي يعيد به تراجع الاضطرابات توجيه $\sigma^{-1}(n+1)$ في مسألة نهاية الأسبوع من هذا الفصل، وهو كيفية ترقيع التبديلات في مسألة الزمرة المتناظرة من الفصل 7.

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

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

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

برهان. نفترض $f$ متباينًا. عندئذ يكون $f$ تقابلًا من $E$ على $f(E)$ ، ومنه $\abs{f(E)} = \abs{E} = \abs{F}$ . ولو فات $f(E)$ نقطة $y_0$ من $F$ لكان $f$ تطبيقًا متباينًا من $E$ في $F \setminus \{y_0\}$ ، وهي مجموعة عدد عناصرها $\abs{F} - 1 < \abs{E}$ — وهذا مستحيل حسب مبدأ الأدراج. إذن $f(E) = F$ : أي أن $f$ شامل، فهو إذن تقابليّ.

ونفترض $f$ شاملًا. نختار من أجل كل $y \in F$ سابقةً واحدة $s(y) \in E$ ؛ عندئذ $f \circ s = \mathrm{id}_F$ ، فيكون $s$ متباينًا (القضية 1.26). وبتطبيق الفقرة السابقة على $s$ (فعددا العناصر متساويان) يكون $s$ تقابليًا. ومن $f \circ s = \mathrm{id}_F$ نحصل على $f = \mathrm{id}_F \circ s^{-1} = s^{-1}$ ، ومنه يكون $f$ تقابليًا. وأخيرًا فإن التطبيق التقابلي متباين وشامل معًا بحكم التعريف، وبهذا تُغلق دورة الاستلزامات. ∎

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

على مجموعة منتهية تكون القضية 2.5 اختصارًا قويًا: فأيّ تطبيق متباين من $E$ إلى نفسها هو تلقائيًا تبديلة في $E$ — أي أن نصف التقابلية يأتي مجانًا. وينهار الاستلزامان معًا على المجموعات اللانهائية: فالتطبيق $n \mapsto n + 1$ متباين من $\N$ إلى $\N$ لكنه يفوت $0$ ، والتطبيق $\N \to \N$ الذي يرسل $0 \mapsto 0$ و $n \mapsto n - 1$ من أجل $n \geq 1$ شامل وغير متباين. وكلما استُدعيت هذه القضية كان فرض الانتهاء يقوم بعمل حقيقي — وهو موضوع تستكشفه مسألة نهاية الأسبوع في الفصل 1 من الجهة المقابلة، حيث تكون المجموعات اللانهائية هي بالضبط تلك التي تقبل تطبيقات ذاتية كهذه.

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

تأمّل التطبيق $f$ على $\{0, 1, \dots, 6\}$ الذي يرسل $k$ إلى باقي قسمة $3k$ على $7$ ؛ وجدول قيمه هو

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

هل $f$ تقابل؟ يكفي التباين وحده (القضية 2.5): فإذا كان للعددين $3k$ و $3k'$ الباقي نفسه قسم $7$ الفرق $3(k - k')$ ، وبما أن $7$ أوليّ ولا يقسم $3$ فإنه يقسم $k - k'$ (مبرهنة إقليدس المساعدة، المستعملة هنا على مستوى الثانوية والمبرهن عليها في الفصل 6)؛ ومع $\abs{k - k'} \leq 6$ يفرض هذا $k = k'$ . ويأتي الشمول مجانًا — دون حاجة إلى حلّ $3k \equiv c$ من أجل كل $c$ ، وإن كان الجدول يؤكد ظهور كل قيمة مرة واحدة بالضبط. وهذا الاختصار عتيد: فهو يبرهن على قابلية الضرب الترديدي للقلب (الفصل 6)، وهو محرك الازدواج في مبرهنة ويلسون، ويعود في الجبر الخطي في صورة «تشاكل ذاتي لفضاء منته البُعد يكون متباينًا إذا وفقط إذا كان شاملًا» (الفصل 19).

2.2 مبادئ العدّ

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

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

إذا كان $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}$ .
وفي الحالة العامة، $\abs{E \cup F} = \abs{E} + \abs{F} - \abs{E \cap F}$ .
$\abs{E \times F} = \abs{E} \times \abs{F}$ .
مجموعة كل التطبيقات من $E$ إلى $F$ ، وهي $F^E$ ، تحقق $\abs{F^E} = \abs{F}^{\abs{E}}$ .
$\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) المجموعة $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) المجموعة $E \times F$ اتحاد منفصل، على $x \in E$ ، للمجموعات $\{x\} \times F$ التي عدد عناصر كلٍّ منها $\abs{F}$ ؛ فطبّق (1).

(4) التطبيق من $E = \{x_1, \dots, x_m\}$ إلى $F$ هو بالضبط اختيار المتتالية المنتهية ذات $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 .

أي إن قرابة نصف الرموز السرّية تكرّر رقمًا. والفكرة النافذة: كلما صيغ عدٌّ بعبارة «على الأقل» أو «ليس كلها» فجرّب المتمّمة أولًا — إذ تضمن قاعدة الجمع أن $\abs{A} = \abs{E} - \abs{\overline A}$ ، وكثيرًا ما تكون المتمّمة تشكيلة واحدة نظيفة.

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

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

\binom{7}{4} = 35 .

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

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

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

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

لتكن $E$ مجموعة حيث $\abs{E} = n$ وليكن $0 \leq k \leq n$ .

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

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

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

عدد الترتيبات من الرتبة $k$ في $E$ هو $n (n-1) \cdots (n-k+1) = \dfrac{n!}{(n-k)!}$ ؛
وعدد التبديلات في $E$ هو $n!$ ؛
و $\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)!$ ترتيبًا دائريًا — ثم رتّب الضيفين داخل كتلتهما ( $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 .

برهان. المتطابقة الأولى: التطبيق $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 (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$ : أي إن نصف أجزاء مجموعة غير خالية بالضبط له عدد عناصر زوجيّ.

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

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

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

وإليك المتطابقة نفسها دون أيّ جبر البتة. الطرف الأيمن يعدّ الكلمات ذات الطول $n$ على الأبجدية $\{0, 1, 2\}$ (بقاعدة الجداء). صنّف كل كلمة بحسب مجموعة المواضع $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)

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

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

جمع حالات غير منفصلة. تقتضي قاعدة الجمع وجود تجزئة؛ فإذا كانت تشكيلة ما قد تحقق حالتين في آن واحد عُدَّت مرتين — والعلاج هو الاحتواء والاستبعاد (المبرهنة 2.24) أو تقسيم أدقّ للحالات.
المرتَّب في مقابل غير المرتَّب. اختيار «لجنة من اثنين» هو $\binom n2$ ، لا $n(n-1)$ : فقرّر قبل الحساب إن كان الاختيار يحمل ترتيبًا، وإذا كان العدّ المرتَّب أسهل فاقسم في النهاية على عدد الترتيبات — لكن بشرط أن ينشأ كل غرض غير مرتَّب من العدد نفسه من الأغراض المرتَّبة.
اختيارات على مراحل غير مستقلة. تقتضي قاعدة الجداء أن يكون عدد الخيارات في كل مرحلة مستقلًا عن الاختيارات السابقة. فقولنا «اختر قائدًا ثم نائبًا مختلفًا عنه» سليم ( $n(n-1)$ )؛ أمّا «اختر لاعبين ينسجمان معًا» فليس جداءً على مرحلتين البتة.
العدّ المزدوج بحكم الإنشاء. بناء كل غرض مرتين — مثل عدّ الأيدي التي فيها آسٌ واحد على الأقل بحاصل (اختر آسًا) $\times$ (اختر $4$ أوراق أخرى) — يعدّ الأيدي ذات الآسين عدًّا زائدًا. فعبارة «على الأقل» تستدعي المتمّمة في كل الأحوال تقريبًا (المثال 2.9).

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

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

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

للبرهان على متطابقة بين تعبيرين عدديين، جد مجموعة منتهية واحدة يعدّها الطرفان معًا — وهي عادةً مجموعة من الأزواج — ثم احسب عدد عناصرها بترتيبين مختلفين. والنموذج الأصلي هو مبرهنة المصافحات المساعدة: في حفل ما، عُدَّ الأزواج (شخص، يد صافحها). فالجمع على الأشخاص يعطي $\sum_p d_p$ (أي عدد مصافحات كل شخص $p$ )؛ والجمع على المصافحات يعطي ضعف عدد المصافحات (إذ تضمّ كل مصافحة شخصين). ومنه فإن $\sum_p d_p$ زوجيّ — فعدد الأشخاص الذين صافحوا عددًا فرديًا من الأيدي زوجيّ دائمًا، وهو استنتاج غير بديهي حصلنا عليه دون أيّ صيغة البتة. والمحرك نفسه يشغّل التمرين 2.12 وعدة أسئلة من مسألة نهاية الأسبوع أدناه.

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

ما متوسط عدد عناصر جزء من مجموعة $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: فكثيرًا ما يعوّض ازدواجٌ حسن الاختيار عن متطابقة.

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

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

من أجل مجموعات منتهية $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. إذن يُعدّ كل عنصر من الاتحاد مرة واحدة بالضبط. ∎

مثال 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 ويُطوَّر في مجلد السنة 2.

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

الاضطراب تبديلة بلا نقطة صامدة. لتكن $A_i$ مجموعة تبديلات $\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)، فإن قرابة $37\%$ من جميع التبديلات اضطرابات، مهما تكن $n$ .

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

المعاملات الثنائية أكثر أغراض هذا الفصل إعادةَ استعمال: فهي تحرّك مبرهنة ثنائي الحدّ في الفصل 8 (نشر $(X + a)^n$ )، وصيغة لايبنتز للمشتقة من الرتبة $n$ لجداء في الفصل 14، ومعاملات نشور تايلور في الفصل 16. وتعود التبديلات في صورة زمرة — مع الإشارة المبنية على عدّ الانقلابات — في الفصل 7، وتعرّف الإشارةُ بدورها المحدداتِ في الفصل 22. والاحتواء والاستبعاد ومبادئ العدّ هي العمود الفقري المنتهي للاحتمال المتقطع، الذي يُطوَّر في مجلد السنة 2؛ أمّا أعداد الاضطراب في المثال 2.26 فتُدرس بعمق في مسألة نهاية الأسبوع أدناه.

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 ★

برهن على أنه في أيّ مجموعة من $13$ شخصًا يشترك اثنان في شهر الميلاد؛ وعلى أنه من بين أيّ $n + 1$ عددًا صحيحًا مختارًا من $\intint{1}{2n}$ يوجد عددان متتاليان. (مبدأ الأدراج في المرتين: سمِّ الأدراج.)

حل

حل التمرين 2.4.

شهور الميلاد: الأدراج هي الشهور $12$ ؛ و $13$ شخصًا في $12$ درجًا يفرضون وجود شخصين في الدرج نفسه (النتيجة 2.3).

الأعداد المتتالية: الأدراج هي الأزواج $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. (وبطريقة أخرى: اشتقّ $(1+x)^n = \sum_k \binom nk x^k$ وضع $x = 1$ .)

تمرين 2.6 ★★

كم تطبيقًا متزايدًا تمامًا يوجد من $\intint{1}{k}$ إلى $\intint{1}{n}$ ؟ استنتج عدد التطبيقات المتزايدة (لا بالضرورة تمامًا). إرشاد للعدّ الثاني: التطبيق $f$ متزايد $\mapsto$ $g(i) = f(i) + i - 1$ .

حل

حل التمرين 2.6.

التطبيق المتزايد تمامًا $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$ عنصرًا في مجموعة مقسومة إلى كتلتين حجمهما $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.

اقسم مجموعة $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$ مجموعة مضاعفات $d$ في $\intint{1}{1000}$ ، ومنه $\abs{A_d} = \lfloor 1000/d \rfloor$ . وبالاحتواء والاستبعاد (المبرهنة 2.24) مع $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 ★★

عُدَّ التطبيقات الشاملة من مجموعة ذات $4$ عناصر على مجموعة ذات $2$ عنصرين؛ ثم على مجموعة ذات $3$ عناصر. إرشاد: عُدَّ التطبيقات غير الشاملة بالاحتواء والاستبعاد على القيم الفائتة.

حل

حل التمرين 2.9.

على مجموعة ذات $2$ عنصرين: جميع التطبيقات $2^4 = 16$ عدا التطبيقين الثابتين $2$ : أي $14$ تطبيقًا شاملًا.

وعلى مجموعة ذات $3$ عناصر: بالاحتواء والاستبعاد على القيم الفائتة، يكون عدد التطبيقات من مجموعة ذات $4$ عناصر إلى مجموعة ذات $3$ عناصر التي تفوتها قيمة واحدة على الأقل هو $\binom 31 2^4 - \binom 32 1^4 = 48 - 3 = 45$ ؛ وعدد التطبيقات كلها $3^4 = 81$ ؛ فعدد الشاملة: $81 - 45 = 36$ . (وللتحقق: التطبيق الشامل من $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 الخاصة بالعدد $D_n$ بالتفصيل، واستنتج $n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k}$ (وبرهن كذلك على هذه المتطابقة مباشرةً بتصنيف التبديلات بحسب مجموعة نقاطها الصامدة).

حل

حل التمرين 2.11.

مع $A_i = \{\sigma : \sigma(i) = i\}$ ، تصمد التبديلة من $\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}$ بحسب مجموعة نقاطها الصامدة $F(\sigma)$ . ومن أجل جزء $F$ مثبَّت فيه $k$ عنصرًا، تكون التبديلات التي تحقق $F(\sigma) = F$ هي بالضبط اضطرابات المتمّمة: أي $D_{n-k}$ تبديلة. وبالجمع على اختيارات $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. وصيغة الاحتواء والاستبعاد ليست إلا الحركة الافتتاحية: فهذه المسألة تطوّر التراجعات التي تحسب $D_n$ ، وبرهانين مستقلين آخرين على الصيغة، والمبرهنة اللافتة القائلة إن $D_n$ أقرب عدد صحيح إلى $n!/\eu$ ، والتوزيع الكامل للنقاط الصامدة في تبديلة عشوائية، والحساب الطريف للمتتالية $(D_n)$ . وفي كل ما يلي، يرمز $D_n$ إلى عدد الاضطرابات (أي التبديلات الخالية من النقاط الصامدة) في $\intint1n$ ، مع الاصطلاح $D_0 = 1$ (إذ إن التبديلة الخالية بلا نقطة صامدة).

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

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

$\sum_{\sigma} \abs{\mathrm{Fix}(\sigma)} = n! :$

أي إن للتبديلة العشوائية، في المتوسط، نقطة صامدة واحدة بالضبط، مهما يكن $n \geq 1$ .

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

برهن توفيقيًا، من أجل $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$ .
بوضع $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).$
انطلاقًا من السؤال 6، برهن بالاستقراء على صيغة المثال 2.26،

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

— وهو برهان مستقل كل الاستقلال عن الاحتواء والاستبعاد.
(القلب الثنائي) لتكن $(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.)
طبّق السؤال 8 على المتطابقة $n! = \sum_k \binom nk D_{n-k}$ من التمرين 2.11 للحصول على برهان ثالث على صيغة $D_n$ .

الجزء 3 — أقرب عدد صحيح إلى $n!/\eu$ . اقبل في هذا الجزء — فالنظرية مبنيّة في الفصل 17 — أن $\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$ .

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

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

ثبّت $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.)
بعدّ مزدوج للثلاثيات $(\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$ من جديد، ومطابق لقانون بواسون من جديد.
احسب نسبة التبديلات ذات نقطة صامدة واحدة على الأقل من أجل $n = 4, 5, 6$ (في صورة كسور وبأربعة أرقام عشرية)، وقارنها بالمقدار $1 - \eu^{-1} \approx 0.6321$ .
بيّن مباشرة — دون حاجة إلى أيّ نهايات — أن $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}$ .
(تبادل الهدايا السرّي) يسحب $n$ شخصًا اسمًا واحدًا من قبعة؛ فإذا سحب أحدهم اسمه أُعيد السحب كله من جديد. باستعمال الواقعة المعيارية القائلة إن حدثًا احتماله $p$ يقتضي في المتوسط $1/p$ محاولة، قدّر متوسط عدد السحوب الكاملة اللازمة، واستنتج أن هذا الإجراء يكلّف نحو $\eu \approx 2.72$ سحبة في المتوسط، وذلك باستقلال جوهري عن $n$ .

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

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

حل

حل المسألة 2.1.

1. $D_1 = 0$ (فالتبديلة الوحيدة تصمد عند $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$ . ثلاثة في كل مجموعة: أي $D_4 = 9$ .

2. التبديلة ذات $k$ نقطة صامدة بالضبط محدَّدة باختيار مجموعة نقاطها الصامدة $F$ ( $\binom nk$ طريقة) مع قصرها على المتمّمة، الذي يجب أن يكون تبديلة على $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)!$ تبديلة. ومنه فإن عدد الأزواج هو $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$ تبديلة في $\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): فهو ينعدم من أجل $j < n$ ويساوي $1$ من أجل $j = n$ . فلا يبقى إلا $j = n$ ، ويكون الطرف الأيمن هو $b_n$ ، وهو المطلوب.

9. بالتناظر $\binom nk = \binom n{n-k}$ ، تُكتب متطابقة التمرين 2.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)!$ تبديلة. والمجموع: $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. السحبة الكاملة الواحدة تبديلة عشوائية منتظمة، وتصحّ عندما تكون اضطرابًا: أي باحتمال $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$ إلى العبارة الشفافة «أقرب عدد صحيح إلى $n!/\eu$ » (الأسئلة 10–14).

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

المصطلحات المعرَّفة في هذا الفصل

عرض كل المصطلحات (395) في المسرد