संयोजन वर्ग

From Vigyanwiki

गणित में, संयोजन वर्ग गणितीय वस्तुओं का गणनीय सेट होता है, जिसमें आकार फ़ंक्शन प्रत्येक ऑब्जेक्ट को गैर-नकारात्मक पूर्णांक में मैप करता है, जैसे कि प्रत्येक आकार की सीमित रूप से कई वस्तुएं होती हैं।[1][2]


क्रमों की गिनती और समरूपता

एक संयोजन वर्ग का गिनती क्रम i = 0, 1, 2, ... के लिए आकार के तत्वों की संख्या का अनुक्रम है; इसे जनरेटिंग फ़ंक्शन के रूप में भी वर्णित किया जा सकता है जिसमें ये संख्याएं इसके गुणांक के रूप में होती हैं। कॉम्बिनेटरियल कक्षाओं के गिनती क्रम गणनात्मक कॉम्बिनेटरिक्स के अध्ययन का मुख्य विषय हैं। दो संयोजक वर्गों को समरूपी कहा जाता है यदि उनमें प्रत्येक आकार की वस्तुओं की संख्या समान हो, या समकक्ष, यदि उनकी गिनती का क्रम समान हो।[3] अक्सर, जब दो संयोजक वर्गों को आइसोमोर्फिक के रूप में जाना जाता है, तो इस तुल्यता का विशेषण प्रमाण मांगा जाता है; इस तरह के प्रमाण की व्याख्या यह दर्शाने के रूप में की जा सकती है कि दो आइसोमोर्फिक वर्गों की वस्तुएं दूसरे के लिए क्रिप्टोमोर्फिज्म हैं।

उदाहरण के लिए, नियमित बहुभुजों के बहुभुज त्रिभुज (बहुभुज की भुजाओं की संख्या द्वारा दिए गए आकार के साथ, और प्रत्येक आकार के लिए त्रिभुज बनाने के लिए बहुभुज का निश्चित विकल्प) और बिना जड़ वाला बाइनरी ट्री ट्री_(ग्राफ_थ्योरी)#प्लेन_ट्रीज़ (तक) का सेट ग्राफ समरूपता, पत्तियों के निश्चित क्रम के साथ, और पत्तियों की संख्या द्वारा दिए गए आकार के साथ) दोनों को कैटलन संख्याओं द्वारा गिना जाता है, इसलिए वे समरूपी संयोजन वर्ग बनाते हैं। इस मामले में विशेषण समरूपता दोहरे ग्राफ द्वारा दी गई है: त्रिकोण को प्रत्येक बहुभुज किनारे के लिए पत्ती, प्रत्येक त्रिकोण के लिए आंतरिक नोड और प्रत्येक दो (बहुभुज किनारों?) या त्रिकोणों के लिए किनारे के साथ पेड़ में रूपांतरित किया जा सकता है। दूसरे से सटे हुए हैं.[4]


विश्लेषणात्मक कॉम्बिनेटरिक्स

कॉम्बिनेटरियल प्रजातियों का सिद्धांत और विश्लेषणात्मक कॉम्बिनेटरिक्स तक इसका विस्तार कई महत्वपूर्ण कॉम्बिनेटरियल वर्गों का वर्णन करने, पहले से परिभाषित लोगों के संयोजन से नए वर्गों का निर्माण करने और स्वचालित रूप से उनके गिनती अनुक्रम प्राप्त करने के लिए भाषा प्रदान करता है।[3]उदाहरण के लिए, दो संयोजक वर्गों को असंयुक्त संघ द्वारा, या कार्टेशियन उत्पाद निर्माण द्वारा जोड़ा जा सकता है जिसमें वस्तुओं को दो वर्गों में से प्रत्येक से वस्तु के जोड़े का आदेश दिया जाता है, और आकार फ़ंक्शन प्रत्येक वस्तु के आकार का योग होता है जोड़ा। ये ऑपरेशन क्रमशः कॉम्बीनेटोरियल क्लासों के परिवार पर मोटी हो जाओ के जोड़ और गुणन संचालन का निर्माण करते हैं, जिसमें शून्य ऑब्जेक्ट खाली कॉम्बीनेटरियल क्लास है, और यूनिट वह क्लास है जिसका एकमात्र ऑब्जेक्ट खाली सेट है।[5]


क्रमपरिवर्तन पैटर्न

क्रमपरिवर्तन पैटर्न के अध्ययन में, क्रमपरिवर्तन लंबाई द्वारा गणना किए गए क्रमपरिवर्तन वर्गों के संयोजन वर्ग को विल्फ वर्ग कहा जाता है।[6] विशिष्ट क्रमपरिवर्तन वर्गों की गणना के अध्ययन से प्रतीत होता है कि असंबद्ध क्रमपरिवर्तन वर्गों के गिनती अनुक्रमों में अप्रत्याशित रूप से समतुल्यता सामने आई है।

संदर्भ

  1. 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.
  2. 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. 3.0 3.1 Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, Definition I.3, p.19, ISBN 9781139477161.
  4. 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.
  5. Bard, Gregory V. (2009), Algebraic Cryptanalysis, Springer, Section 4.2.1, "Combinatorial Classes", ff., pp. 30–34, ISBN 9780387887579.
  6. 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