--- title: "التوافيق والعدّ" book: "رياضيات المرحلة الثانوية" subject: math language: ar chapter: 27 exercises: 10 source: https://one-course.com/books/math/2/ar/chapter/27-combinatorics-and-counting --- # الفصل 27 — التوافيق والعدّ التوافيق فنّ العدّ دون سرد. ويكفي مبدآها الابتدائيان — اجمع أحجام البدائل المنفصلة، واضرب أعداد الاختيارات المستقلة — لعدّ الترتيبات [والتبديلات](#def-g12-comb-permutation) وأجزاء مجموعة منتهية، ويبلغان ذروتهما في مبرهنة ثنائي الحد. ## 27.1 مبدآ العدّ نكتب $\abs{E}$ للدلالة على عدد عناصر (أي *عدد العناصر*) مجموعة منتهية $E$. **قضية 27.1 (مبدأ الجمع).** إذا قُسّمت مجموعة منتهية $E$ إلى أجزاء $A_1, \dots, A_k$ (منفصلة مثنى مثنى، واتحادها $E$)، فإن $$ \abs{E} = \abs{A_1} + \abs{A_2} + \dots + \abs{A_k}. $$ **قضية 27.2 (مبدأ الضرب).** إذا بُني شيء بتتابع $k$ اختيارًا، مع $n_1$ إمكانية من أجل الاختيار الأول، و، *مهما كانت الاختيارات [السابقة](https://one-course.com/books/math/2/ar/chapter/3-functions#def-g10-functions-function)*، $n_i$ إمكانية من أجل الاختيار رقم $i$، فإن عدد الأشياء المبنية هو $n_1 \times n_2 \times \dots \times n_k$. **برهان.** يُبرهن على العبارتين بالتراجع على $k$؛ والحالة $k = 2$ من الثانية ترجع إلى عدّ جدول مستطيلي سطرًا سطرًا. ∎ **مثال 27.3.** مطعم يقدّم 4 مقبلات و 6 أطباق رئيسية و 3 حلويات: أي $4 \times 6 \times 3 = 72$ وجبة مختلفة من ثلاثة أطباق. ## 27.2 القوائم المرتبة والتبديلات والعوامل **تعريف 27.4 (القوائم المرتبة ذات kkk حدًا).** *القائمة المرتبة ذات $k$ حدًا* في مجموعة $E$ هي قائمة مرتبة $(x_1, \dots, x_k)$ من عناصر $E$، مع السماح بالتكرار. وأما القائمة المرتبة ذات $k$ حدًا وعناصرها *متمايزة* فهي *ترتيبة* لعدد $k$ من عناصر $E$. **قضية 27.5.** ليكن $\abs E = n$. عدد القوائم المرتبة ذات $k$ حدًا في $E$ هو $n^k$. وعدد ترتيبات $k$ من عناصر $E$ (حيث $0 \leq k \leq n$) هو $$ n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!}, $$ حيث $n! = 1 \times 2 \times \dots \times n$ (مع $0! = 1$) هو *عاملي* العدد $n$. **برهان.** بمبدأ الضرب: من أجل قائمة مرتبة ذات $k$ حدًا توجد $n$ إمكانية عند كل خطوة من الخطوات $k$؛ ومن أجل [ترتيبة](#def-g12-comb-tuples)، توجد $n$ إمكانية من أجل $x_1$، ثم $n - 1$ من أجل $x_2$ (لأن عنصرًا استُعمل)، …، و $n - k + 1$ من أجل $x_k$. ∎ **تعريف 27.6 (التبديلة).** *التبديلة* للمجموعة $E$ هي [ترتيبة](#def-g12-comb-tuples) لعناصر $E$ كلها البالغ عددها $n$: أي [ترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system) للمجموعة $E$. وحسب [القضية 27.5](#prop-g12-comb-tuples) (الحالة $k = n$)، يكون عدد تبديلات مجموعة فيها $n$ عنصرًا هو $n!$. **مثال 27.7.** يمكن لخمسة عدّائين أن ينهوا سباقًا بعدد $5! = 120$ ترتيبًا مختلفًا. وعدد منصات التتويج الممكنة (المراكز الثلاثة الأولى) هو $5 \times 4 \times 3 = 60$. ## 27.3 التوفيقات والمعاملات الثنائية **تعريف 27.8 (التوفيقات).** *التوفيقة* لعدد $k$ من عناصر $E$ هي جزء من $E$ فيه $k$ عنصرًا (بلا [ترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system) وبلا تكرار). ويُكتب عددها $\dbinom{n}{k}$، ويُقرأ “$n$ اختر $k$”. **مبرهنة 27.9.** من أجل $0 \leq k \leq n$: $$ \binom{n}{k} = \frac{n!}{k!\,(n-k)!} . $$ **برهان.** عُدّ ترتيبات $k$ من عناصر $E$ بطريقتين. مباشرةً: $\frac{n!}{(n-k)!}$. وبطريقة أخرى، اختر أولًا الجزء الحامل ($\binom nk$ طريقة)، ثم رتّبه ($k!$ طريقة)؛ فيعطي مبدأ الضرب $\binom{n}{k}\,k!$. وبالمساواة بينهما، $\binom nk = \frac{n!}{k!(n-k)!}$. ∎ **قضية 27.10 (المتطابقات الأساسية).** من أجل $0 \leq k \leq n$: $$ \binom{n}{0} = \binom{n}{n} = 1, \qquad \binom{n}{1} = n, \qquad \binom{n}{k} = \binom{n}{n-k}, $$ و*قاعدة باسكال*: من أجل $1 \leq k \leq n-1$، $$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. $$ **برهان.** يصح التناظر $\binom nk = \binom{n}{n-k}$ لأن أخذ المتممات يقابل الأجزاء ذات $k$ عنصرًا بالأجزاء ذات $(n-k)$ عنصرًا، واحدًا بواحد. وأما [قاعدة باسكال](#prop-g12-comb-identities)، فثبّت عنصرًا $a \in E$ ورتّب الأجزاء ذات $k$ عنصرًا في تلك التي تحوي $a$ — وتُنال بإضافة $a$ إلى جزء ذي $(k-1)$ عنصرًا من $E \setminus \{a\}$، وعددها $\binom{n-1}{k-1}$ — و تلك التي تتجنب $a$، وهي الأجزاء ذات $k$ عنصرًا من $E \setminus \{a\}$، وعددها $\binom{n-1}{k}$. ثم اختم بمبدأ الجمع. ∎ وتولّد [قاعدة باسكال](#prop-g12-comb-identities) المعاملات سطرًا بعد سطر — *[مثلث باسكال](https://one-course.com/books/math/2/ar/chapter/19-the-binomial-distribution#prop-g11-binom-pascal)*: فكل خانة مجموع الخانتين اللتين فوقها. ![مثلث باسكال، السطور من n = 0 إلى 5: وقاعدة باسكال 41 + 42 = 52 في العمل.](https://one-course.com/images/onecourse/chapters/math-2/g12-comb/fig-37a02167c00d.svg) *[مثلث باسكال](https://one-course.com/books/math/2/ar/chapter/19-the-binomial-distribution#prop-g11-binom-pascal)، السطور من $n = 0$ إلى $5$: [وقاعدة باسكال](#prop-g12-comb-identities) $\binom{4}{1} + \binom{4}{2} = \binom{5}{2}$ في العمل.* **مبرهنة 27.11 (مبرهنة ثنائي الحد).** من أجل كل $a, b \in \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)$ ($n$ عاملًا): فكل حد من [النشر](https://one-course.com/books/math/2/ar/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-expand) يختار $a$ أو $b$ في كل عامل، فينتج $a^k b^{n-k}$ حيث $k$ عدد العوامل التي تسهم بالعنصر $a$. وعدد طرائق اختيار هذه العوامل $k$ من بين $n$ هو $\binom nk$، وهو إذن معامل $a^k b^{n-k}$. ∎ **نتيجة 27.12.** $\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ و $\displaystyle\sum_{k=0}^{n} (-1)^k\binom{n}{k} = 0$ (حيث $n \geq 1$). **برهان.** خذ $a = b = 1$، ثم $a = -1$ و $b = 1$ في مبرهنة ثنائي الحد. وللمتطابقة الأولى معنى مباشر أيضًا: فلمجموعة فيها $n$ عنصرًا $2^n$ جزءًا (إذ كل عنصر داخل أو خارج: بمبدأ الضرب)، مرتَّبةً بالحجم. ∎ **طريقة 27.13 (اختيار النموذج المناسب).** قبل العدّ، أجب عن سؤالين: *هل [الترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system) مهم؟* و *هل التكرار مسموح؟* | | [الترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system) مهم | [الترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system) غير مهم | | --- | --- | --- | | التكرار مسموح | $n^k$ (قوائم مرتبة) | (الجامعة) | | لا تكرار | $\frac{n!}{(n-k)!}$ (ترتيبات) | $\binom nk$ (أجزاء) | وأما سحب كرات من كيس: *بالإرجاع وبالترتيب* $\to$ قوائم مرتبة؛ و*بلا إرجاع وبالترتيب* $\to$ ترتيبات؛ و*حفنة دفعة واحدة* $\to$ أجزاء. ## 27.4 تمارين **تمرين 27.1 ★.** تتكوّن لوحة تسجيل من 2 حرف (A–Z)، ثم 3 أرقام، ثم 2 حرف. فكم لوحة ممكنة؟ وكم منها بلا محرف مكرَّر؟ **حل التمرين 27.1.** بمبدأ الضرب: $26^2 \times 10^3 \times 26^2 = 26^4 \times 10^3 = 456\,976\,000$. وبلا محارف مكرَّرة، يجب أن تكون الحروف الأربعة متمايزة ($26 \times 25 \times 24 \times 23$ طريقة، بملء مواضع الحروف [بالترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system)) والأرقام الثلاثة متمايزة ($10 \times 9 \times 8$): $$ 26 \times 25 \times 24 \times 23 \times 10 \times 9 \times 8 = 358\,800 \times 720 = 258\,336\,000 . $$ **تمرين 27.2 ★.** احسب $\dbinom{8}{3}$ و $\dbinom{10}{8}$، وبسّط $\dfrac{\binom{n}{2}}{\binom{n+1}{2}}$. **حل التمرين 27.2.** $\dbinom83 = \dfrac{8 \times 7 \times 6}{3!} = 56$؛ $\dbinom{10}{8} = \dbinom{10}{2} = \dfrac{10 \times 9}{2} = 45$؛ $$ \frac{\binom n2}{\binom{n+1}2} = \frac{n(n-1)/2}{(n+1)n/2} = \frac{n-1}{n+1}. $$ **تمرين 27.3 ★.** في قسم فيه 30 تلميذًا، يجب انتخاب لجنة من 4 تلاميذ، ثم رئيس وأمين مال داخل اللجنة (ولا يمكن لشخص واحد أن يشغل المنصبين معًا). فكم نتيجة ممكنة؟ **حل التمرين 27.3.** اختر اللجنة: $\binom{30}{4}$ طريقة. ثم اختر الرئيس وأمين المال من بين الأربعة، [بالترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system): $4 \times 3 = 12$ طريقة. والمجموع $$ \binom{30}{4} \times 12 = 27\,405 \times 12 = 328\,860 . $$ **تمرين 27.4 ★.** انشر $(x + 2)^5$ و $(1 - x)^6$ باستعمال مبرهنة ثنائي الحد. وما معامل $x^3$ في $(2x + 3)^7$؟ **حل التمرين 27.4.** $$ (x+2)^5 = x^5 + 10x^4 + 40x^3 + 80x^2 + 80x + 32 , $$ $$ (1-x)^6 = 1 - 6x + 15x^2 - 20x^3 + 15x^4 - 6x^5 + x^6 . $$ وفي $(2x+3)^7$، يكون الحد في $x^3$ هو $\binom{7}{3}(2x)^3\,3^4 = 35 \times 8 \times 81\, x^3$: فالمعامل هو $22\,680$. **تمرين 27.5 ★★.** تتكوّن يد البوكر المعيارية من 5 أوراق من رزمة فيها 52 ورقة. 1. كم يدًا توجد؟ 2. كم يدًا تحوي آصًا واحدًا بالضبط؟ وكم يدًا تحوي آصًا واحدًا على الأقل؟ 3. كم يدًا تكون “بيتًا كاملًا” (ثلاث أوراق من رتبة واحدة، واثنتان من رتبة أخرى)؟ **حل التمرين 27.5.** *1.* $\dbinom{52}{5} = 2\,598\,960$. *2.* آص واحد بالضبط: اخترْه ($4$ طرائق) وأكمل بعدد $4$ من الأوراق غير الآصات: $4 \times \binom{48}{4} = 4 \times 194\,580 = 778\,320$. وآص واحد على الأقل: بالعدّ المتمم، $\binom{52}{5} - \binom{48}{5} = 2\,598\,960 - 1\,712\,304 = 886\,656$. *3.* اختر رتبة الثلاثية ($13$)، ورموزها ($\binom43 = 4$)، ورتبة الزوج ($12$ باقية)، ورموزه ($\binom42 = 6$): $13 \times 4 \times 12 \times 6 = 3744$. **تمرين 27.6 ★★.** كم جناسًا (إعادة [ترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system) للحروف، ذا معنى أو بلا معنى) لكلمة “حساب”؟ وكم لكلمة “اللاما”؟ (إرشاد من أجل “اللاما”: ضع حروف الألف الثلاثة أولًا.) **حل التمرين 27.6.** لكلمة “حساب” 4 حروف متمايزة: أي $4! = 24$ جناسًا. ولكلمة “اللاما” 6 حروف: ثلاث ألفات ولامان وميم واحدة. اختر مواضع الألفات ($\binom63$)، ثم مواضع اللامين من الباقي ($\binom32$)، وتأخذ الميم الموضع الأخير: $$ \binom{6}{3}\binom{3}{2} = 20 \times 3 = 60 . $$ (وبصيغة مكافئة $\frac{6!}{3!\,2!\,1!} = 60$.) **تمرين 27.7 ★★.** برهن على المتطابقة $k\dbinom{n}{k} = n\dbinom{n-1}{k-1}$ (حيث $1 \leq k \leq n$) بطريقتين: بالصيغة [العاملية](#prop-g12-comb-tuples)، وبعدّ الأزواج (لجنة من $k$ شخصًا، ورئيسها) المختارة من $n$ شخصًا بطريقتين. **حل التمرين 27.7.** *جبريًا:* $$ k\binom nk = \frac{k\,n!}{k!(n-k)!} = \frac{n!}{(k-1)!\,(n-k)!} = n\,\frac{(n-1)!}{(k-1)!\bigl((n-1)-(k-1)\bigr)!} = n\binom{n-1}{k-1}. $$ *وبالعدّ المزدوج:* عُدّ الأزواج (لجنة من $k$، ورئيسها فيها). فإما أن تختار اللجنة ($\binom nk$) ثم رئيسها ($k$): فتكون $k\binom nk$ زوجًا. وإما أن تختار الرئيس أولًا ($n$ إمكانية) ثم الأعضاء $k-1$ الآخرين من بين الباقين $n-1$: أي $n\binom{n-1}{k-1}$ زوجًا. **تمرين 27.8 ★★.** مسار في المستوي يذهب من $(0,0)$ إلى $(m, n)$ بخطوات واحدية نحو الشرق أو نحو الشمال. بيّن أن عدد هذه المسارات هو $\dbinom{m+n}{m}$. **حل التمرين 27.8.** يتكوّن المسار من $m + n$ خطوة بالضبط، منها $m$ نحو الشرق و $n$ نحو الشمال؛ وهو محدَّد تمامًا بمجموعة اللحظات (من بين $m+n$) التي يُخطى فيها نحو الشرق. وعدد هذه الاختيارات $\binom{m+n}{m}$. **تمرين 27.9 ★★★.** برهن على *متطابقة فاندرموند*: من أجل $0 \leq k \leq m + n$، $$ \binom{m+n}{k} = \sum_{j=0}^{k} \binom{m}{j}\binom{n}{k-j}, $$ بعدّ الأجزاء ذات $k$ عنصرًا في مجموعة مقسومة إلى فريق من $m$ و فريق من $n$. واستنتج أن $\displaystyle\sum_{j=0}^{n}\binom{n}{j}^{\!2} = \binom{2n}{n}$. **حل التمرين 27.9.** اقسم مجموعة فيها $m + n$ شخصًا إلى فريق $A$ فيه $m$ وفريق $B$ فيه $n$. فالجزء ذو $k$ عنصرًا يحوي عددًا ما $j$ من أعضاء $A$ (حيث $0 \leq j \leq k$) و $k - j$ من أعضاء $B$؛ ومن أجل $j$ ثابت يوجد $\binom mj \binom{n}{k-j}$ جزءًا كهذا، ويعطي مبدأ الجمع على $j$ متطابقة فاندرموند. ومع $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$. **تمرين 27.10 ★★★.** باستعمال مبرهنة ثنائي الحد، بيّن أنه من أجل كل $n \geq 1$، $$ \sum_{k=1}^{n} k \binom{n}{k} = n\,2^{n-1}. $$ (إرشاد: إما أن تشتق $(1+x)^n$، وإما أن تستعمل [التمرين 27.7](#exo-g12-comb-7).) **حل التمرين 27.10.** *بواسطة [التمرين 27.7](#exo-g12-comb-7):* $$ \sum_{k=1}^n k\binom nk = \sum_{k=1}^n n\binom{n-1}{k-1} = n\sum_{j=0}^{n-1}\binom{n-1}{j} = n\,2^{n-1}, $$ حسب [النتيجة 27.12](#cor-g12-comb-sums). *وبواسطة الاشتقاق:* اشتقاق $(1+x)^n = \sum_k \binom nk x^k$ يعطي $n(1+x)^{n-1} = \sum_k k \binom nk x^{k-1}$؛ ثم قدّر عند $x = 1$. ## 27.5 مسألة: فنّ العدّ مرتين **مسألة 27.1.** مسألة نهاية الأسبوع — النجوم والقضبان، والقبعات المشوَّشة، ومتطابقات تُبرهن بعدّ الشيء نفسه بطريقتين أعمق حيلة في التوافيق بسيطة إلى حدّ نزع السلاح: عُدّ المجموعة نفسها مرتين، بطريقتين مختلفتين، ثم ساوِ بين الجوابين. وتتدرّب هذه المسألة على نماذج [الطريقة 27.13](#met-g12-comb-model)، وتضيف تقنية لم يحتجها درس الفصل — *النجوم والقضبان* في عدّ المثلجات — ثم تعدّ *القبعات المشوَّشة* الشهيرة عدًّا مضبوطًا، وتجد العدد $\frac1\eu$ ينتظر في قاع كومة القبعات، في ظهوره الثالث في هذا الكتاب. **الجزء الأول — اختيار النموذج.** 1. عُدّ لوحات التسجيل المكوّنة من $2$ حرف يتبعهما $3$ أرقام؛ ثم أجناس كلمة “اللاما”. 2. من رزمة فيها $32$ ورقة، عُدّ الأيدي ذات $5$ أوراق؛ ثم الأيدي التي تحوي بالضبط $2$ من الآصات $4$ . 3. يمشي روبوت من $(0,0)$ إلى $(4,3)$ مستعملًا خطوات واحدية نحو اليمين أو نحو الأعلى فقط: فكم مسارًا؟ (رمّز المسار كلمةً بالحرفين R و U.) 4. انشر $(1 + x)^4$ بمبرهنة ثنائي الحد ( [المبرهنة 27.11](#thm-g12-comb-binomial) )؛ ثم قدّر عند $x = 1$ و $x = -1$ : فأي متطابقتين بخصوص الأعداد $\binom nk$ تسقطان؟ 5. برهن بالعدّ المزدوج على أن $k\binom nk = n\binom{n-1}{k-1}$ (بعدّ اللجان ذات الرئيس بطريقتين)، واستنتج $\sum_{k=0}^{n} k\binom nk = n\,2^{n-1}$ . **الجزء الثاني — النجوم والقضبان.** 6. محل مثلجات يبيع $4$ نكهات؛ وأنت تطلب $10$ كرات (وقد تتكرر النكهات، [وترتيبها](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system) في الكأس غير مهم). رمّز الطلب صفًا من $10$ نجوم (كرات) يفصلها $3$ قضبان (تغيرات النكهة)، ثم عُدّ الطلبات. 7. عُدّ الثلاثيات من [الأعداد الصحيحة](https://one-course.com/books/math/2/ar/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) غير السالبة حيث $x + y + z = 12$ . 8. عُدّ الثلاثيات من [الأعداد الصحيحة](https://one-course.com/books/math/2/ar/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) *الموجبة تمامًا* حيث $x + y + z = 12$ (عوّض $x = 1 + x'$ ، وهكذا). 9. كم حدًا أحاديًا متمايزًا يظهر في [نشر](https://one-course.com/books/math/2/ar/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-expand) $(a + b + c)^5$ ؟ 10. تحقق من سلامة المنهج: عُدّ طلبات $3$ كرات من $2$ نكهة بالصيغة، ثم اسردها كلها وقارن. 11. قل بالضبط أين دخلت عبارة “الكرات متطابقة” في الترميز — ثم عُدّ ما يحدث بدلًا من ذلك إذا أُكلت الكرات [بالترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system) (بمواضع متمايزة)، بقائمة تحقق [الطريقة 27.13](#met-g12-comb-model) . **الجزء الثالث — القبعات المشوَّشة.** *التشويش* هو إعادة [توزيع](https://one-course.com/books/math/2/ar/chapter/18-probability-and-random-variables#def-g11-prob-rv) $n$ قبعة على أصحابها $n$ بحيث *لا أحد* ينال قبعته؛ وليكن $D_n$ عددها. (وقد بيّن [المسألة 18.1](https://one-course.com/books/math/2/ar/chapter/18-probability-and-random-variables#pb-g11-prob-1) أن ضيفًا واحدًا وسطيًا يستعيد قبعته — والآن نعدّ الحفلات المنكوبة تمامًا عدًّا مضبوطًا.) 12. احسب $D_1$ و $D_2$ و $D_3$ بالسرد، و $D_4$ بصبر (أو بذكاء). 13. برّر العلاقة التراجعية $D_n = (n - 1)\left(D_{n-1} + D_{n-2}\right)$ : فالضيف 1 ينال قبعةً ما $k \neq 1$ ( $n - 1$ اختيارًا)؛ ثم قسّم بحسب ما إذا كان الضيف $k$ ينال القبعة 1 أم لا. وتحقق من أنها تعيد إنتاج $D_4$ ، ثم احسب $D_5$ . 14. من أجل $n = 3$ ، برهن بمبدأ الاحتواء والاستبعاد (بطرح التوزيعات التي تثبّت قبعة واحدة على الأقل، ثم إعادة إضافة ما عُدّ زيادة) على أن $D_3 = 3!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}\right)$ ، ثم صُغ الصيغة العامة. 15. احسب $\frac{D_5}{5!}$ وقارنه بالمقدار $\frac1\eu \approx 0.3679$ : [فاحتمال](https://one-course.com/books/math/2/ar/chapter/9-probability-and-sampling#def-g10-proba-distribution) أن تتشوّش حفلة كبيرة مخلوطة تشويشًا كاملًا هو $\frac1\eu$ — وهو الظهور الثالث لهذا الثابت، بعد اليانصيب والسكرتيرة في [المسألة 23.1](https://one-course.com/books/math/2/ar/chapter/23-exponential-and-logarithm#pb-g12-exp-1) . (والسبب: أن صيغة السؤال 14 هي بداية متسلسلة شهيرة للمقدار $\eu^{-1}$ ، محكية في الكتب الجامعية.) 16. تبادل الهدايا السري بين $10$ أصدقاء: تُسحب الأسماء عشوائيًا بانتظام. فما [احتمال](https://one-course.com/books/math/2/ar/chapter/9-probability-and-sampling#def-g10-proba-distribution) أن تكون السحبة صحيحة (ألا يسحب أحد نفسه)، وكم إعادة سحب ينبغي للمجموعة أن تتوقع؟ **الجزء الرابع — عُدّ مرتين، واربح مرتين.** 17. مبرهنة المصافحات: في أي حفلة، يعدّ جمع عدد الأيدي التي صافحها كل ضيف كلَّ مصافحة مرتين بالضبط. استنتج أن *عدد الضيوف الذين صافحوا عددًا فرديًا من الأيدي زوجي دائمًا* — وتحقق من معقولية الادعاء في حفلة من ثلاثة ضيوف. 18. برهن على الجوهرة $1^3 + 2^3 + \dots + n^3 = (1 + 2 + \dots + n)^2$ بالتراجع، وتحقق منها من أجل $n = 3$ . (فمجموع غاوس الصغير، مربَّعًا، يعدّ المكعبات.) 19. متطابقة فاندرموند ( [التمرين 27.9](#exo-g12-comb-9) ) عبر المسارات: فسّر $\binom{2n}{n}$ على أنه مسارات شبكية من نمط السؤال 3 من $(0,0)$ إلى $(n,n)$ ، ثم اقطع كل مسار عند عبوره القطر المضاد، وفسّر كيف يظهر $\sum_j \binom nj^2$ . 20. الخاتمة — حركات العدّاد الأربع، سطر واحد لكل حركة مع مثال من هذه المسألة: اضرب المراحل واجمع الحالات؛ ورمّز بذكاء (النجوم والقضبان، وكلمات المسارات)؛ وعُدّ الشيء نفسه مرتين (اللجنة ذات الرئيس، والمصافحات)؛ واطرح غير المرغوب وصحّح ما عُدّ زيادة (التشويشات). ولاحظ أين يذهب العدّ إلى العمل تاليًا: في الاحتمالات، وفي مسارات فصل المصفوفات والبيانات. **حل المسألة 27.1.** **1.** $26^2 \times 10^3 = 676\,000$ لوحة. وأما “اللاما”: فلها $6$ حروف مع ألف ثلاثية ولام ثنائية: $\frac{6!}{3!\,2!} = 60$ جناسًا. **2.** $\binom{32}{5} = 201\,376$ يدًا؛ و $\binom42 \binom{28}{3} = 6 \times 3\,276 = 19\,656$ يدًا فيها آصان بالضبط. **3.** المسار كلمة فيها $4$ حروف R و $3$ حروف U: اختر مواضع U: $\binom73 = 35$. **4.** $(1+x)^4 = 1 + 4x + 6x^2 + 4x^3 + x^4$. وعند $x = 1$: $\sum_k \binom nk = 2^n$؛ وعند $x = -1$: $\sum_k (-1)^k \binom nk = 0$ — أي مجاميع سطور [مثلث باسكال](https://one-course.com/books/math/2/ar/chapter/19-the-binomial-distribution#prop-g11-binom-pascal) ومجاميعها المتناوبة. **5.** اللجان المكوّنة من $k$ شخصًا مع رئيس، من بين $n$: اختر اللجنة ثم رئيسها ($\binom nk \times k$)، أو الرئيس ثم بقية الأعضاء ($n \times \binom{n-1}{k-1}$): فهما متساويان. وبالجمع على $k$: يصير مجموع الطرف الأيمن $n \sum_j \binom{n-1}{j} = n\,2^{n-1}$. **6.** صف من $10$ نجوم و $3$ قضبان يرمّز الطلب (كرات النكهة 1 قبل القضيب الأول، وهكذا)؛ وللصف $13$ رمزًا وهو محدَّد بمواضع القضبان: $\binom{13}{3} = 286$ طلبًا. **7.** $12$ نجمًا و $2$ قضيب: $\binom{14}{2} = 91$. **8.** مع $x', y', z' \geq 0$ و $x' + y' + z' = 9$: $\binom{11}{2} = 55$. **9.** الحد الأحادي $a^i b^j c^k$ حيث $i + j + k = 5$: $\binom72 = 21$. **10.** بالصيغة: $3$ نجوم وقضيب $1$: $\binom41 = 4$؛ وبالسرد: $(3,0)$ و $(2,1)$ و $(1,2)$ و $(0,3)$: فالتوافق حاصل. **11.** دخلت كلمة “متطابقة” عندما أُعلن أن الطلب ليس إلا *أعداد* كل نكهة — فالنجوم لا تحمل أسماء. أما إذا أُكلت الكرات [بالترتيب](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#def-g10-coordgeom-system)، فكل موضع من المواضع $10$ المتمايزة يختار نكهةً بحرية: $4^{10} = 1\,048\,576$ [متتالية](https://one-course.com/books/math/2/ar/chapter/20-sequences#def-g12-seq-sequence) — وهو نموذج مختلف وعالم مختلف ([الطريقة 27.13](#met-g12-comb-model): اسأل دائمًا *أمرتَّب؟ أمتمايز؟ أالتكرار مسموح؟*). **12.** $D_1 = 0$؛ و $D_2 = 1$ (بالتبادل)؛ و $D_3 = 2$ (الدورتان من الرتبة $3$)؛ و $D_4 = 9$. **13.** ينال الضيف 1 القبعة $k \neq 1$: $n - 1$ اختيارًا. فإذا نال الضيف $k$ القبعة 1، شوّش الضيوف $n - 2$ الباقون قبعاتهم: أي $D_{n-2}$ طريقة. وإذا *لم* ينل الضيف $k$ القبعة 1، فأعد تسمية القبعة 1 على أنها القبعة المحرَّمة على الضيف $k$: فيشوّش الضيوف $n - 1$ الباقون: أي $D_{n-1}$ طريقة. ومنه $D_n = (n-1)(D_{n-1} + D_{n-2})$. وللتحقق: $D_4 = 3(2 + 1) = 9$؛ و $D_5 = 4(9 + 2) = 44$. **14.** من التوزيعات $3! = 6$، اطرح تلك التي تثبّت قبعة واحدة على الأقل: فثلاثة منها تثبّت قبعة معينة ($2!$ لكل منها، أي $3 \times 2 = 6$)، وقد عُدّت الأزواج زيادة ($3$ أزواج، $1!$ لكل منها) فيجب أن تعود، ثم يُطرح التطابق من جديد ($1$): $D_3 = 6 - 6 + 3 - 1 = 2$، أي $3!\left(1 - 1 + \frac12 - \frac16\right) = 2$. وبوجه عام $D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$. **15.** $\frac{D_5}{120} = \frac{44}{120} \approx 0.3667$، وهو قريب أصلًا من $\frac1\eu \approx 0.3679$: فالمجموع المتناوب $1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \dots$ يسير نحو $\eu^{-1}$. وتتشوّش قبعات حفلة كبيرة في نحو $36.8\,\%$ من الحالات — وهو ثابت اليانصيب والسكرتيرة، في مشاهدته الثالثة. **16.** $\P(\text{صحيحة}) = \frac{D_{10}}{10!} \approx 0.368$. وتنجح كل إعادة سحب [باحتمال](https://one-course.com/books/math/2/ar/chapter/9-probability-and-sampling#def-g10-proba-distribution) $\approx \frac1\eu$، إذن يكون عدد السحبات المأمول نحو $\eu \approx 2.7$: فخصّص ثلاث تمريرات للقبعات. **17.** كل مصافحة تسهم بالعدد $2$ في مجموع الدرجات، إذن مجموع أعداد مصافحات كل الضيوف زوجي. ومجموع أعداد صحيحة لا يكون زوجيًا إلا إذا كان عدد الحدود [الفردية](https://one-course.com/books/math/2/ar/chapter/11-functions-and-variations#def-g11-func-parity) زوجيًا: فالمصافحون الفرديون يأتون بأعداد [زوجية](https://one-course.com/books/math/2/ar/chapter/11-functions-and-variations#def-g11-func-parity). (وعند ثلاثة ضيوف: لا تحوي ملامح المصافحات الممكنة أبدًا مدخلًا فرديًا واحدًا أو ثلاثة مداخل [فردية](https://one-course.com/books/math/2/ar/chapter/11-functions-and-variations#def-g11-func-parity) — فتحقق من البيانات الأربعة الممكنة.) **18.** $n = 1$: $1 = 1$. وإذا كان $1^3 + \dots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$، فبإضافة $(n+1)^3$: $$ \frac{n^2(n+1)^2}{4} + (n+1)^3 = \frac{(n+1)^2\left(n^2 + 4n + 4\right)}{4} = \left(\frac{(n+1)(n+2)}{2}\right)^{\!2} : $$ وهي الوراثة. ومن أجل $n = 3$: $1 + 8 + 27 = 36 = 6^2$. **19.** المسار إلى $(n, n)$ يقطع $2n$ خطوة ويعبر القطر المضاد $x + y = n$ عند نقطة شبكية واحدة بالضبط $(j, n - j)$؛ والنصف الأول مسار فيه $j$ حرف R من بين $n$ خطوة ($\binom nj$ اختيارًا)، والنصف الثاني، مقروءًا بالمقلوب، كذلك ($\binom nj$ مرة أخرى، بالتناظر). وبالجمع على نقطة العبور: $\binom{2n}{n} = \sum_j \binom nj^2$ — أي متطابقة فاندرموند، مرسومةً. **20.** اضرب المراحل واجمع الحالات: لوحات التسجيل وأيدي البوكر. ورمّز: المسارات كلمات بالحرفين R و U، والطلبات نجوم وقضبان. وعُدّ مرتين: اللجنة ذات الرئيس، والمصافحات، والمسارات المقطوعة في [المنتصف](https://one-course.com/books/math/2/ar/chapter/5-coordinate-geometry#prop-g10-coordgeom-midpoint). واطرح وصحّح: القبعات المشوَّشة، وبقيتها $\frac1\eu$. والمحطات التالية: هذه الأعداد تحت كسور [الاحتمال](https://one-course.com/books/math/2/ar/chapter/9-probability-and-sampling#def-g10-proba-distribution)، وقوى عدّ المسارات في مصفوفات الجوار بعد فصلين.