Distributions of Inversions and Descents over Integer Compositions

तकनीकी सारांश: पूर्णांक संरचनाओं (Integer Compositions) पर व्युत्क्रमण (Inversions) और अवरोहण (Descents) के वितरण

समस्या विवरण
यह शोध पत्र पूर्णांक संरचनाओं (integer compositions) के गणन पर केंद्रित है, विशेष रूप से इन पर लागू दो मौलिक क्रमचय सांख्यिकी (permutation statistics)—व्युत्क्रमण (inversions) और अवरोहण (descents)—के वितरण पर। एक $n$ के लिए $k$-संरचना (k-composition) को धनात्मक पूर्णांकों के एक क्रमित $k$-टुपल (ordered $k$-tuple) के रूप में परिभाषित किया गया है जिनका योग $n$ है। जबकि पिछले साहित्य (जैसे, Heubach et al., Knopfmacher et al.) ने विशिष्ट मामलों के लिए जनरेटिंग फंक्शन या व्युत्क्रमण गणनाओं के लिए साहचर्य व्यवहार (asymptotic behaviors) स्थापित किए थे, यह कार्य सामान्य मामलों के लिए स्पष्ट जनरेटिंग फंक्शन प्राप्त करने का लक्ष्य रखता है:

1. $r$ व्युत्क्रमों वाले $n$ के $k$-संरचनाओं की संख्या ($icr(n, k)$)।
2. $d$ अवरोहणों वाले $n$ के $k$-संरचनाओं की संख्या ($dcr(n, k)$)।
3. संगत एकचर (univariate) मामले जहाँ $k$ अनिर्धारित है ($icr(n)$और$dcr(n)$)।

कार्यप्रणाली
मुख्य दृष्टिकोण $k$-संरचनाओं ($C_k$) के सेट और एक क्रमचय ($\pi \in S_k$) एवं एक पूर्णांक विभाजन ($\lambda$) के युग्म के बीच एक द्वैत मैपिंग (bijective mapping) पर आधारित है। यह द्वैत (bijection), जो मैकमैहोन (MacMahon) द्वारा प्रतिपादित है, एक संरचना $\sigma$ को एक अद्वितीय क्रमचय $\pi$ और एक विभाजन $\lambda$ के साथ जोड़ता है ताकि:
$$|\sigma| = |\lambda| + \text{maj}(\pi)$$
जहाँ $|\cdot|$ भागों का योग है और $\text{maj}$ मेजर इंडेक्स (major index) है।

लेखक इस द्वैत का उपयोग यह प्रदर्शित करने के लिए करते हैं कि संरचनाओं पर सांख्यिकी सीधे संबंधित क्रमचयों के संगत सांख्यिकी द्वारा कूटबद्ध (encoded) होती है। विशेष रूप से:

• एक संरचना $\sigma$ का व्युत्क्रमण संख्या, संबद्ध क्रमचय $\pi$ की व्युत्क्रमण संख्या के अनुरूप होती है।
• एक संरचना $\sigma$ का अवरोहण संख्या, $\pi$ के व्युत्क्रम क्रमचय $\pi^{-1}$ (या फोआटा द्वैत (Foata bijection) के माध्यम से $\pi$ के मेजर इंडेक्स के समतुल्य) के अवरोहण संख्या से संबंधित होती है।
• एक संरचना $\sigma$ का को-मेजर इंडेक्स (comajor index), $\pi$ के व्युत्क्रम मेजर इंडेक्स के अनुरूप होता है।

सममित समूह $S_k$ पर संयुक्त सांख्यिकी—विशेष रूप से $(\text{maj}, \text{inv})$ और $(\text{inv}, \text{des})$ के वितरण—के ज्ञात जनरेटिंग फंक्शनों का उपयोग करते हुए, यह शोध पत्र इन परिणामों को संरचनाओं के जनरेटिंग फंक्शन में परिवर्तित करता है। इसका व्युत्पत्ति मानक $q$-एनालॉग नोटेशन, गॉसियन द्विपद गुणांक (Gaussian binomial coefficients), और शू फंक्शन (Schur functions) का उपयोग करता है।

प्रमुख योगदान और परिणाम

