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

साहचर्य गणित में, समुच्चय ${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,...$ (ओईआईएस में अनुक्रम 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,...$ (ओईआईएस में अनुक्रम A000364) हैं।

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

तदनुसार, विषम सूचकांकों वाली संख्या A_2n+1 को स्पर्शरेखा संख्या या ज़ैग संख्या कहा जाता है। पहले कुछ मान 1, 2, 16, 272, 7936, ... (ओईआईएस में अनुक्रम 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