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

साहचर्य गणित में, समुच्चय {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वीं शताब्दी में डेसिरे आंद्रे द्वारा किया गया था।

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

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

परिभाषाएँ

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

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

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

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

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

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

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

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

सभी n ≥ 1 के लिए, आंद्रे (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 के लिए,

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

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

$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)$.

N^th ज़िगज़ैग संख्या प्रवेशकर्ता संख्या E(n, n) के बराबर है।

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

छेदक संख्याएँ सूत्र E_2n = (−1)ⁿA_2n द्वारा हस्ताक्षरित यूलर संख्याओं (अतिपरवलयिक छेदक के टेलर गुणांक) से ($En=0$ जब n विषम है) संबंधित हैं।

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

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

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

$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)$ दूसरी तरह की स्टर्लिंग संख्या को दर्शाता है।

यह भी देखें

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

संदर्भ

• 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