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

Not to be confused with the alternating group.

साहचर्य गणित में, सेट {1, 2, 3, ..., n} का एक वैकल्पिक क्रमचय (या ज़िगज़ैग क्रमपरिवर्तन) उन संख्याओं का एक क्रमचय (व्यवस्था) है ताकि प्रत्येक प्रविष्टि वैकल्पिक रूप से अधिक या कम हो पिछली प्रविष्टि की तुलना में। उदाहरण के लिए, {1, 2, 3, 4} के पाँच वैकल्पिक क्रमपरिवर्तन हैं:

• 1, 3, 2, 4        क्योंकि       1 <3> 2 <4,
• 1, 4, 2, 3        क्योंकि       1 < 4 > 2 < 3,
• 2, 3, 1, 4        क्योंकि       2 <3> 1 < 4,
• 2, 4, 1, 3        क्योंकि       2 <4> 1 <3, और
• 3, 4, 1, 2        क्योंकि       3 <4> 1 <2।

इस प्रकार के क्रमचय का अध्ययन पहली बार 19वीं शताब्दी में डेसिरे आंद्रे द्वारा किया गया था। अलग-अलग लेखक अल्टरनेटिंग परमिटेशन शब्द का उपयोग थोड़ा अलग तरीके से करते हैं: कुछ के लिए आवश्यक है कि एक अल्टरनेटिंग परमुटेशन में दूसरी प्रविष्टि पहले से बड़ी होनी चाहिए (जैसा कि ऊपर के उदाहरणों में है), अन्य के लिए यह आवश्यक है कि प्रत्यावर्तन को उलट दिया जाए (ताकि दूसरी प्रविष्टि छोटी हो जाए) पहले की तुलना में, फिर तीसरा दूसरे से बड़ा, और इसी तरह), जबकि अन्य दोनों प्रकारों को वैकल्पिक क्रमपरिवर्तन के नाम से पुकारते हैं।

संख्या ए का निर्धारण_n समुच्चय {1, ..., n} के वैकल्पिक क्रमपरिवर्तनों की संख्या को 'आंद्रे की समस्या' कहा जाता है। नंबर ए_n यूलर नंबर, ज़िगज़ैग नंबर या अप/डाउन नंबर के रूप में जाने जाते हैं। जब n सम संख्या A हो_n एक छेदक संख्या के रूप में जाना जाता है, जबकि यदि n विषम है तो इसे स्पर्शरेखा संख्या के रूप में जाना जाता है। ये बाद वाले नाम अनुक्रम के लिए जनरेटिंग फ़ंक्शन के अध्ययन से आते हैं।

परिभाषाएँ

एक क्रमपरिवर्तन c₁, ..., c_n को वैकल्पिक कहा जाता है यदि इसकी प्रविष्टियाँ वैकल्पिक रूप से उठती और उतरती हैं। इस प्रकार, पहली और आखिरी के अलावा प्रत्येक प्रविष्टि अपने दोनों पड़ोसियों की तुलना में या तो बड़ी या छोटी होनी चाहिए। कुछ लेखक केवल अप-डाउन क्रमपरिवर्तन को संदर्भित करने के लिए वैकल्पिक शब्द का उपयोग करते हैं जिसके लिए c₁ < c₂ > c₃ < ..., संतुष्ट करने वाले डाउन-अप क्रमपरिवर्तनों को कॉल करना c₁ > c₂ < c₃ > ... रिवर्स अल्टरनेटिंग नाम से। अन्य लेखक इस सम्मेलन को उलट देते हैं, या ऊपर-नीचे और नीचे-ऊपर क्रमपरिवर्तन दोनों को संदर्भित करने के लिए वैकल्पिक शब्द का उपयोग करते हैं।

नीचे-ऊपर और ऊपर-नीचे क्रमचय के बीच एक-से-एक पत्राचार एक सरल आपत्ति है: प्रत्येक प्रविष्टि की जगह c_i साथ n + 1 - c_i प्रविष्टियों के सापेक्ष क्रम को उलट देता है।

प्रथा के अनुसार, किसी भी नामकरण योजना में लंबाई 0 (खाली सेट का क्रमचय) और 1 (एकल प्रविष्टि 1 से युक्त क्रमचय) के अद्वितीय क्रमपरिवर्तन को वैकल्पिक रूप से लिया जाता है।

आंद्रे का प्रमेय

