✖

التوافيق

نستخدم التوافيق (combinations) عندما نختار عدداً معيناً من العناصر من مجموعة ما، ولا يكون ترتيب اختيار هذه العناصر مهماً. ومن المسائل النموذجية سحب 6 أرقام من 49: في صندوق السحب 49 رقماً نسحب منها 6 أرقام، ولا يهمّ الترتيب الذي نسحبها به.

استنتاج القانون

عجلة دوّارة

لتكن لدينا مجموعة M، مثلاً M = {a, b, c, d, e}. التوفيق المكوّن من k من العناصر هو مجموعة جزئية K ⊆ M تحتوي على k من العناصر. وبما أنّ K مجموعة، فمن الطبيعي ألا يهمّ الترتيب. فمن التوافيق الثلاثية من المجموعة M مثلاً {a, b, d} أو {b, c, d}.

والفرق بينها وبين التباديل أنّ الترتيب في التباديل مهم، فالثلاثيتان (a, b, e) و (e, b, a) تبديلان مختلفان، لكنهما توفيق واحد، لأنّ (a, b, e) و (e, b, a) تحتويان على العناصر نفسها؛ أما اختلاف ترتيبها فلا يعنينا في التوافيق.

لكن يمكننا أن نستفيد من التباديل للحصول على قانون عدد التوافيق المختلفة كلها. نعلم أنّ عدد تباديل n من العناصر مأخوذة k في كل مرة هو

nPk=n!(n−k)!.

فإذا حسبنا عدد التباديل الثلاثية من المجموعة السابقة M = {a, b, c, d, e}، حصلنا على 5P3 = 60 تبديلاً مختلفاً. غير أنّ هذا العدد يتضمن لكل ثلاثية كل تباديلها. أي يتضمن الثلاثية abc، ويتضمن أيضاً الثلاثيات acb, bac, bca, cab و cba. هذه ستة تباديل مختلفة، لكنها توفيق واحد، لأنّ عناصرها هي نفسها.

فإذا كانت لدينا ثلاثية ما، فكم تبديلاً مختلفاً لها يوجد؟ يوجد 3! تبديلاً. وبعبارة أخرى، عدد التباديل الثلاثية يساوي عدد التوافيق الثلاثية مضروباً في 3!. فبدلاً من أن نعدّ التوفيق الواحد مرة واحدة، نعدّه 3! مرات، مرة لكل تبديل من تباديل الثلاثية. ولذلك إذا قسمنا عدد التباديل على 3!، حصلنا على عدد التوافيق.

ويمكننا أن نعمّم هذه الطريقة فنقول: إذا بحثنا عن عدد التوافيق المختلفة المكوّنة من k من العناصر من مجموعة فيها n من العناصر، ورمزنا لهذا العدد بالرمز nCk، فإنّه يساوي

nCk=nPkk!,

أي عدد التباديل مقسوماً على k!، وهو عدد تباديل كل مجموعة من k من العناصر. ونبسّط القانون بكتابة قانون التباديل بالتفصيل:

nCk=nPkk!=n!(n−k)!⋅1k!=n!(n−k)!⋅k!.

مثال: عدد التوافيق الثنائية من المجموعة {a, b, c} هو

3C2=3!1!×2!=3

وهذه التوافيق هي: {a, b}, {a, c} و {b, c}. أما التوافيق الثلاثية من المجموعة الأولى M = {a, b, c, d, e} فعددها

5C3=5!(5−3)!×3!=10

وهذه التوافيق هي: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

معامل ذات الحدين

إلى جانب الرمز nCk يُستخدم كثيراً رمز آخر يُسمّى معامل ذات الحدين (binomial coefficient)، وصورته

(nk)

وهو يشبه كسراً بلا خط كسر (وإن كان كثير من الطلاب يرسمونه بحكم العادة)، لكن بين قوسين (والقوسان ليسا اختياريين، بل يجب كتابتهما). ونقرؤه: «توافيق n مأخوذة k» (أو «n فوق k»)، وقيمته هي نفسها قيمة nCk.

(nk)=n!(n−k)!⋅k!

فإذا كانت لدينا مجموعة فيها 5 عناصر، واخترنا منها رباعيات، فإنّ عددها الكلي هو

(54)=5!1!×4!=5.

العلاقات الأساسية

لمعامل ذات الحدين ولكل n ∈ ℕ لدينا:

