आंशिक क्रमपरिवर्तन: Difference between revisions
No edit summary |
No edit summary |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
[[ साहचर्य ]] गणित में, परिमित [[सबसेट|समुच्चय]] | [[ साहचर्य | साहचर्य]] गणित में, परिमित [[सबसेट|समुच्चय]] ''S'' पर एक आंशिक [[परिवर्तन|क्रम परिवर्तन]] या पुनरावृत्ति के बिना अनुक्रम, ''S'' के दो निर्दिष्ट उपसमूहों के बीच एक आक्षेप है। यही है, यह समान आकार के दो उपसमुच्चय ''U'' और ''V'' द्वारा परिभाषित किया गया है, और ''U'' से ''V'' तक एक-से-एक प्रतिचित्रण है। समतुल्य रूप से, यह 'S' पर आंशिक फलन है जिसे क्रमपरिवर्तन तक बढ़ाया जा सकता है।<ref>{{citation | ||
| last = Straubing | first = Howard | | last = Straubing | first = Howard | ||
| doi = 10.1016/0012-365X(83)90164-4 | | doi = 10.1016/0012-365X(83)90164-4 | ||
| Line 24: | Line 24: | ||
== प्रतिनिधित्व == | == प्रतिनिधित्व == | ||
उस विषय पर विचार करना सामान्य है जब समुच्चय S मात्र प्रथम n पूर्णांकों का समुच्चय {1, 2, ..., n} है। इस विषय में, एक आंशिक क्रमपरिवर्तन को n प्रतीकों के एक [[स्ट्रिंग (कंप्यूटर विज्ञान)]] द्वारा दर्शाया जा सकता है, जिनमें से कुछ 1 से लेकर श्रेणी में विशिष्ट संख्याएं | उस विषय पर विचार करना सामान्य है जब समुच्चय S मात्र प्रथम n पूर्णांकों का समुच्चय {1, 2, ..., n} है। इस विषय में, एक आंशिक क्रमपरिवर्तन को n प्रतीकों के एक [[स्ट्रिंग (कंप्यूटर विज्ञान)|स्ट्रिंग(कंप्यूटर विज्ञान)]] द्वारा दर्शाया जा सकता है, जिनमें से कुछ 1 से लेकर श्रेणी में विशिष्ट संख्याएं <math>n</math> हैं और जिनमें से शेष एक विशेष छिद्र प्रतीक ◊ हैं। इस सूत्रीकरण में, आंशिक क्रमपरिवर्तन के फलन U के प्रांत में स्ट्रिंग में स्थिति होती है जिसमें छिद्र नहीं होता है, और ऐसी प्रत्येक स्थिति को उस स्थिति में संख्या में प्रतिचित्रित किया जाता है। उदाहरण के लिए, स्ट्रिंग 1 ◊ 2 आंशिक क्रमपरिवर्तन का प्रतिनिधित्व करेगा जो 1 को स्वयं से प्रतिचित्रित करता है और 3 से 2 को प्रतिचित्रित करता है।<ref name="cjjk">{{citation | ||
| last1 = Claesson | first1 = Anders | | last1 = Claesson | first1 = Anders | ||
| last2 = Jelínek | first2 = Vít | | last2 = Jelínek | first2 = Vít | ||
| Line 51: | Line 51: | ||
यह निम्नानुसार निर्धारित किया जाता है: | यह निम्नानुसार निर्धारित किया जाता है: | ||
#<math>P(n-1)</math> आंशिक क्रमपरिवर्तन जहां प्रत्येक समुच्चय के अंतिम अवयव छोड़े जाते हैं: | #<math>P(n-1)</math> आंशिक क्रमपरिवर्तन जहां प्रत्येक समुच्चय के अंतिम अवयव छोड़े जाते हैं: | ||
#<math>P(n-1)</math> आंशिक क्रमपरिवर्तन जहां प्रत्येक समुच्चय के अंतिम अवयव एक दूसरे को | #<math>P(n-1)</math> आंशिक क्रमपरिवर्तन जहां प्रत्येक समुच्चय के अंतिम अवयव एक दूसरे को प्रतिचित्रित करते हैं। | ||
#<math>(n-1)P(n-1)</math> आंशिक क्रमपरिवर्तन जहां पूर्व समुच्चय का अंतिम अवयव सम्मिलित है, परन्तु दूसरे समुच्चय के अंतिम अवयव को | #<math>(n-1)P(n-1)</math> आंशिक क्रमपरिवर्तन जहां पूर्व समुच्चय का अंतिम अवयव सम्मिलित है, परन्तु दूसरे समुच्चय के अंतिम अवयव को प्रतिचित्रित नहीं करता है | ||
#<math>(n-1)P(n-1)</math> आंशिक क्रमपरिवर्तन जहां दूसरे समुच्चय का अंतिम अवयव सम्मिलित है, परन्तु पूर्व समुच्चय के अंतिम अवयव को | #<math>(n-1)P(n-1)</math> आंशिक क्रमपरिवर्तन जहां दूसरे समुच्चय का अंतिम अवयव सम्मिलित है, परन्तु पूर्व समुच्चय के अंतिम अवयव को प्रतिचित्रित नहीं करता है | ||
#<math>-(n-1)^2P(n-2)</math>, 3 और 4 दोनों में सम्मिलित आंशिक क्रमपरिवर्तन, वे क्रमपरिवर्तन जहां दोनों समुच्चय के अंतिम अवयव सम्मिलित हैं, परन्तु एक दूसरे के लिए | #<math>-(n-1)^2P(n-2)</math>, 3 और 4 दोनों में सम्मिलित आंशिक क्रमपरिवर्तन, वे क्रमपरिवर्तन जहां दोनों समुच्चय के अंतिम अवयव सम्मिलित हैं, परन्तु एक दूसरे के लिए प्रतिचित्रित नहीं करते हैं। | ||
== प्रतिबंधित आंशिक क्रमपरिवर्तन == | == प्रतिबंधित आंशिक क्रमपरिवर्तन == | ||
| Line 70: | Line 70: | ||
| volume = 376 | | volume = 376 | ||
| year = 2010| arxiv = math/0512122 | | year = 2010| arxiv = math/0512122 | ||
}}.</ref> या सीमा<ref name="cjjk"/>कुछ k के लिए, n पदों के समुच्चय में प्रथम k पदों को सम्मिलित करने के लिए आपत्ति को अत्यावश्यक किया जाता है। पूर्व विषय में, n-समुच्चय से लंबाई k का आंशिक क्रमपरिवर्तन बिना दोहराव के n-समुच्चय से k शब्दों का एक क्रम है। (प्रारंभिक साहचर्य में, इन पदों को कभी-कभी | }}.</ref> या सीमा<ref name="cjjk"/>कुछ k के लिए, n पदों के समुच्चय में प्रथम k पदों को सम्मिलित करने के लिए आपत्ति को अत्यावश्यक किया जाता है। पूर्व विषय में, n-समुच्चय से लंबाई k का आंशिक क्रमपरिवर्तन बिना दोहराव के n-समुच्चय से k शब्दों का एक क्रम है।(प्रारंभिक साहचर्य में, इन पदों को कभी-कभी अस्पष्टतः रूप से n-समुच्चय के k-क्रमपरिवर्तन कहा जाता है।) | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist}} | {{reflist}} | ||
[[Category:Created On 02/03/2023]] | [[Category:Created On 02/03/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:कार्य और मानचित्रण]] | |||
[[Category:साहचर्य]] | |||
Latest revision as of 09:37, 14 March 2023
साहचर्य गणित में, परिमित समुच्चय 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.