बर्नोली (1742) में ज़िगज़ैग नंबर, ओपेरा ओम्निया वॉल्यूम। 4, पृ. 105

संख्या ए का निर्धारण_n समुच्चय {1, ..., n} के वैकल्पिक क्रमपरिवर्तनों की संख्या को एंड्रे की समस्या कहा जाता है। नंबर ए_n विभिन्न प्रकार से यूलर नंबर, ज़िगज़ैग नंबर, अप/डाउन नंबर, या इन नामों के कुछ संयोजनों के रूप में जाने जाते हैं। विशेष रूप से यूलर संख्या नाम का प्रयोग कभी-कभी निकट से संबंधित अनुक्रम के लिए किया जाता है। ए के पहले कुछ मान_n हैं 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (sequence A000111 in the OEIS).

ये संख्याएँ कैटलन संख्याओं के समान एक सरल पुनरावृत्ति को संतुष्ट करती हैं: सेट { 1, 2, 3, ..., n, n + के वैकल्पिक क्रमपरिवर्तन (दोनों डाउन-अप और अप-डाउन) के सेट को विभाजित करके 1} सबसे बड़ी प्रविष्टि की स्थिति k के अनुसार n + 1, कोई यह दिखा सकता है

$2A_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}A_{k}A_{n-k}$

सभी के लिए n ≥ 1. André (1881) ने इस पुनरावृत्ति का उपयोग चरघातांकी जनक फलन से संतुष्ट अवकल समीकरण देने के लिए किया

$A(x)=\sum _{n=0}^{\infty }A_{n}{\frac {x^{n}}{n!}}$

अनुक्रम के लिए A_n. वास्तव में, पुनरावृत्ति देता है:

$2\sum _{n\geq 1}A_{n+1}{\frac {x^{n+1}}{(n+1)!}}=\sum _{n\geq 1}\sum _{k=0}^{n}{\frac {A_{k}}{k!}}{\frac {A_{n-k}}{(n-k)!}}{\frac {x^{n+1}}{n+1}}=\int \left(\sum _{k\geq 0}A_{k}{\frac {x^{k}}{k!}}\right)\left(\sum _{j\geq 0}A_{j}{\frac {x^{j}}{j!}}\right)\,dx-x$

जहां हम स्थानापन्न करते हैं $j=n-k$ और ${\frac {x^{n+1}}{n+1}}=\int x^{k+j}\,dx$. यह अभिन्न समीकरण देता है

$2(A(x)-1-x)=\int A(x)^{2}\,dx-x,$

जो विभेदन के बाद बन जाता है $2{\frac {dA}{dx}}-2=A^{2}-1$. इस अंतर समीकरण को चरों को अलग करके (प्रारंभिक स्थिति का उपयोग करके) हल किया जा सकता है $A(0)=A_{0}/0!=1$), और अंतिम परिणाम देते हुए स्पर्शरेखा अर्ध-कोण सूत्र का उपयोग करके सरलीकृत किया गया

$A(x)=\tan \left({\frac {\pi }{4}}+{\frac {x}{2}}\right)=\sec x+\tan x$,

त्रिकोणमितीय कार्यों का योग#पारस्परिक कार्य और स्पर्शरेखा (त्रिकोणमिति) कार्य। इस परिणाम को आंद्रे प्रमेय के रूप में जाना जाता है।

यह आंद्रे के प्रमेय से अनुसरण करता है कि श्रृंखला के अभिसरण की त्रिज्या A(x) हैπ/2. यह किसी को स्पर्शोन्मुख विस्तार की गणना करने की अनुमति देता है

$A_{n}\sim 2\left({\frac {2}{\pi }}\right)^{n+1}n!\,.$

संबंधित पूर्णांक अनुक्रम

विषम-अनुक्रमित ज़िगज़ैग संख्याएँ (यानी, स्पर्शरेखा संख्याएँ) बर्नौली संख्याओं से निकटता से संबंधित हैं। संबंध सूत्र द्वारा दिया गया है

$B_{2n}=(-1)^{n-1}{\frac {2n}{4^{2n}-2^{2n}}}A_{2n-1}$

n > 0 के लिए।

अगर जेड_n {1, ..., n} के क्रमपरिवर्तनों की संख्या को दर्शाता है जो या तो ऊपर-नीचे या नीचे-ऊपर (या दोनों, n <2 के लिए) हैं, तो यह ऊपर दिए गए जोड़े से Z का अनुसरण करता है_n = कोई_n n ≥ 2 के लिए। Z के पहले कुछ मान_n हैं 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... (sequence A001250 in the OEIS).

