البرهان التوافقي

Combinatorial Proof

تستخدم طريقة البرهان التوافقي في اثبات المتطابقات التوافقية وآليته تعتمد على الحساب المزدوج لشيء ما بطريقتين مختلفتين كل واحدة تعطينا صيغة حسابية معينة ونظرا لأنهما تتعلقان بحساب شيء واحد فكلا الصيغتين الناتجتين متساويتين. من الناحية العملية لاستخدام البرهان التوافقي يتعين عليك اختيار مجموعة X مناسبة ثم مسألة عد عليها مناسبة أيضا بحيث عندما نحلها بطريقتين نحصل على تلك الصيغ الموجودة في المتطابقة المراد إثباتها.

على سبيل المثال في قانون باسكال

$\left( \begin{array}{c} n - 1 \\ r - 1 \\ \end{array} \right) + \left( \begin{array}{c} n - 1 \\ r \\ \end{array} \right) = \left( \begin{array}{c} n \\ r \\ \end{array} \right)$

(والذي يمكن اثباته بطريقة كلاسيكية أيضا), خذ المجموعة X المكونة من n عنصرا. قسم هذه المجموعة إلى مجموعتين Y وفيها $n - 1$ عنصرا والمجموعة Z وفيها عنصر واحد سمه u. الآن نعدد المجموعات الجزئية من X والتي في كل واحدة r عنصرا بطريقتين.

الطريقة الأولى أن عدد هذه المجموعات الجزئية هو بالضبط التوافيق المأخوذة راء راء من هذه المجموعة , أي $\left( \begin{array}{c} n \\ r \\ \end{array} \right)$ .

الطريقة الثانية هي تقسيم هذه المجموعات إلى قسمين:

مجموعات ليس فيها العنصر u وهذه بالضبط هي التوافيق المأخوذة راء راء من المجموعة Y وعددها $\left( \begin{array}{c} n - 1 \\ r \\ \end{array} \right)$ , ومجموعات فيها العنصر u وهي بالضبط تلك المجموعات الجزئية من Y ذات $r - 1$ عنصرا مضافا إليها العنصر u وعدد هذه المجموعات قبل الإضافة هو $\left( \begin{array}{c} n - 1 \\ r - 1 \\ \end{array} \right)$
إذا

$\left( \begin{array}{c} n - 1 \\ r - 1 \\ \end{array} \right) + \left( \begin{array}{c} n - 1 \\ r \\ \end{array} \right) = \left( \begin{array}{c} n \\ r \\ \end{array} \right)$ .

لاحظ كيف أن هذا البرهان أسهل بشكل واضح من البرهان الجبري المعروف لهذه المتطابقة ولكن هذة ليست صفة دائمة في البراهين الوافقية كما ييتضح من التدريب التالي.

تدريب: قدم برهان توافقي على المتطابقة المعروفة $\left( \begin{array}{l} n \\ k \\ \end{array} \right) = \left( \begin{array}{c} n \\ n - k \\ \end{array} \right)$ .

مسائل 1:

1) قدم برهان توافقي على أن $P(n,k) = P(n,k - 1) + kP(n - 1,k - 1)$ .

2) قدم برهان توافقي على أن $\left( \begin{array}{l} n \\ r \\ \end{array} \right) = \frac{n}{r}\left( \begin{array}{c} n - 1 \\ r - 1 \\ \end{array} \right)$ .

3) قدم برهان توافقي على الصورة الأعم $\left( \begin{array}{l} n \\ r \\ \end{array} \right)\left( \begin{array}{l} r \\ k \\ \end{array} \right) = \left( \begin{array}{c} n \\ k \\ \end{array} \right)\left( \begin{array}{c} n - k \\ r - k \\ \end{array} \right)$ .