ما الذي تقوم به هذه الحاسبة
تحسب حاسبة التوافيق مع التكرار عدد الطرق الممكنة لاختيار r من العناصر من بين n من الأنواع المختلفة، مع السماح بتكرار النوع نفسه ودون أن يكون لترتيب الاختيار أي أهمية. هذه إحدى الصيغ الأساسية في علم التوافيق ونظرية الاحتمالات، وتُعرف غالبًا بمسألة «النجوم والفواصل» (stars and bars). وبما أنه يمكن اختيار كل نوع أكثر من مرة، يكون العدد الناتج أكبر من عدد التوافيق العادية دون تكرار.
المُدخلات المطلوبة
- العدد الإجمالي لأنواع العناصر (n): كم فئة مختلفة يمكنك الاختيار من بينها — مثلًا 3 نكهات من المثلجات.
- عدد العناصر المراد اختيارها (r): كم اختيارًا تقوم به في المجموع، مع إمكانية انتقاء النوع نفسه أكثر من مرة.
أدخل كلا القيمتين كأعداد صحيحة، وتعيد الحاسبة على الفور نتيجة واحدة: عدد المجموعات المتعددة المتمايزة (اختيارات غير مرتبة تسمح بالتكرار).
الصيغة الرياضية
تطبّق الأداة المعادلة القياسية للتوافيق مع التكرار:
$$C^{R}(n,r) = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$تحسب الأداة داخليًا ثلاثة مضروبات — \((n + r - 1)!\) و\(r!\) و\((n - 1)!\) — ثم تجري عملية القسمة كما هو موضح. وبما أنها تعتمد على مضروبات دقيقة بحساب الأعداد الصحيحة، تكون النتيجة عددًا صحيحًا دقيقًا لا تقريبًا.
مثال محلول
لنفترض أن محل مثلجات يقدّم n = 3 من النكهات، وتريد كوبًا مكوّنًا من r = 2 من الكرات مع إمكانية تكرار النكهة نفسها. عوّض بالقيمتين n = 3 وr = 2:
- \(n + r - 1 = 3 + 2 - 1 = 4\)
- $$C(4, 2) = \frac{4!}{2! \cdot 2!} = \frac{24}{2 \cdot 2} = \mathbf{6}$$
إذًا توجد 6 احتمالات لكوب من كرتين: AA وBB وCC وAB وAC وBC. وتعيد الحاسبة الرقم 6 فورًا.
أمثلة عملية إضافية
يستخدم كل مثال أدناه نفس المتطابقة، \(C^{R}(n,r) = \binom{n+r-1}{r} = \frac{(n+r-1)!}{r!\,(n-1)!}\)، حيث \(n\) هو عدد أنواع العناصر المتميزة المتاحة و \(r\) هو عدد العناصر المختارة. الترتيب لا يهم وكل نوع قد يُستخدم مرة أخرى، لذا كل نتيجة هي مجموعة متعددة.
مثال 1 — ثلاثة نرد متطابقة (n = 6, r = 3)
تدحرج ثلاثة نرد سداسي الأضلاع لا يمكن تمييزها وتسجل فقط مجموعة الأوجه الظاهرة (بحيث 1-3-6 و 6-3-1 تُحسب كنتيجة واحدة). هناك \(n = 6\) أنواع أوجه و \(r = 3\) اختيارات، مع السماح بالتكرار لأن النردين يمكنهما إظهار نفس الوجه.
الفهرس العلوي: \(n + r - 1 = 6 + 3 - 1 = 8\).
$$C^{R}(6,3) = \binom{8}{3} = \frac{8!}{3!\,5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56$$هناك 56 تجميعة أوجه متميزة غير مرتبة. لاحظ أن هذا أقل بكثير من \(6^3 = 216\) رمية مرتبة — تنهار النتائج المرتبة البالغ عددها 216 على 56 مجموعة متعددة، لكن بشكل غير متساوٍ (ثلاثية مثل 4-4-4 لها ترتيب واحد، بينما 1-3-6 لها ستة)، وهذا بالضبط السبب في أن احتماليات مجموع النرد يجب أن تُحسب من 216 رمية مرتبة وليس من 56 مجموعة متعددة.
مثال 2 — ملاعق أكثر من النكهات (n = 3, r = 5)
متجر الآيس كريم يقدم 3 نكهات وتطلب دلو بـ 5 ملاعق؛ السماح بملاعق من نفس النكهة والترتيب الذي يتم حزمه فيه لا يهم. هنا \(r = 5\) أكبر من \(n = 3\)، وهو مستحيل للتوليفات بدون تكرار لكنه مقبول تماماً هنا.
الفهرس العلوي: \(n + r - 1 = 3 + 5 - 1 = 7\).
$$C^{R}(3,5) = \binom{7}{5} = \frac{7!}{5!\,2!} = \frac{7 \times 6}{2 \times 1} = \frac{42}{2} = 21$$هناك 21 دلو ممكن. الاختصار هنا هو حذف \(5!\) بدلاً من \(2!\): لأن \(\binom{7}{5} = \binom{7}{2}\)، يبقى فقط عاملان في البسط. من حيث النجوم والأعمدة، أنت تضع 5 نجوم (ملاعق) و \(n - 1 = 2\) أعمدة (فواصل النكهات) في 7 فتحات — على سبيل المثال \(\star\star\,|\,\star\,|\,\star\star\) تعني 2 فانيليا، 1 شوكولاتة، 2 فراولة.
مثال 3 — حالتا الحد (r = 1 و n = 1)
اختيار عنصر واحد (n = 4, r = 1). تختار مشروباً واحداً من 4 أحجام. مع اختيار واحد فقط، لا يمكن أن يحدث التكرار، لذلك يجب أن تكون الإجابة ببساطة عدد الأنواع:
$$C^{R}(4,1) = \binom{4+1-1}{1} = \binom{4}{1} = \frac{4!}{1!\,3!} = \frac{4}{1} = 4$$التي تعطي 4 نتائج — العمود \(r = 1\) في أي جدول من هذا القبيل يكون دائماً فقط \(n\).
نوع واحد فقط (n = 1, r = 7). تخزن آلة بيع منتجاً واحداً وتشتري 7 وحدات:
$$C^{R}(1,7) = \binom{1+7-1}{7} = \binom{7}{7} = \frac{7!}{7!\,0!} = \frac{5040}{5040 \times 1} = 1$$يوجد مجموعة متعددة واحدة بالضبط — "سبع وحدات من الشيء الوحيد المتاح" — لأنه مع نوع واحد لا توجد خيارات متبقية. رسمياً \(n - 1 = 0\) أعمدة مطلوبة، يجب أن تكون جميع المواضع السبعة نجوماً، و \(\binom{7}{7} = 1\). نفس المنطق يجعل \(C^{R}(n,0) = 1\) لأي \(n\): اختيار لا شيء هو اختيار واحد صحيح (فارغ)، وهذا هو السبب في أن \(0! = 1\) هي الاتفاقية التي تحافظ على اتساق الصيغة.
جدول مرجعي للتوليفات مع التكرار
قيم دقيقة لـ \(C^{R}(n,r) = \binom{n+r-1}{r}\) لـ 1–8 أنواع عناصر مختارة من 1–6 في كل مرة. اقرأ لأسفل حتى عدد أنواعك \(n\)، ثم عبر عدد الاختيارات \(r\).
| n (أنواع) | r = 1 | r = 2 | r = 3 | r = 4 | r = 5 | r = 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | 4 | 5 | 6 | 7 |
| 3 | 3 | 6 | 10 | 15 | 21 | 28 |
| 4 | 4 | 10 | 20 | 35 | 56 | 84 |
| 5 | 5 | 15 | 35 | 70 | 126 | 210 |
| 6 | 6 | 21 | 56 | 126 | 252 | 462 |
| 7 | 7 | 28 | 84 | 210 | 462 | 924 |
| 8 | 8 | 36 | 120 | 330 | 792 | 1716 |
كيفية قراءة الأنماط
- كل صف هو قطري من مثلث باسكال. الصف \(n = 1\) هو متسلسلة ثابتة من الـ 1، الصف \(n = 2\) هو الأعداد الطبيعية \(2, 3, 4, \dots\)، الصف \(n = 3\) هو الأعداد المثلثة \(3, 6, 10, 15, 21, 28\)، والصف \(n = 4\) هو الأعداد الرباعية الأبعاد \(4, 10, 20, 35, 56, 84\). هذا ببساطة \(\binom{n+r-1}{r}\) الممتدة على طول \(n\) ثابت.
- الجدول متماثل تحت إزاحة. لأن \(\binom{n+r-1}{r} = \binom{n+r-1}{n-1}\)، نحصل على \(C^{R}(n,r) = C^{R}(r+1,\,n-1)\). على سبيل المثال \(C^{R}(6,3) = 56 = C^{R}(4,5)\)، و \(C^{R}(8,3) = 120 = C^{R}(4,7)\). تبديل أدوار "الأنواع" و "الاختيارات" بهذه الطريقة غالباً ما يحول الضرب الطويل إلى ضرب قصير.
- النمو متعدد الحدود في r، من الدرجة n − 1. مع إبقاء \(n\) ثابتاً، \(C^{R}(n,r) = \frac{(r+1)(r+2)\cdots(r+n-1)}{(n-1)!}\)، متعدد حدود من الدرجة \(n-1\) — خطي لـ \(n = 2\)، تربيعي لـ \(n = 3\)، مكعب لـ \(n = 4\). مع إبقاء \(r\) ثابتاً وزيادة \(n\) يتصرف بنفس الطريقة مع عكس الأدوار (درجة \(r\) في \(n\)). على أي حال تبقى العدادات أقل بكثير من \(n^{r}\) عد الاختيارات المرتبة مع التكرار.
- كل إدخال هو مجموع الواحد فوقه والواحد على يساره (حيث يكون كلاهما موجوداً): \(C^{R}(n,r) = C^{R}(n-1,r) + C^{R}(n,r-1)\). تحقق من \(126 = 70 + 56\) في الخلية \(n = 6\)، \(r = 4\). هذا التكرار هو طريقة سريعة لتوسيع الجدول يدويّاً.
كيفية حسابها يدويّاً
صورة النجوم والأعمدة
قبل الحساب، يساعد أن ترى لماذا للصيغة هذا الشكل. مثّل الاختيار كـ \(r\) نجوم متطابقة (العناصر التي تأخذها) مفصولة إلى \(n\) مجموعات بـ \(n-1\) أعمدة (الفواصل بين أنواع العناصر المتتالية). عدد النجوم في المجموعة \(i\) هو عدد نسخ النوع \(i\) التي اخترتها. كل ترتيب من النجوم والأعمدة يتوافق مع اختيار صحيح واحد بالضبط، وهناك \(r + (n-1) = n + r - 1\) مواضع في الصف. عد الاختيارات يعني اختيار أي \(r\) من تلك المواضع الـ \(n+r-1\) تحتفظ بالنجوم:
$$C^{R}(n,r) = \binom{n+r-1}{r} = \binom{n+r-1}{n-1}$$على سبيل المثال مع \(n = 4\) أنواع و \(r = 5\) اختيارات، الصف \(\star\,|\,|\,\star\star\star\,|\,\star\) له 8 مواضع ويعني 1 من النوع A، لا شيء من النوع B، 3 من النوع C، 1 من النوع D.
إجراء خطوة بخطوة
- تحقق من المدخلات. تأكد من أن \(n\) و \(r\) أعداد صحيحة مع \(n \ge 1\) و \(r \ge 0\). بخلاف التوليفات بدون تكرار، قد يتجاوز \(r\) \(n\) — التكرار مسموح به، لذا لا توجد حد أعلى لـ \(r\).
- احسب الفهرس العلوي. احسب \(N = n + r - 1\). هذا هو العدد الإجمالي لمواضع النجوم والأعمدة.
- اكتب ذات الحدين. \(C^{R}(n,r) = \dbinom{N}{r} = \dfrac{N!}{r!\,(n-1)!}\). لا تطور هذه المضروبات بالكامل أبداً — \(N!\) ينفجر بسرعة والأعداد الكبيرة تلغي بعضها.
- ألغِ \((n-1)!\) مع \(N!\). بما أن \(N - r = n - 1\)، يترك حاصل القسمة \(N!/(n-1)!\) بالضبط \(r\) عوامل تنازلية في البسط:
- اضرب حدود البسط الـ \(r\)، ثم اقسم على \(r!\). إذا كان \(r\) أكبر من \(n-1\)، استخدم التماثل \(\binom{N}{r} = \binom{N}{n-1}\) أولاً لتضرب العدد الأصغر من العوامل بدلاً من ذلك.
- تحقق من أن النتيجة عدد صحيح. معامل ذات الحدين دائماً عدد صحيح، لذا أي كسر متبقٍ أو باقٍ يعني خطأ حسابي. اختباران سريعان آخران: يجب أن يعطي \(r = 1\) بالضبط \(n\)، ويجب أن يعطي \(n = 1\) بالضبط 1.
مثال عملي (n = 5, r = 4)
أربع ملاعق من الزبادي المجمد من 5 إضافات، التكرار مسموح به، الترتيب غير ذي صلة.
- الخطوة 2: \(N = 5 + 4 - 1 = 8\).
- الخطوة 3: \(C^{R}(5,4) = \dfrac{8!}{4!\,4!}\).
- الخطوة 4: ألغِ \((n-1)! = 4!\)، وترك \(r = 4\) عوامل تنازلية من 8 حتى \(n = 5\): \(\dfrac{8 \times 7 \times 6 \times 5}{4!}\).
- الخطوة 5: \(\dfrac{1680}{24} = 70\).
- الخطوة 6: 70 عدد صحيح، وهو يطابق خلية \(n = 5\)، \(r = 4\) في الجدول المرجعي أعلاه.
الإجابة هي 70 تجميعة إضافات متميزة. تباين مفيد: نفس المدخلات تعطي \(5^4 = 625\) إذا أهم الترتيب، و فقط \(\binom{5}{4} = 5\) إذا كان التكرار محظوراً — لذا قرر دائماً ما إذا كان الترتيب والتكرار ينطبقان قبل اختيار صيغة.
الأسئلة الشائعة
ما الفرق بين هذا وبين التوافيق العادية؟ التوافيق العادية \(C(n, r)\) تمنع التكرار — إذ يُختار كل عنصر مرة واحدة على الأكثر. أما التوافيق مع التكرار فتسمح باختيار النوع نفسه عدة مرات، ولهذا ننتقل إلى الصيغة \(C(n + r - 1, r)\).
هل للترتيب أهمية هنا؟ لا. فاختيار AB يُعدّ نفس اختيار BA. ولو كان الترتيب مهمًا لاستخدمت التباديل (التراتيب) بدلًا من ذلك.
هل يمكن أن يكون r أكبر من n؟ نعم. وبما أن التكرار مسموح به، يمكنك اختيار عدد من العناصر أكبر من عدد الأنواع — فمثلًا اختيار 5 كرات من 3 نكهات أمر صحيح تمامًا ويعطي عددًا أكبر.