यूलर टेढ़ी-मेढ़ी संख्याएं एंट्रिंगर संख्या से संबंधित हैं, जिससे टेढ़ी-मेढ़ी संख्या की गणना की जा सकती है। प्रवेशक संख्याओं को पुनरावर्ती रूप से निम्नानुसार परिभाषित किया जा सकता है:

$E(0,0)=1$

$E(n,0)=0\qquad {\mbox{for }}n>0$

$E(n,k)=E(n,k-1)+E(n-1,n-k)$.

तब^th टेढ़ी मेढ़ी संख्या प्रवेशकर्ता संख्या E(n, n) के बराबर है।

नंबर ए_2n सम सूचकांकों के साथ को छेदक संख्या या ज़िग संख्या कहा जाता है: चूंकि छेदक फलन सम फलन है और स्पर्शरेखा विषम फलन है, यह ऊपर एंड्रे के प्रमेय से अनुसरण करता है कि वे मैकलॉरिन श्रृंखला के अंश हैं sec x. पहले कुछ मान 1, 1, 5, 61, 1385, 50521, ... (sequence A000364 in the OEIS).

छेदक संख्याएँ सूत्र E द्वारा हस्ताक्षरित यूलर संख्याओं (अतिशयोक्तिपूर्ण छेदक के टेलर गुणांक) से संबंधित हैं_2n = (−1)^{एन</सुप>ए_2n. (और_n= 0 जब n विषम हो।)}

तदनुसार, संख्या ए_2n+1 विषम सूचकांकों के साथ स्पर्शरेखा संख्याएँ या ज़ैग संख्याएँ कहलाती हैं। पहले कुछ मान 1, 2, 16, 272, 7936, ... (sequence A000182 in the OEIS).

दूसरी तरह की स्टर्लिंग संख्याओं के संदर्भ में स्पष्ट सूत्र

यूलर टेढ़ी-मेढ़ी संख्या का यूलर संख्या के साथ संबंध, और बर्नौली संख्या का उपयोग निम्नलिखित को सिद्ध करने के लिए किया जा सकता है

$A_{r}=-{\frac {4^{r}}{a_{r}}}\sum _{k=1}^{r}{\frac {(-1)^{k}\,S(r,k)}{k+1}}\left({\frac {3}{4}}\right)^{(k)}$

कहाँ

$a_{r}={\begin{cases}(-1)^{\frac {r-1}{2}}(1+2^{-r})&{\mbox{if r is odd}}\\(-1)^{\frac {r}{2}}&{\mbox{if r is even}}\end{cases}},$

$(x)^{(n)}=(x)(x+1)\cdots (x+n-1)$ गिरने और बढ़ते फैक्टोरियल को दर्शाता है, और $S(r,k)$ दूसरी तरह की स्टर्लिंग संख्या को दर्शाता है।

यह भी देखें

• सबसे लंबे समय तक बारी-बारी से
• Boustrophedon रूपांतरण
• बाड़ (गणित), एक आंशिक रूप से आदेशित सेट जिसमें इसके रैखिक विस्तार के रूप में वैकल्पिक क्रमपरिवर्तन हैं

संदर्भ

• André, Désiré (1879), "Développements de séc x et de tang x", Comptes rendus de l'Académie des sciences, 88: 965–967.

• André, Désiré (1881), "Sur les permutations alternées" (PDF), Journal de mathématiques pures et appliquées, 3e série, 7: 167–184, archived from the original (PDF) on November 22, 2021.

• Henry, Philippe; Wanner, Gerhard (2019). "Zigzags with Bürgi, Bernoulli, Euler and the Seidel–Entringer–Arnol'd triangle". Elemente der Mathematik. 74 (4): 141–168. doi:10.4171/EM/393..

• Stanley, Richard P. (2011). Enumerative Combinatorics. Vol. I (2nd ed.). Cambridge University Press.

बाहरी संबंध

• Weisstein, Eric W. "Alternating Permutation". MathWorld.
• Ross Tang, "An Explicit Formula for the Euler zigzag numbers (Up/down numbers) from power series" A simple explicit formula for A_n.
• "A Survey of Alternating Permutations", a preprint by Richard P. Stanley