1. व्युत्क्रमों के लिए सामान्य जनरेटिंग फंक्शन:
   शोध पत्र $r$ व्युत्क्रमों वाले $n$ के $k$-संरचनाओं की संख्या के लिए एक द्विचरीय (bivariate) जनरेटिंग फंक्शन व्युत्पन्न करता है। प्रमेय 10 स्थापित करता है कि $C_k$ पर व्युत्क्रमों का वितरण $S_k$ पर $(\text{maj}, \text{inv})$ के वितरण से संबंधित है।

• अनुवर्ती 11 (Corollary 11) $f^\lambda(p)f^\lambda(q)$ वाले विभाजनों $\lambda \vdash k$ पर आधारित योग के रूप में $f^\lambda(q)$ (जो आकार $\lambda$ के मानक यंग टेबलू की संख्या का $q$-एनालॉग है) के पदों में स्पष्ट जनरेटिंग फंक्शन $IC_q(p, k)$ प्रदान करता है।
• $IC_q(p, k)$ के लिए एक पुनरावृत्ति संबंध (recurrence relation) भी दिया गया है, जो सभी विभाजनों को योग किए बिना गुणांकों की गणना करने की अनुमति देता है।

2. अवरोहणों के लिए सामान्य जनरेटिंग फंक्शन:
   इसी प्रकार, शोध पत्र दिए गए अवरोहणों की संख्या के साथ $k$-संरचनाओं के लिए जनरेटिंग फंक्शन व्युत्पन्न करता है।

• अनुवर्ती 12 (Corollary 12) $q$-यूलरियन बहुपदों $A_k(q, t)$ का उपयोग करके $DC_t(q, k)$ को व्यक्त करता है, जो $S_k$ पर $(\text{inv}, \text{des})$ के वितरण का वर्णन करते हैं।
• परिणाम को $g_\lambda(q)$ सांख्यिकी वाले विभाजनों के योग के रूप में दिया गया है, जो अवरोहण सेटों द्वारा भारित (weighted) टेबलू की गणना करता है।

3. एकीकृत ढांचा (Unified Framework):
   यह शोध पत्र इन सांख्यिकीओं के उपचार को एकीकृत करता है यह दिखाते हुए कि $S_k$ के साथ द्वैत के माध्यम से व्यक्त की जाने वाली संरचनाओं की कोई भी सांख्यिकी का विश्लेषण क्रमचय सांख्यिकी के ज्ञात संयुक्त वितरणों का उपयोग करके किया जा सकता है। इसमें योग, मेजर इंडेक्स और अवरोहण संख्या का संयुक्त वितरण शामिल है।

4. स्पष्ट मान और OEIS संबंध:
   लेखक $n=16$ तक $icr(n)$और$dcr(n)$ के स्पष्ट मानों की गणना करते हैं और उन्हें सूचीबद्ध करते हैं, जो मौजूदा OEIS प्रविष्टियों (A189074, A238343, A238344) के अनुरूप डेटा प्रदान करते हैं।

महत्व
यह शोध पत्र मुख्य रूप से उन स्पष्ट अभिव्यक्तियों को प्रदान करने की अपनी क्षमता के कारण महत्वपूर्ण होने का दावा करता है जो पहले केवल विशिष्ट मामलों के लिए ज्ञात थे या जिन्हें प्राप्त करने के लिए जटिल समावेश-अपवर्जन (inclusion-exclusion) सिद्धांतों की आवश्यकता थी। $S_k$ के साथ द्वैत के माध्यम से संरचना सांख्यिकी और क्रमचय सांख्यिकी के बीच एक सीधा संबंध स्थापित करके, यह कार्य इन जनरेटिंग फंक्शनों के व्युत्पत्ति को सरल बनाता है।

लेखक नोट करते हैं कि यद्यपि विभाजनों पर आधारित योगों से गुणांक निकालने की कम्प्यूटेशनल जटिलता $n$ के साथ तेजी से बढ़ती है, फिर भी यह विधि सभी $2^{n-1}$ संरचनाओं की ब्रूट-फोर्स गणना (brute-force enumeration) की तुलना में अधिक कुशल है। यह कार्य व्युत्क्रमण और अवरोहण के वितरण के लिए एक व्यापक संदर्भ के रूप में कार्य करता है, जो Heubach et al. और Knopfmacher et al. जैसे पिछले शोधकर्ताओं के नोटेशन और परिणामों को सामान्य $n, k,$ और $r$ तक विस्तारित करता है।