المبادئ التوافقية

في إثبات النتائج في علم التوافيق، يتم التعرف على العديد من القواعد التوافقية المفيدة أو المبادئ التوافقية واستخدامها بشكل شائع.

تُستخدم قاعدة الجمع، وقاعدة الضرب، ومبدأ الإدراج والاستبعاد غالبًا لأغراض التعداد . وتُستخدم البراهين التقابلية لإثبات أن مجموعتين لهما نفس عدد العناصر . أما مبدأ خانة الحمام، فيُستخدم غالبًا للتحقق من وجود شيء ما، أو لتحديد الحد الأدنى أو الأقصى لعدد شيء ما في سياق منفصل .

تنشأ العديد من المتطابقات التوافقية من طرق العد المزدوج أو طريقة العنصر المميز . تُعد الدوال المولدة وعلاقات التكرار أدوات قوية يمكن استخدامها لمعالجة المتتاليات، ويمكنها وصف العديد من المواقف التوافقية، إن لم يكن حلها.

قاعدة المجموع هي مبدأ بديهي ينص على أنه إذا كان هناك a نتيجة محتملة لحدث ما (أو طرق للقيام بشيء ما)، و b نتيجة محتملة لحدث آخر (أو طرق للقيام بشيء آخر)، ولا يمكن أن يقع الحدثان معًا (أو لا يمكن القيام بالشيئين معًا)، فإن إجمالي النتائج المحتملة للحدثين (أو إجمالي الطرق الممكنة للقيام بأحدهما) هو a + b . وبصورة أدق، فإن مجموع حجمي مجموعتين منفصلتين يساوي حجم اتحادهما.

قاعدة الضرب هي مبدأ بديهي آخر ينص على أنه إذا كانت هناك طريقة للقيام بشيء ما و b طريقة للقيام بشيء آخر، فإن هناك a  · b طريقة للقيام بكلا الأمرين. 

يربط مبدأ الإدراج والاستبعاد بين حجم اتحاد عدة مجموعات، وحجم كل مجموعة، وحجم كل تقاطع ممكن بين هذه المجموعات. وأصغر مثال على ذلك هو عندما تكون هناك مجموعتان: عدد العناصر في اتحاد A و B يساوي مجموع عدد العناصر في A و B مطروحًا منه عدد العناصر في تقاطعهما.

بشكل عام، وفقًا لهذا المبدأ، إذا كانت _A1 ، ...، An مجموعات منتهية، _فإن

$\displaystyle \begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}$

تنص قاعدة القسمة على أن هناك n/d طريقة لإنجاز مهمة ما إذا كان من الممكن القيام بها باستخدام إجراء يمكن تنفيذه في n طريقة، ولكل طريقة w ، فإن d من الطرق n تتوافق مع الطريقة w .

تثبت البراهين التقابلية أن مجموعتين لهما نفس عدد العناصر من خلال إيجاد دالة تقابلية (تناظر واحد لواحد) من مجموعة إلى أخرى.

العد المزدوج هو أسلوب يقوم بمساواة تعبيرين لحساب حجم مجموعة بطريقتين.

ينص مبدأ خانة الحمام على أنه إذا وُضِعَ كل عنصر من العناصر (أ) في خانة واحدة من الخانات (ب) ، حيث (أ) > (ب) ، فإن إحدى الخانات تحتوي على أكثر من عنصر واحد. وباستخدام هذا المبدأ، يمكن، على سبيل المثال، إثبات وجود عنصر ما في مجموعة ما بخصائص محددة.

تقوم طريقة العنصر المميز بتحديد "عنصر مميز" من مجموعة ما لإثبات نتيجة معينة.

الدوال المولدة هي متسلسلات قوى رسمية، معاملاتُها تُطابق حدودَ متتاليةٍ مُعطاة. هذا التمثيل الجديد للمتتالية يفتح آفاقًا جديدةً لإيجاد المتطابقات والصيغ المغلقة المتعلقة بمتتالياتٍ مُعينة. الدالة المولدة (العادية) للمتتالية a _n هي

${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}$

تُعرّف العلاقة التكرارية كل حد من حدود المتتالية بدلالة الحدود السابقة له. قد تُفضي العلاقات التكرارية إلى خصائص غير معروفة سابقًا للمتتالية، ولكن عمومًا، يُفضّل استخدام صيغ مغلقة لحدود المتتالية.

• فان لينت، جيه إتش ؛ ويلسون، آر إم (2001). دورة في التوافقية (الطبعة الثانية  ). مطبعة جامعة كامبريدج. ISBN 0-521-00601-5.