संयोजन वर्ग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 22: | Line 22: | ||
| title = Boltzmann samplers for the random generation of combinatorial structures | | title = Boltzmann samplers for the random generation of combinatorial structures | ||
| volume = 13 | | volume = 13 | ||
| year = 2004}}.</ref> | | year = 2004}}.</ref> | ||
==क्रमों की गिनती और समरूपता == | ==क्रमों की गिनती और समरूपता == | ||
एक संयोजन वर्ग का गिनती क्रम i = 0, 1, 2, ... के लिए आकार के तत्वों की संख्या का अनुक्रम है; इसे [[जनरेटिंग फ़ंक्शन|जनरेटिंग फलन]] के रूप में भी वर्णित किया जा सकता है जिसमें ये संख्याएं इसके गुणांक के रूप में होती हैं। संयोजक कक्षाओं के गिनती क्रम गणनात्मक संयोजक के अध्ययन का मुख्य विषय हैं। दो संयोजक वर्गों को समरूपी कहा जाता है यदि उनमें प्रत्येक आकार की वस्तुओं की संख्या समान हो, या समकक्ष, यदि उनकी गिनती का क्रम समान होता है।<ref name="ac">{{citation|title=Analytic Combinatorics|first1=Philippe|last1=Flajolet|author1-link=Philippe Flajolet|first2=Robert|last2=Sedgewick|author2-link=Robert Sedgewick (computer scientist)|publisher=Cambridge University Press|year=2009|isbn=9781139477161|at=Definition I.3, p.19|title-link= Analytic Combinatorics}}.</ref> अधिकांशतः, जब दो संयोजक वर्गों को आइसोमोर्फिक के रूप में जाना जाता है, जिससे इस तुल्यता का [[विशेषण प्रमाण]] मांगा जाता है; इस प्रकार के प्रमाण की व्याख्या यह दर्शाने के रूप में की जा सकती है कि दो आइसोमोर्फिक वर्गों की वस्तुएं दूसरे के लिए [[क्रिप्टोमोर्फिज्म]] हैं। | एक संयोजन वर्ग का गिनती क्रम i = 0, 1, 2, ... के लिए आकार के तत्वों की संख्या का अनुक्रम है; इसे [[जनरेटिंग फ़ंक्शन|जनरेटिंग फलन]] के रूप में भी वर्णित किया जा सकता है जिसमें ये संख्याएं इसके गुणांक के रूप में होती हैं। संयोजक कक्षाओं के गिनती क्रम गणनात्मक संयोजक के अध्ययन का मुख्य विषय हैं। दो संयोजक वर्गों को समरूपी कहा जाता है यदि उनमें प्रत्येक आकार की वस्तुओं की संख्या समान हो, या समकक्ष, यदि उनकी गिनती का क्रम समान होता है।<ref name="ac">{{citation|title=Analytic Combinatorics|first1=Philippe|last1=Flajolet|author1-link=Philippe Flajolet|first2=Robert|last2=Sedgewick|author2-link=Robert Sedgewick (computer scientist)|publisher=Cambridge University Press|year=2009|isbn=9781139477161|at=Definition I.3, p.19|title-link= Analytic Combinatorics}}.</ref> अधिकांशतः, जब दो संयोजक वर्गों को आइसोमोर्फिक के रूप में जाना जाता है, जिससे इस तुल्यता का [[विशेषण प्रमाण]] मांगा जाता है; इस प्रकार के प्रमाण की व्याख्या यह दर्शाने के रूप में की जा सकती है कि दो आइसोमोर्फिक वर्गों की वस्तुएं दूसरे के लिए [[क्रिप्टोमोर्फिज्म]] हैं। | ||
Revision as of 15:37, 8 July 2023
गणित में, संयोजन वर्ग गणितीय वस्तुओं का गणनीय समुच्चय होता है, जिसमें आकार फलन प्रत्येक ऑब्जेक्ट को गैर-नकारात्मक पूर्णांक में मैप करता है, जैसे कि प्रत्येक आकार की सीमित रूप से कई वस्तुएं होती हैं।[1][2]
क्रमों की गिनती और समरूपता
एक संयोजन वर्ग का गिनती क्रम i = 0, 1, 2, ... के लिए आकार के तत्वों की संख्या का अनुक्रम है; इसे जनरेटिंग फलन के रूप में भी वर्णित किया जा सकता है जिसमें ये संख्याएं इसके गुणांक के रूप में होती हैं। संयोजक कक्षाओं के गिनती क्रम गणनात्मक संयोजक के अध्ययन का मुख्य विषय हैं। दो संयोजक वर्गों को समरूपी कहा जाता है यदि उनमें प्रत्येक आकार की वस्तुओं की संख्या समान हो, या समकक्ष, यदि उनकी गिनती का क्रम समान होता है।[3] अधिकांशतः, जब दो संयोजक वर्गों को आइसोमोर्फिक के रूप में जाना जाता है, जिससे इस तुल्यता का विशेषण प्रमाण मांगा जाता है; इस प्रकार के प्रमाण की व्याख्या यह दर्शाने के रूप में की जा सकती है कि दो आइसोमोर्फिक वर्गों की वस्तुएं दूसरे के लिए क्रिप्टोमोर्फिज्म हैं।
उदाहरण के लिए, नियमित बहुभुज के बहुभुज त्रिभुज (बहुभुज की भुजाओं की संख्या द्वारा दिए गए आकार के साथ, और प्रत्येक आकार के लिए त्रिभुज बनाने के लिए बहुभुज का निश्चित विकल्प) और बिना जड़ वाला बाइनरी ट्री (ग्राफ सिद्धांत) प्लेन ट्रीज़ का समुच्चय ग्राफ समरूपता, पत्तियों के निश्चित क्रम के साथ, और पत्तियों की संख्या द्वारा दिए गए आकार के साथ) दोनों को कैटलन संख्याओं द्वारा गिना जाता है, इसलिए वे समरूपी संयोजन वर्ग बनाते हैं। इस स्थिति में विशेषण समरूपता दोहरे ग्राफ द्वारा दी गई है: त्रिकोण को प्रत्येक बहुभुज किनारे के लिए पत्ती, प्रत्येक त्रिकोण के लिए आंतरिक नोड और प्रत्येक दो (बहुभुज किनारों?) या त्रिकोणों के लिए किनारे के साथ ट्री में रूपांतरित किया जा सकता है। दूसरे से सटे हुए हैं.[4]
विश्लेषणात्मक संयोजक
संयोजक प्रजातियों का सिद्धांत और विश्लेषणात्मक संयोजक तक इसका विस्तार कई महत्वपूर्ण संयोजक वर्गों का वर्णन करने, पहले से परिभाषित लोगों के संयोजन से नए वर्गों का निर्माण करने और स्वचालित रूप से उनके गिनती अनुक्रम प्राप्त करने के लिए भाषा प्रदान करता है।[3] उदाहरण के लिए, दो संयोजक वर्गों को असंयुक्त संघ द्वारा, या कार्टेशियन उत्पाद निर्माण द्वारा जोड़ा जा सकता है जिसमें वस्तुओं को दो वर्गों में से प्रत्येक से वस्तु के जोड़े का आदेश दिया जाता है, और आकार फलन प्रत्येक वस्तु के आकार का योग होता है जोड़ा। ये संचालन क्रमशः संयोजक क्लासों के वर्ग पर सेमीरिंग के जोड़ और गुणन संचालन का निर्माण करते हैं, जिसमें शून्य ऑब्जेक्ट खाली कॉम्बीनेटरियल क्लास है, और इकाई वह क्लास है जिसका एकमात्र ऑब्जेक्ट खाली समुच्चय है।[5]
क्रमपरिवर्तन प्रतिरूप
क्रमपरिवर्तन प्रतिरूप के अध्ययन में, क्रमपरिवर्तन लंबाई द्वारा गणना किए गए क्रमपरिवर्तन वर्ग के संयोजन वर्ग को विल्फ वर्ग कहा जाता है।[6] विशिष्ट क्रमपरिवर्तन वर्गों की गणना के अध्ययन से प्रतीत होता है कि असंबद्ध क्रमपरिवर्तन वर्गों के गिनती अनुक्रमों में अप्रत्याशित रूप से समतुल्यता सामने आई है।
संदर्भ
- ↑ Martínez, Conrado; Molinero, Xavier (2001), "A generic approach for the unranking of labeled combinatorial classes" (PDF), Random Structures & Algorithms, 19 (3–4): 472–497, doi:10.1002/rsa.10025, MR 1871563.
- ↑ Duchon, Philippe; Flajolet, Philippe; Louchard, Guy; Schaeffer, Gilles (2004), "Boltzmann samplers for the random generation of combinatorial structures", Combinatorics, Probability and Computing, 13 (4–5): 577–625, doi:10.1017/S0963548304006315, MR 2095975.
- ↑ 3.0 3.1 Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, Definition I.3, p.19, ISBN 9781139477161.
- ↑ De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010), Triangulations: Structures for Algorithms and Applications, Algorithms and Computation in Mathematics, vol. 25, Springer, Theorem 1.1.3, pp. 4–6, ISBN 9783642129711.
- ↑ Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34, ISBN 9780387887579.
- ↑ Steingrímsson, Einar (2013), "Some open problems on permutation patterns", Surveys in combinatorics 2013, London Math. Soc. Lecture Note Ser., vol. 409, Cambridge Univ. Press, Cambridge, pp. 239–263, MR 3156932
