التوافقيات الأولية وصيغة ذات الحدين لنيوتن

مبادئ العدّ

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

عدّ عناصر مجموعة هو ترقيمها: أي أن نُسند إلى كل عدد من $1$ إلى $n$ عنصرًا، دون تكرار أي عنصر ودون إغفال أي عنصر. نقول إن مجموعة $A$ لها $n$ عنصرًا، حيث $n$ عدد طبيعي، إذا وُجد تقابل من المجموعة $\{1, 2, \ldots, n\}$ إلى $A$، أي دالة ترسل الأعداد المختلفة إلى عناصر مختلفة وتبلغ جميع عناصر $A$؛ والمجموعة الخالية لها $0$ عنصرًا، وتكون المجموعة منتهية إذا كانت خالية أو كان لها $n$ عنصرًا من أجل عدد طبيعي ما $n$. وتُدرَس التقابلات وتركيبها وعكسها في الدرس الخاص بـالمجموعات والعلاقات والدوال.

حقيقة مقبولة دون برهان (عدد العناصر). نقبل دون برهان أن عدد عناصر مجموعة منتهية معرَّف تعريفًا جيدًا: لا يمكن لمجموعة أن يكون لها في آن واحد $m$ عنصرًا و$n$ عنصرًا إذا كان $m \neq n$. ونقبل أيضًا أن كل مجموعة جزئية من مجموعة منتهية منتهية.

تُبرهَن الحقيقتان كلتاهما بالاستقراء على $n$؛ والأولى هي في جوهرها مبدأ برج الحمام، الذي ينص على أنه لا توجد دالة ترسل الأعداد $n + 1$ من $\{1, \ldots, n + 1\}$ إلى أعداد مختلفة من $\{1, \ldots, n\}$. وبراهينهما طويلة ولا تقدّم أفكارًا تُستعمل فيما بعد، ولذلك نقبلهما. ودون الأولى لن يكون للعبارة «عدد العناصر» معنى، ولن يستطيع برهان توفيقي، يعدّ المجموعة نفسها بطريقتين، أن يستنتج أن النتيجتين متساويتان.

بالاستقراء على عدد الأجزاء، يمتد المبدأ إلى أي عدد منتهٍ من المجموعات المنفصلة مثنى مثنى: اتحاد $A_1, \ldots, A_r$، التي أعداد عناصرها $n_1, \ldots, n_r$، له $n_1 + \cdots + n_r$ عنصرًا، لأن اتحاد المجموعات $r + 1$ الأولى هو اتحاد المجموعات $r$ الأولى مع الأخيرة، التي ليس لها معها عناصر مشتركة. ومنه يُستنتج المبدأ الثاني، الذي يعدّ الاختيارات التي تُجرى على مراحل.

وبالطريقة نفسها، بالاستقراء على عدد المراحل، يمتد مبدأ الضرب إلى أي عدد منتهٍ منها: فالاختيار على $r$ مرحلة، يمكن إجراؤها بـ$n_1, n_2, \ldots, n_r$ طريقة على الترتيب، يمكن إجراؤه بـ$n_1 n_2 \cdots n_r$ طريقة. فمثلًا، في النظام العشري المدروس في الدرس الخاص بـأنظمة العدّ الموضعية يوجد $9 \cdot 10 \cdot 10 = 900$ عددًا من ثلاثة أرقام، لأن الرقم الأول لا يمكن أن يكون $0$ والرقمين الآخرين حرّان. وتجدر الإشارة إلى أن مبدأ الضرب يشترط ألّا يتوقف عدد الخيارات في كل مرحلة على ما اختير قبلها، وإن توقفت عليه الخيارات نفسها؛ فإذا لم يتحقق هذا الشرط، نفصل حالات يتحقق فيها ونجمع نتائجها بمبدأ الجمع.

تُمثَّل المراحل المتتابعة لاختيار بـالمخطط الشجري: من نقطة ابتدائية، هي الجذر، تخرج فروع بعدد خيارات المرحلة الأولى؛ ومن طرف كل فرع فروع بعدد خيارات المرحلة الثانية، وهكذا. وكل مسار من الجذر إلى طرف نهائي، أو ورقة، هو اختيار كامل، ومبدأ الضرب يعدّ الأوراق دون رسمها.