برهان تقابلي

الموسوعة الحرة

في علم التوافيق ، يُعدّ البرهان التقابلي أسلوبًا لإثبات أن مجموعتين تحتويان على عدد متساوٍ من العناصر، أو أن المجموعات في فئتين توافيقيتين متساوية في الحجم، وذلك بإيجاد دالة تقابلية تربط إحدى المجموعتين بالأخرى ارتباطًا مباشرًا . يُمكن الاستفادة من هذا الأسلوب في إيجاد صيغة لحساب عدد عناصر مجموعات معينة، من خلال ربطها بمجموعات أخرى يسهل عدّها. إضافةً إلى ذلك، غالبًا ما تُقدّم طبيعة التقابل نفسها رؤى قيّمة حول كلٍّ من المجموعتين أو كلتيهما.

أمثلة أساسية

إثبات تناظر معاملات ذات الحدين

ينص تناظر معاملات ذات الحدين على أن

(نك)=(نن-ك).{\displaystyle {n \choose k}={n \choose nk}.}

هذا يعني أن هناك بالضبط عدد من تركيبات k من الأشياء في مجموعة بحجم n يساوي عدد تركيبات n − k   من الأشياء في مجموعة بحجم n . 

يمكن فهم الفكرة الرئيسية للبرهان التقابلي من خلال مثال بسيط: اختيار k طفلاً ليتم مكافأتهم بأقماع الآيس كريم، من بين مجموعة من n طفلاً، له نفس التأثير تمامًا مثل اختيار n − k   طفلاً بدلاً من ذلك ليتم حرمانهم من أقماع الآيس كريم.

أمثلة أخرى

لا تقتصر المسائل التي تقبل البراهين التقابلية على متطابقات معاملات ذات الحدين. فكلما ازدادت المسألة تعقيدًا، أصبح البرهان التقابلي بالغ التعقيد. وتُعد هذه التقنية مفيدة بشكل خاص في مجالات الرياضيات المتقطعة ، مثل التوافقية ونظرية المخططات ونظرية الأعداد .

تتضمن الأمثلة الكلاسيكية الأكثر شيوعًا للبراهين التقابلية في علم التوافق ما يلي:

انظر أيضاً

مراجع

للمزيد من القراءة