ما هو عدد ستيرلنغ من النوع الثاني؟
عدد ستيرلنغ من النوع الثاني، ويُرمز له بالرمز \(S(n,k)\)، يحسب عدد الطرق الممكنة لتقسيم مجموعة مكوّنة من \(n\) عنصرًا متمايزًا (مُعنونًا) إلى \(k\) مجموعة جزئية غير فارغة وغير مُعنونة. وهو مقدار أساسي في علم التوافيق (Combinatorics) ويظهر في المسائل المتعلقة بتقسيم المجموعات، والدوال الغامرة (Surjections)، وأعداد بِل. هذه أداة رياضية بحتة تعمل بالطريقة نفسها في كل مكان دون اختلاف.
كيفية استخدام الحاسبة
أدخل حجم المجموعة \(n\) وعدد المجموعات الجزئية \(k\). يجب أن يكون كلاهما عددًا صحيحًا غير سالب. ثم اضغط على زر الحساب للحصول على قيمة \(S(n,k)\)، أي العدد الدقيق للتقسيمات. إذا كانت \(k\) أكبر من \(n\)، فإن الناتج يساوي 0، لأنه لا يمكن ملء عدد من المجموعات غير الفارغة يفوق عدد العناصر المتاحة.
شرح الصيغة
الصيغة الصريحة هي $$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} j^{n}$$ حيث يمثل \(C(k,j)\) المعامل الثنائي (Binomial coefficient). وهناك طريقة مكافئة وأكثر أمانًا من الناحية العددية، وهي العلاقة التراجعية $$S(n,k) = k\,S(n-1,k) + S(n-1,k-1)$$ بالحالات الأساسية \(S(0,0)=1\)، و \(S(n,0)=0\) عندما \(n>0\)، و \(S(0,k)=0\) عندما \(k>0\). تعتمد هذه الحاسبة على العلاقة التراجعية لتجنّب أخطاء الإلغاء في الأعداد ذات الفاصلة العائمة. ومن الحالات الخاصة المفيدة: \(S(n,1)=1\)، و \(S(n,n)=1\)، و \(S(n,2)=2^{n-1}-1\).
مثال محلول
لنأخذ \(n=5\) و \(k=2\): باستخدام الحالة الخاصة نجد أن $$S(5,2)=2^{5-1}-1=16-1=15.$$ وتؤكد العلاقة التراجعية هذه النتيجة: $$S(5,2)=2\cdot S(4,2)+S(4,1)=2\cdot 7+1=15.$$ إذًا هناك 15 طريقة لتقسيم مجموعة من 5 عناصر إلى مجموعتين غير فارغتين.
جدول أعداد ستيرلينغ من النوع الثاني S(n,k) للقيم n من 0 إلى 10
يمثل كل مدخل عدد الطرق لتقسيم مجموعة مكوّنة من n عنصرًا مُعرَّفًا (قابلًا للتمييز) إلى k مجموعات جزئية غير فارغة وغير مرقّمة بالضبط. يُبنى الجدول من علاقة التكرار \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\)، مع \(S(0,0)=1\) و\(S(n,0)=S(0,n)=0\) من أجل \(n\ge 1\). الخلايا الفارغة تمثل الحالات \(k>n\)، حيث تكون S(n,k)=0. العمود الأخير هو مجموع الصف، وهو عدد بيل B(n). على سبيل المثال، S(10,4) = 34105.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | مجموع الصف B(n) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | ||||||||||
| 1 | 0 | 1 | 1 | |||||||||
| 2 | 0 | 1 | 1 | 2 | ||||||||
| 3 | 0 | 1 | 3 | 1 | 5 | |||||||
| 4 | 0 | 1 | 7 | 6 | 1 | 15 | ||||||
| 5 | 0 | 1 | 15 | 25 | 10 | 1 | 52 | |||||
| 6 | 0 | 1 | 31 | 90 | 65 | 15 | 1 | 203 | ||||
| 7 | 0 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | 877 | |||
| 8 | 0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 | 4140 | ||
| 9 | 0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 | 21147 | |
| 10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 | 115975 |
التحقق من مدخل واحد باستخدام علاقة التكرار: \(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\). ودائمًا \(S(n,1)=1\)، و\(S(n,2)=2^{n-1}-1\)، و\(S(n,n-1)=\binom{n}{2}\)، و\(S(n,n)=1\).
المصطلحات الأساسية والترميز
- تقسيم المجموعة
- طريقة لتجزئة مجموعة إلى مجموعات جزئية غير فارغة ومتنافية مثنى مثنى (كتل) يكون اتحادها هو المجموعة كلها. ترتيب الكتل وترتيب العناصر داخل الكتلة لا يُحدثان فرقًا.
- مُعرَّف مقابل غير مُعرَّف
- عناصر المجموعة n مُعرَّفة (قابلة للتمييز، مثل 1، 2، …، n). المجموعات الجزئية k غير مرقّمة: تبديل كتلتين يعطي التقسيم نفسه. لو كانت الكتل مُعرَّفة لكان العدد k!·S(n,k) بدلًا من ذلك.
- كتلة غير فارغة
- يجب أن تحتوي كل مجموعة جزئية من المجموعات الـ k على عنصر واحد على الأقل. لهذا السبب يكون S(n,0)=0 من أجل n ≥ 1، وS(n,k)=0 عندما يكون k > n.
- الترميز S(n,k)
- عدد ستيرلينغ من النوع الثاني، ويُكتب أيضًا \(\left\{ n \atop k \right\}\). يُحسب بالصيغة \(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\).
- عدد بيل B(n)
- العدد الكلي لتقسيمات مجموعة مكوّنة من n عنصرًا إلى أي عدد من الكتل: \(B(n)=\sum_{k=0}^{n}S(n,k)\). القيم الأولى هي 1، 1، 2، 5، 15، 52، 203، 877، 4140، 21147، 115975.
- معامل ذو الحدين
- \(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\)، وهو عدد الطرق لاختيار j عنصرًا من بين k. ويظهر في صيغة الاحتواء والاستبعاد أعلاه.
- التطبيق الشامل (المتباين الغامر)
- دالة من مجموعة مكوّنة من n عنصرًا إلى مجموعة مكوّنة من k عنصرًا، بحيث يُصاب كل عنصر من عناصر مجموعة الـ k مرة واحدة على الأقل. عدد هذه الدوال هو \(k!\cdot S(n,k)\): نقسم المجال إلى k كتلة، ثم نسند الكتل إلى الأهداف الـ k بـ k! طريقة.
النوع الثاني مقابل النوع الأول. تعد أعداد ستيرلينغ من النوع الثاني تقسيمات مجموعة إلى k كتلة. أما أعداد ستيرلينغ من النوع الأول، وتُكتب \(c(n,k)\) أو \(\left[ n \atop k \right]\) (غير الموجبة)، فتعد التباديل لـ n عنصرًا التي لها k دورات بالضبط. وتتبع علاقة تكرار مختلفة هي \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\)، وترتبط بالنوع الثاني بكونهما مصفوفتين معكوستين لبعضهما (مع الإشارات).
الأسئلة الشائعة
لماذا تكون قيمة \(S(0,0)=1\)؟ بحكم الاصطلاح الرياضي، تمتلك المجموعة الخالية تقسيمًا واحدًا فقط إلى صفر أجزاء، وهو التقسيم الخالي.
ماذا يحدث عندما تكون \(k > n\)؟ يكون الناتج 0، لأن كل مجموعة جزئية يجب أن تكون غير فارغة، بينما لديك عدد من العناصر أقل من اللازم.
ما علاقة ذلك بأعداد بِل؟ عند جمع قيم \(S(n,k)\) لكل قيم \(k\) من 0 إلى \(n\)، نحصل على عدد بِل \(B(n)\)، وهو العدد الإجمالي لتقسيمات مجموعة مكوّنة من \(n\) عنصرًا.