(n0)=(nn)=(00)=1(n1)=n

ولكل n, k ∈ ℕ0 (أي الأعداد الطبيعية مع الصفر) حيث k ≤ n يتحقق

(nn−k)=(nk).

ولكل n, k ∈ ℕ0 حيث k < n يتحقق

(nk)+(nk+1)=(n+1k+1).

الحاسبة

تحسب الحاسبة الآتية معامل ذات الحدين لقيمتين معطاتين n و k.

عدد توافيق 6 من العناصر مأخوذة 3 في كل مرة هو 20.

أمثلة محلولة

  1. لنبدأ بالسحب الذي ذكرناه: نسحب 6 كرات من صندوق فيه 49 كرة مرقّمة. كم نتيجة مختلفة يمكن أن يعطي السحب؟

    أولاً: هل ترتيب سحب الأرقام مهم؟ لا، فما يهمّ هو الأرقام وحدها لا ترتيبها. إذن نستخدم التوافيق. لدينا 49 كرة، ونسحب 6 كرات، فنحصل على معامل ذات الحدين

    (496)=49!(49−6)!×6!=49!43!×6!=13,983,816

    إذن يمكن أن يعطي السحب 13,983,816 نتيجة مختلفة. ومن ذلك نجد أنّ احتمال تخمين الأرقام الستة كلها بتخمين واحد هو 1/13,983,816، أي 0.00000715112%.

  2. في نادي الرياضيات 13 طالباً، ويريد المعلم أن يختار منهم 4 طلاب يمثّلون النادي في مسابقة. كم رباعية مختلفة يمكن أن يختار منها المعلم؟

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

    (134)=715.

  3. لدينا مجموعة من خمسين شخصاً، نصفهم رجال ونصفهم نساء. كم ثلاثية مختلفة من الأشخاص توجد، إذا كان لا يجوز أن تتكون الثلاثية من جنس واحد فقط (أي لا يجوز أن تضم ثلاثة رجال أو ثلاث نساء)؟

    هذه مسألة توافيق أصعب قليلاً. إذا استبعدنا الثلاثيات المكوّنة من جنس واحد، بقيت طريقتان فقط لتكوين الثلاثية: رجلان وامرأة، أو رجل وامرأتان. وعدد توافيق المجموعة الأولى (رجلان وامرأة) يساوي عدد توافيق المجموعة الثانية. فيكفي أن نحسب عدد توافيق المجموعة الأولى ثم نضربه في 2. والباقي سهل: نحدد عدد الأزواج المختلفة من الرجال، وهو خمسة وعشرون فوق اثنين، ونضربه في عدد طرق اختيار امرأة واحدة (وهو خمسة وعشرون، كما في العلاقات الأساسية أعلاه، في السطر الثاني تحديداً). ثم نضرب هذه النتيجة في 2، فنحصل على النتيجة النهائية.

    2×(252)×(251)=15000.

  4. في صندوق 15 منتجاً، منها 4 منتجات معيبة. بكم طريقة يمكن أن نختار 6 منتجات بحيث

    • لا يكون أي منها معيباً؟ نختار في هذه الحالة 6 منتجات من 15 − 4 = 11 منتجاً سليماً. فنحصل على معامل ذات الحدين

      (116)=462.

    • يكون منتج واحد فقط معيباً؟ نختار إذن مجموعة فيها 5 منتجات سليمة ومنتج واحد معيب. لدينا 11 منتجاً سليماً و 4 منتجات معيبة. نطبق قاعدة الضرب فنحصل على النتيجة:

      (115)×(41)=1848

    • يكون منتج واحد على الأكثر معيباً؟ نستفيد في الحل من النتيجتين السابقتين. نعلم أنّ لدينا 462 طريقة لاختيار 6 منتجات سليمة، و 1848 طريقة لاختيار خمسة منتجات سليمة ومنتج واحد معيب. نطبق إذن مبدأ الجمع، فنجمع النتيجتين ونحصل على المطلوب، أي منتج معيب واحد على الأكثر (= لا يوجد منتج معيب، أو يوجد منتج معيب واحد). فتكون النتيجة: 462 + 1848 = 2310.

المحتويات: التوافيقيات, التباديل (الترتيب دون تكرار), تباديل جميع العناصر, التوافيق, الترتيب مع التكرار, التوافيق مع التكرار, عدد رموز PIN الممكنة