आंशिक क्रमपरिवर्तन
साहचर्य गणित में, परिमित समुच्चय S पर एक आंशिक क्रम परिवर्तन या पुनरावृत्ति के बिना अनुक्रम, S के दो निर्दिष्ट उपसमूहों के बीच एक आक्षेप है। यही है, यह समान आकार के दो उपसमुच्चय U और V द्वारा परिभाषित किया गया है, और U से V तक एक-से-एक प्रतिचित्रण है। समतुल्य रूप से, यह 'S' पर आंशिक फलन है जिसे क्रमपरिवर्तन तक बढ़ाया जा सकता है।[1][2]
प्रतिनिधित्व
उस विषय पर विचार करना सामान्य है जब समुच्चय S मात्र प्रथम n पूर्णांकों का समुच्चय {1, 2, ..., n} है। इस विषय में, एक आंशिक क्रमपरिवर्तन को n प्रतीकों के एक स्ट्रिंग(कंप्यूटर विज्ञान) द्वारा दर्शाया जा सकता है, जिनमें से कुछ 1 से लेकर श्रेणी में विशिष्ट संख्याएं हैं और जिनमें से शेष एक विशेष छिद्र प्रतीक ◊ हैं। इस सूत्रीकरण में, आंशिक क्रमपरिवर्तन के फलन U के प्रांत में स्ट्रिंग में स्थिति होती है जिसमें छिद्र नहीं होता है, और ऐसी प्रत्येक स्थिति को उस स्थिति में संख्या में प्रतिचित्रित किया जाता है। उदाहरण के लिए, स्ट्रिंग 1 ◊ 2 आंशिक क्रमपरिवर्तन का प्रतिनिधित्व करेगा जो 1 को स्वयं से प्रतिचित्रित करता है और 3 से 2 को प्रतिचित्रित करता है।[3]
दो पदों पर सात आंशिक क्रमपरिवर्तन हैं
- ◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21।
संयुक्त गणना
n पदों पर आंशिक क्रमपरिवर्तन की संख्या, n = 0, 1, 2, ... के लिए पूर्णांक अनुक्रम द्वारा दी गई है
- 1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, ... (sequence A002720 in the OEIS)
जहां अनुक्रम में nवां पद योग सूत्र द्वारा दिया गया है
जिसमें iवां पद आकार i के समर्थन के साथ आंशिक क्रमपरिवर्तन की संख्या की गणना करता है, अर्थात i गैर-छिद्र प्रविष्टियों वाले आंशिक क्रमपरिवर्तन की संख्या।
वैकल्पिक रूप से, इसकी गणना पुनरावृत्ति संबंध द्वारा की जा सकती है
यह निम्नानुसार निर्धारित किया जाता है:
- आंशिक क्रमपरिवर्तन जहां प्रत्येक समुच्चय के अंतिम अवयव छोड़े जाते हैं:
- आंशिक क्रमपरिवर्तन जहां प्रत्येक समुच्चय के अंतिम अवयव एक दूसरे को प्रतिचित्रित करते हैं।
- आंशिक क्रमपरिवर्तन जहां पूर्व समुच्चय का अंतिम अवयव सम्मिलित है, परन्तु दूसरे समुच्चय के अंतिम अवयव को प्रतिचित्रित नहीं करता है
- आंशिक क्रमपरिवर्तन जहां दूसरे समुच्चय का अंतिम अवयव सम्मिलित है, परन्तु पूर्व समुच्चय के अंतिम अवयव को प्रतिचित्रित नहीं करता है
- , 3 और 4 दोनों में सम्मिलित आंशिक क्रमपरिवर्तन, वे क्रमपरिवर्तन जहां दोनों समुच्चय के अंतिम अवयव सम्मिलित हैं, परन्तु एक दूसरे के लिए प्रतिचित्रित नहीं करते हैं।
प्रतिबंधित आंशिक क्रमपरिवर्तन
कुछ लेखक आंशिक क्रमपरिवर्तन को प्रतिबंधित करते हैं ताकि या तो प्रांत[4] या सीमा[3]कुछ k के लिए, n पदों के समुच्चय में प्रथम k पदों को सम्मिलित करने के लिए आपत्ति को अत्यावश्यक किया जाता है। पूर्व विषय में, n-समुच्चय से लंबाई k का आंशिक क्रमपरिवर्तन बिना दोहराव के n-समुच्चय से k शब्दों का एक क्रम है।(प्रारंभिक साहचर्य में, इन पदों को कभी-कभी अस्पष्टतः रूप से n-समुच्चय के k-क्रमपरिवर्तन कहा जाता है।)
संदर्भ
- ↑ Straubing, Howard (1983), "A combinatorial proof of the Cayley-Hamilton theorem", Discrete Mathematics, 43 (2–3): 273–279, doi:10.1016/0012-365X(83)90164-4, MR 0685635.
- ↑ Ku, C. Y.; Leader, I. (2006), "An Erdős-Ko-Rado theorem for partial permutations", Discrete Mathematics, 306 (1): 74–86, doi:10.1016/j.disc.2005.11.007, MR 2202076.
- ↑ 3.0 3.1 Claesson, Anders; Jelínek, Vít; Jelínková, Eva; Kitaev, Sergey (2011), "Pattern avoidance in partial permutations", Electronic Journal of Combinatorics, 18 (1): Paper 25, 41, MR 2770130.
- ↑ Burstein, Alexander; Lankham, Isaiah (2010), "Restricted patience sorting and barred pattern avoidance", Permutation patterns, London Math. Soc. Lecture Note Ser., vol. 376, Cambridge: Cambridge Univ. Press, pp. 233–257, arXiv:math/0512122, doi:10.1017/CBO9780511902499.013, MR 2732833.
