दूसरे प्रकार की स्टर्लिंग संख्या क्या है?
दूसरे प्रकार की स्टर्लिंग संख्या, जिसे \(S(n,k)\) लिखा जाता है, यह गिनती है कि n अलग-अलग (लेबल वाले) तत्वों के एक समुच्चय को ठीक k गैर-खाली, अलेबल उपसमुच्चयों में कितने तरीकों से बाँटा जा सकता है। यह संयोजनशास्त्र (combinatorics) की एक बुनियादी राशि है और समुच्चय विभाजन, आच्छादक फलन (surjections) तथा बेल संख्याओं से जुड़ी समस्याओं में सामने आती है। यह शुद्ध गणित का उपकरण है, जो हर जगह एक ही तरह काम करता है।
इस कैलकुलेटर का उपयोग कैसे करें
समुच्चय का आकार \(n\) और उपसमुच्चयों की संख्या \(k\) दर्ज करें। दोनों ऋणेतर पूर्णांक (non-negative integers) होने चाहिए। \(S(n,k)\) — यानी विभाजनों की सटीक गिनती — पाने के लिए calculate दबाएँ। यदि 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\), \(n>0\) के लिए \(S(n,0)=0\), और \(k>0\) के लिए \(S(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$$यानी 5 तत्वों वाले समुच्चय को दो गैर-खाली समूहों में बाँटने के 15 तरीके हैं।
दूसरे प्रकार की स्टर्लिंग संख्याओं S(n,k) की तालिका, n = 0 से 10 तक
प्रत्येक प्रविष्टि उन तरीकों की संख्या है जिनसे n अंकित (labeled) तत्वों के समुच्चय को ठीक k गैर-रिक्त, बिना अंकित (unlabeled) खंडों में विभाजित किया जा सकता है। तालिका पुनरावृत्ति सूत्र \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\) से बनाई गई है, जिसमें \(S(0,0)=1\) और \(n\ge 1\) के लिए \(S(n,0)=S(0,n)=0\) है। रिक्त कोष्ठ \(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 में से प्रत्येक उपसमुच्चय में कम से कम एक तत्व होना चाहिए। इसी कारण n ≥ 1 के लिए S(n,0)=0 है और जब k > n हो तो S(n,k)=0 है।
- संकेतन 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)!}\), k में से j वस्तुएँ चुनने के तरीकों की संख्या। यह ऊपर के समावेशन–अपवर्जन सूत्र में आता है।
- आच्छादक फलन (Surjection)
- n-समुच्चय से k-समुच्चय पर एक फलन, जिसमें k-समुच्चय का प्रत्येक तत्व कम से कम एक बार प्रभावित हो। ऐसे फलनों की संख्या \(k!\cdot S(n,k)\) है: प्रांत को k खंडों में बाँटो, फिर खंडों को k लक्ष्यों को k! तरीकों से सौंपो।
दूसरे प्रकार बनाम पहले प्रकार। दूसरे प्रकार की स्टर्लिंग संख्याएँ किसी समुच्चय के k खंडों में विभाजनों की गिनती करती हैं। पहले प्रकार की स्टर्लिंग संख्याएँ, जो \(c(n,k)\) या \(\left[ n \atop k \right]\) (अचिह्नित) लिखी जाती हैं, n तत्वों के ठीक k चक्रों वाले क्रमचयों (permutations) की गिनती करती हैं। इनका पुनरावृत्ति सूत्र अलग है, \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\), और ये (चिह्नों सहित) एक-दूसरे के व्युत्क्रम आव्यूह (inverse matrices) हैं।
अक्सर पूछे जाने वाले प्रश्न
\(S(0,0)=1\) क्यों होता है? परंपरा के अनुसार, रिक्त समुच्चय (empty set) का शून्य भागों में ठीक एक ही विभाजन होता है: रिक्त विभाजन।
जब \(k > n\) हो तो क्या होता है? परिणाम 0 होता है, क्योंकि हर उपसमुच्चय गैर-खाली होना चाहिए और आपके पास तत्व बहुत कम हैं।
इसका बेल संख्याओं से क्या संबंध है? \(k=0\) से \(n\) तक सभी \(S(n,k)\) का योग करने पर बेल संख्या \(B(n)\) मिलती है, जो n तत्वों वाले समुच्चय के कुल विभाजनों की संख्या है।