✖

التوافيق مع التكرار

التوافيق مع التكرار (combinations with repetition) تشبه التوافيق العادية، إلا أننا نسمح بتكرار عناصر المجموعة الأساسية M.

التعريف والقانون

لنبدأ بمثال لطيف: يذهب خالد إلى المتجر ليشتري اثنتي عشرة زجاجة عصير لرحلة. وفي الرف أربعة أنواع مختلفة من العصير. أمامه إمكانيات كثيرة لشراء الزجاجات: يمكن مثلاً أن يشتري 5 زجاجات برتقال، وزجاجتي تفاح، وزجاجة مانجو واحدة، و 4 زجاجات جوافة، أو أن يشتري ثلاث زجاجات من كل نوع. كم طريقة مختلفة توجد لشراء الزجاجات بحيث يكون عددها اثنتي عشرة زجاجة؟

لدينا إذن المجموعة الأساسية M = {برتقال, تفاح, مانجو, جوافة}، والسؤال: كم مجموعة مكوّنة من k من العناصر (حيث k = 12) توجد، عناصرها من المجموعة M ولا يهمّ فيها الترتيب؟

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

111⏟برتقال0111⏟تفاح011111⏟مانجو01⏟جوافة

ولو أردنا أن نشتري 6 زجاجات برتقال، و 4 زجاجات تفاح، وزجاجتي جوافة، ولا شيء من المانجو، لكانت المتتالية على النحو الآتي:

111111⏟برتقال01111⏟تفاح0011⏟جوافة

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

ويكفي أن نحسب مواقع الأصفار: فعندما نوزّع 3 أصفار بين 12 واحداً، نحصل على مجموعة صالحة من الزجاجات. وبعبارة أخرى: لدينا 15 خانة، ويجب أن نشغل 3 منها بأصفار، أما الخانات الباقية فتُشغل تلقائياً بآحاد.

وهذه مسألة بسيطة على التوافيق دون تكرار. نرقّم الخانات الخمس عشرة بالأعداد {1, …, 15}، ثم نختار من هذه المجموعة ثلاثيات من الأعداد، فنحصل على ثلاثة مواقع نضع فيها الأصفار. فالتوفيق {2, 4, 7} مثلاً يعطينا المتتالية 101011011111111: في الخانات الثانية والرابعة والسابعة صفر، والباقي آحاد. إذن يوجد

(153)=455

طريقة مختلفة لتوزيع الأصفار على 15 خانة، ومن ثمّ 455 طريقة مختلفة لشراء 12 زجاجة عصير إذا كانت لدينا أربعة أنواع مختلفة.

ويمكننا أن نعمّم هذا الاستدلال. إذا كانت لدينا مجموعة M فيها n من العناصر، واخترنا منها مجموعات من k من العناصر مع جواز تكرار العناصر، فإننا نكوّن متتالية من الأصفار والآحاد طولها n + k − 1 (k من الآحاد و n − 1 من الأصفار)، ونبحث عن عدد طرق توزيع الأصفار وعددها n − 1. إذن عدد التوافيق مع التكرار (لا رمز خاصاً له) يساوي

n+k−1Ck=(n+k−1n−1)=(n+k−1k).

والخطوة الأخيرة جائزة بفضل العلاقات الأساسية بين معاملات ذات الحدين.

أمثلة محلولة

  1. بكم طريقة يمكن أن نوزّع 20 تذكرة مجانية لعرض مسرحي على 10 متقاعدات؟ هذا مثال على التوافيق مع التكرار، لأنّ المتقاعدة الواحدة قد تحصل على أكثر من تذكرة، بل ربما على التذاكر كلها. يجب فقط أن نحدد بدقة ما n وما k. نحن في الحقيقة نختار توافيق من 20 عنصراً من بين 10 متقاعدات، أي نكوّن متتالية من الأصفار والآحاد طولها 29، فيها 20 واحداً و 9 أصفار. إذن n = 10, k = 20. فنحصل على النتيجة:

10+20−1C20=(10+20−120)=10,015,005.

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