التوافيقيات
كم مجموعة مختلفة من خمس أوراق يمكن أن نختار من رزمة فيها 32 ورقة؟ وهذا هو نوع المسائل الذي تعالجه التوافيقيات (combinatorics). وفيها قاعدتان أساسيتان للعد: مبدأ الجمع ومبدأ الضرب. أما سائر الطرق فليست إلا توسيعاً لهذين المبدأين.
مبدأ الجمع
مبدأ الجمع بسيط جداً، وهو ينص على ما يلي: إذا كانت لدينا مجموعتان A, B ليس بينهما أي عنصر مشترك، فإنّ عدد الطرق الممكنة لاختيار عنصر واحد من الاتحاد A ∪ B يساوي |A| + |B|، أي مجموع عددَي عناصر المجموعتين.
لنبدأ بمثال سهل. لدينا 6 كرات حمراء و 8 كرات زرقاء، ونضع هذه الكرات كلها في صندوق سحب واحد. كم إمكانية لدينا إذا سحبنا كرة واحدة؟ كانت لدينا في البداية مجموعة الكرات الحمراء، ولنرمز لها بالحرف A، ثم مجموعة الكرات الزرقاء، ولنرمز لها بالحرف B. هاتان المجموعتان منفصلتان، أي لا توجد كرة تنتمي إلى كلتيهما. ونريد أن نسحب كرة واحدة، فيكون لدينا إجمالاً |A| + |B| = 6 + 8 = 14 إمكانية. وهذا كل شيء.
مبدأ العد الأساسي (قاعدة الضرب)
لدينا مرة أخرى مجموعتان، Z و M. تحتوي المجموعة Z على ثلاث نساء، وتحتوي المجموعة M على أربعة رجال. والسؤال الآن: كم زوجاً مختلفاً من النوع رجل–امرأة يمكن أن نكوّن من هاتين المجموعتين؟ الفكرة أننا نأخذ في كل مرة امرأة واحدة ونقرن بها رجلاً ما. ونحسب عدد الأزواج كلها كما يلي: نأخذ امرأة واحدة، ولتكن فاطمة، ونقرن بها الرجال واحداً بعد الآخر. فنحصل على 4 أزواج مختلفة، لأنّ عدد الرجال الذين يمكن أن نقرنهم بها 4. ونفعل الشيء نفسه مع المرأتين الأخريين، فتكوّن كل منهما 4 أزواج أخرى. وهذا كل شيء، فلدينا إجمالاً 4 + 4 + 4 = 12 زوجاً.
فماذا فعلنا في الحقيقة؟ ضربنا عدد عناصر المجموعة الأولى في عدد عناصر المجموعة الثانية. كانت لدينا 3 نساء و 4 رجال، فيكون العدد الكلي للأزواج 3 × 4 = 12. ومن هنا جاء اسم قاعدة الضرب. فإذا كانت لدينا مجموعتان نكوّن منهما أزواجاً، فإننا نضرب ببساطة عدد عناصر إحداهما في عدد عناصر الأخرى.
ويمكننا أن نتحقق من صحة ذلك فيما يلي. هذه هي كل الأزواج التي يمكن أن نكوّنها من 3 نساء و 4 رجال. يمثل كل صف الإمكانيات المتاحة لإحدى النساء، ويمثل كل عمود الإمكانيات المتاحة لأحد الرجال. فلدينا ثلاثة صفوف وأربعة أعمدة، أي إن عدد الإمكانيات يساوي عدد الصفوف مضروباً في عدد الأعمدة.
أمثلة محلولة
- كم عدداً مختلفاً مكوّناً من رقمين يوجد؟ كيف يبدو العدد المكوّن من رقمين؟ في الخانة الأولى يقع أحد الأرقام 1, …, 9، أما في الخانة الثانية فقد يقع الصفر أيضاً: 0, …, 9. ففي المجموعة الأولى 9 أرقام، وفي الثانية 10 أرقام. نطبق قاعدة الضرب فنحصل على النتيجة النهائية: 9 × 10 = 90.
- كم عدداً مختلفاً مكوّناً من ثلاثة أرقام يوجد، بشرط ألا يتكرر فيه أي رقم؟ في الخانة الأولى يمكن أن يقع أحد تسعة أرقام، لأنّ العدد لا يمكن أن يبدأ بالصفر. وفي الخانة الثانية يمكن أن تقع كل الأرقام بما فيها الصفر، ما عدا الرقم الواقع في الخانة الأولى، فنطرح 1 من عدد الأرقام العشرة الممكنة. (فإذا بدأ العدد مثلاً بالرقم 4، فمن الواضح أنّ الرقم 4 لا يمكن أن يقع في الخانة الثانية، وإلا تكرر في العدد مرتين.) وفي الخانة الثالثة يمكن أن تقع كل الأرقام أيضاً، ما عدا الرقمين الواقعين في الخانتين الأولى والثانية، للسبب نفسه. فإذا كان الرقم 4 في الخانة الأولى والرقم 7 في الثانية، أمكننا أن نضع في الخانة الثالثة أحد الأرقام من المجموعة {0, …, 9} ∖ {4, 7}. إذن نطرح 2 من عدد الأرقام العشرة. ويبقى أن نضرب: 9 × 9 × 8 = 648. إذن يوجد 648 عدداً من هذا النوع.
- نرمي حجر نرد عادياً مرتين متتاليتين. كم نتيجة مختلفة يمكن أن نحصل عليها؟ في الرمية الأولى يمكن أن تظهر 6 نتائج مختلفة، وكذلك في الرمية الثانية، فيكون العدد الكلي للإمكانيات 6 × 6 = 36.
- نرمي حجر النرد مرتين متتاليتين. كم نتيجة مختلفة يمكن أن نحصل عليها إذا ظهر في الرمية الأولى عدد زوجي؟ في الرمية الأولى ظهر عدد زوجي، أي ظهر أحد الأعداد 2, 4, 6، وهي 3 إمكانيات. وفي الرمية الثانية يمكن أن يظهر أي عدد، فيكون لدينا إجمالاً 3 × 6 = 18 إمكانية.
المحتويات: التوافيقيات, التباديل (الترتيب دون تكرار), تباديل جميع العناصر, التوافيق, الترتيب مع التكرار, التوافيق مع التكرار, عدد رموز PIN الممكنة