الترتيب مع التكرار
الترتيب مع التكرار (arrangements with repetition) يشبه التباديل العادية، إلا أننا نسمح بتكرار عناصر المجموعة الأساسية M (المجموعة التي نختار منها العناصر).
التعريف والقانون
لنبدأ بمثال تقليدي: كم كلمة مختلفة طولها 6 يمكن أن نكوّن من حروف الأبجدية الإنجليزية (abc … xyz، وعددها 26 حرفاً)؟ ستة حروف ليست كثيرة، ومع ذلك سيكون عدد الكلمات كبيراً نسبياً. لا يهمنا معنى الكلمات، فالكلمة «weqrww» مثلاً كلمة صالحة طولها ستة حروف.
لا نحتاج في الحساب إلا إلى مبدأ العد الأساسي (قاعدة الضرب). لدينا 26 حرفاً مختلفاً يمكن أن نستخدمها. ففي الخانة الأولى يمكن أن نضع أحد 26 حرفاً. وفي الخانة الثانية يمكن أن نضع أيضاً أحد 26 حرفاً، لأننا لم نشترط ألا تتكرر الحروف. وهكذا نختار في كل خانة من بين 26 حرفاً، فيكون العدد الكلي للترتيبات بحسب قاعدة الضرب 266 = 308,915,776. وهذا عدد كبير نسبياً، مع أننا استخدمنا 26 حرفاً فقط.
نقول إنّ الترتيب مع التكرار المكوّن من k من العناصر من مجموعة M فيها n من العناصر هو كل نونية مرتبة طولها k عناصرها من المجموعة M، ويمكن أن يتكرر فيها كل عنصر حتى k مرات. فإذا كانت M = {1, 2, 3}، فإنّ كل ما يلي ترتيبات رباعية مع التكرار صالحة: (1, 1, 1, 1)، (1, 2, 3, 1)، (2, 2, 3, 3). وعدد هذه الترتيبات مع التكرار (لا رمز خاصاً له) هو
أمثلة محلولة
-
كم عدداً مكوّناً من ستة أرقام يمكن أن نكوّن من الأرقام {2, 4, 6, 8}، إذا كان يجوز تكرار الأرقام؟ نعوّض ببساطة في القانون: في المجموعة 4 عناصر، ونختار سداسيات، فعدد الترتيبات مع التكرار هو
-
يُستخدم في الحواسيب عادةً نظام العد الثنائي، أي النظام الذي لا يستخدم إلا الرقمين 0 و 1. وتُستخدم فيه وحدات جديدة، فالبت (bit) مثلاً يمثل خلية نخزّن فيها إما صفراً وإما واحداً. وأكبر منه البايت (byte)، وهو يحتوي على 8 بتات. فالرقم 1 بت واحد، أما 01110001 فبايت واحد. بكم طريقة مختلفة يمكن أن نملأ بايتاً واحداً بثمانية بتات؟
نختار من المجموعة {0, 1}، أي من عنصرين. ونختار نونية مرتبة طولها k = 8، فيكون عدد كل الإمكانيات
-
نعلم من المثال السابق أنّ البايت الواحد يمكن أن يميّز بين 256 قيمة مختلفة. بكم طريقة يمكن أن نملأ 4 بايتات؟
تحتوي البايتات الأربعة على 4 × 8 = 32 بتاً، وما زلنا نختار من مجموعة فيها عنصران. فتكون النتيجة:
نرى أنّ أربعة بايتات فقط يمكن أن تميّز بين أكثر من أربعة مليارات قيمة. وللمقارنة: سعة الأقراص في الحواسيب اليوم مئات الغيغابايتات أو حتى عدة تيرابايتات. والتيرابايت الواحد يحتوي على 1,000,000,000,000 بايت، أي على 8,000,000,000,000 بت. إذن يمكن أن نخزّن في قرص سعته تيرابايت واحد حتى 28,000,000,000,000 قيمة مختلفة.
ملاحظة: يسود اليوم شيء من الالتباس في مفهوم الكيلوبايت (والميغابايت وغيرهما). فلأسباب تقنية لم يكن الكيلوبايت الواحد يساوي 1000 بايت، كما جرت العادة في الوحدات الأخرى (فالكيلوغرام الواحد يساوي ألف غرام)، بل كان يساوي 210 بايت، أي 1024 بايت. وكان الميغابايت الواحد يساوي 220 بايت، أي 210 كيلوبايت.
ولذلك نميّز اليوم بين كتابتين: 1 kB (ونقرؤها كيلوبايت) يساوي 1000 بايت، و 1 KiB (ونقرؤها كيبيبايت) يساوي 210 = 1024 بايت.
-
وثمة مثال آخر في مقالة مستقلة عن أمان كلمة المرور.
المحتويات: التوافيقيات, التباديل (الترتيب دون تكرار), تباديل جميع العناصر, التوافيق, الترتيب مع التكرار, التوافيق مع التكرار, عدد رموز PIN الممكنة