الترتيب والتوافيق الثانية باك ع.ر

الخطوة 1 — التعريف والحالات الخاصة.

لـ $n\ge 0$ و $0\le k\le n$، نُعرّف $$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}.$$يمثّل هذا العدد عدد المجموعات الجزئية ذات المقدار $k$ من مجموعة تضم $n$ عنصرًا.

لدينا:

• $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=\frac{0!}{0!\cdot 0!}=\frac{1}{1\cdot 1}=1$.
• $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\frac{n!}{0!\cdot n!}=1$ لكل $n\ge 0$.
• $\left(\genfrac{}{}{0ex}{}{n}{n}\right)=\frac{n!}{n!\cdot 0!}=1$ لكل $n\ge 0$.

هذه الحالات الحدّية متسقة: توجد بالضبط $1$ طريقة لاختيار $0$ عنصر (المجموعة الخالية) و$1$ طريقة لاختيار جميع العناصر الـ$n$.

الخطوة 2 — برهان متطابقة باسكال (برهان جبري مُقدَّم على أنه مكتمل).

نريد إثبات أن $\left(\genfrac{}{}{0ex}{}{n}{k}\right)+\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$ لـ $0\le k\le n-1$.

حساب جبري:

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)+\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)=\frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}.$$

نوحّد المقام إلى $(k+1)!(n-k)!$:

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

ومن ثم $\frac{n!(n+1)}{(k+1)!(n-k)!}=\frac{(n+1)!}{(k+1)!(n-k)!}=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$.

البرهان إذن مكتمل لكل $0\le k\le n-1$. الحالتان $k=0$ و $k=n-1$ مشمولتان في هذا الحساب العام، الذي لا يعرف أي حالة عدم تحديد بما أن $0\le k\le n-1$ يضمن $k+1\ge 1$ و $n-k\ge 1$. يشكّل هذا البرهان الجبري برهانًا كاملًا وكافيًا لمتطابقة باسكال.

الخطوة 3 — متطابقة عصا الهوكي بالترجع على $r=n-k$.

نُثبّت $k\ge 0$ ونُبيّن بالترجع على $n\ge k$ أن $\sum _{j=k}^n\left(\genfrac{}{}{0ex}{}{j}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$.

التأسيس ($n=k$): الطرف الأيسر يساوي $\left(\genfrac{}{}{0ex}{}{k}{k}\right)=1$، والطرف الأيمن يساوي $\left(\genfrac{}{}{0ex}{}{k+1}{k+1}\right)=1$. المساواة محقّقة.

الوراثة: نفترض $\sum _{j=k}^n\left(\genfrac{}{}{0ex}{}{j}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)$ لقيمة معيّنة $n\ge k$. حينئذ:

$$\sum _{j=k}^{n+1}\left(\genfrac{}{}{0ex}{}{j}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)+\left(\genfrac{}{}{0ex}{}{n+1}{k}\right)\cdot \frac{k+1}{k+1}.$$

انتباه: الحد الأخير هو ببساطة $\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right)+\left(\genfrac{}{}{0ex}{}{n+1}{k}\right)$. بمتطابقة باسكال (الخطوة 2)، يساوي هذا $\left(\genfrac{}{}{0ex}{}{n+2}{k+1}\right)$.

الترجع ثابت إذن. لدينا إذن، لكل $n\ge k\ge 0$:

$$\sum _{j=k}^n\left(\genfrac{}{}{0ex}{}{j}{k}\right)=\left(\genfrac{}{}{0ex}{}{n+1}{k+1}\right).$$

الخطوة 4 — لجنة من 4 أساتذة مع رئيس من بين 10.

الطريقة 1 (اللجنة ثم الرئيس): نختار أولًا $4$ أساتذة من بين $10$: $\left(\genfrac{}{}{0ex}{}{10}{4}\right)=210$ طريقة. ثم نختار $1$ رئيسًا من بين الـ$4$: $4$ طرق. المجموع: $210\times 4=840$.

الطريقة 2 (الرئيس ثم اللجنة): نختار أولًا الرئيس من بين الأساتذة الـ$10$: $10$ طرق. ثم نختار الأعضاء الثلاثة الآخرين للجنة من بين الـ$9$ المتبقين: $\left(\genfrac{}{}{0ex}{}{9}{3}\right)=84$ طريقة. المجموع: $10\times 84=840$.

تُعطي الطريقتان $840$، مما يؤكد الاتساق. يمكننا أيضًا كتابة هذه المساواة على الشكل $$4\left(\genfrac{}{}{0ex}{}{10}{4}\right)=10\left(\genfrac{}{}{0ex}{}{9}{3}\right),$$ وهي حالة خاصة من المتطابقة $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$.

الخطوة 5 — حساب $S_n=\sum _{k=0}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

الحد $k=0$ منعدم. لـ $k\ge 1$، نستعمل المتطابقة $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$:

$$S_n=\sum _{k=1}^{n}k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\sum _{k=1}^{n}n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)=n\sum _{k=1}^n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right).$$

نُجري تغيير المتغيّر $j=k-1$ (عندما يتراوح $k$ من $1$ إلى $n$، يتراوح $j$ من $0$ إلى $n-1$):

$$S_n=n\sum _{j=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{j}\right).$$

بصيغة ذات الحدين لنيوتن المطبّقة على $(1+1{)}^{n-1}$:

$$\sum _{j=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{j}\right)=2^{n-1}.$$

نستنتج: $$\boxed{S_n=n\cdot 2^{n-1}}.$$