बिज़ली द्वारा दिए गए जाली पथ गणना के बारे में पुनरावृत्ति संबंध का प्रत्यक्ष प्रमाण क्या है?
लश्कर $k$ एक अप्रतिष्ठित पूर्णांक और होने दो $m,n$नकल सकारात्मक पूर्णांक हो। लश्कर$\phi_k$ से जाली मार्गों की संख्या हो $(0,0)$ सेवा मेरे $(km,kn)$ कदमों के साथ $(0,1)$ तथा $(1,0)$ जो कभी भी लाइन से ऊपर नहीं उठ रहे हैं $my=nx$। इस संपत्ति वाले मार्ग को a कहा जाएगा$\phi$-पथ। फिर,$\phi_k$ पुनरावृत्ति संबंध को संतुष्ट करता है $$ k(m+n)\phi_k = \sum_{j=1}^{k}\binom{j(m+n)}{jm}\phi_{k-j} $$ सभी के लिए $k \in \mathbb{Z}^+$, जैसा कि बिज़ली (1954) द्वारा दिखाया गया है ।
बिज़ली ने कहा है कि "इन संबंधों को पथ के ज्यामितीय गुणों से सामान्य तर्क द्वारा सीधे घटाया जा सकता है"। हालाँकि, मैं इस प्रमेय का एक स्पष्ट प्रमाण प्राप्त करने का प्रबंधन नहीं कर सका।
प्रश्न: ऊपर वर्णित पुनरावृत्ति संबंध का प्रत्यक्ष प्रमाण क्या है?
इस संबंध के बारे में मेरा पहला विचार यह था कि समीकरण का बायाँ भाग सभी के चक्रीय क्रमांकनों की संख्या को गिनता है $\phi$-पथ से $(0,0)$ सेवा मेरे $(km,kn)$। अपने पेपर में, बिज़ली एक जाली मार्ग के उच्चतम बिंदु को "एक जाली बिंदु" के रूप में परिभाषित करता है$X$ पथ पर ऐसा है कि ढाल की रेखा $\frac{n}{m}$ के माध्यम से $X$ के मूल्य पर y- अक्ष काटता है $y$पथ के किसी भी अन्य जाली बिंदु से संबंधित उससे कम नहीं ”। (यह ध्यान रखना महत्वपूर्ण है कि पहला बिंदु$(0,0)$ पथ से संबंधित नहीं माना जाता है।) इस प्रकार, सभी के चक्रीय क्रमपरिवर्तन की संख्या $\phi$-पैसों के योग के रूप में व्यक्त किया जा सकता है $t$ बिल्कुल साथ सभी जाली रास्तों की संख्या $t$ सभी के लिए उच्चतम अंक $t=1,2,\ldots,k$। हालांकि, स्पष्ट रूप से समीकरण के दाहिने हाथ की ओर निर्दिष्ट अंकों की संख्या के साथ जाली रास्तों की संख्या के साथ कुछ नहीं करना है।
मुझे डर है कि मुझे ज्यामितीय गुणों के बारे में कुछ स्पष्ट याद आ रहा है $\phi$-पैथ्स और मुझे बहुत खुशी होगी अगर कोई एक कॉम्बीनेटरियल प्रूफ या ट्रिक प्रदान कर सकता है जिसे मैं देखने का प्रबंधन नहीं कर सकता। अग्रिम में आपके ध्यान के लिए धन्यवाद।
जवाब
चाल जोड़ना है $\phi_k$समीकरण के दोनों किनारों पर, और बाएं हाथ की ओर की व्याख्या एक पूर्वनिर्मित क्षैतिज चरण के साथ पथों के रूप में की जाती है, और इसके एक चरण को चिह्नित किया गया है। फिर, चिह्नित चरण को किसी पथ से पहला चरण बनाएं$(-1, 0)$ सेवा मेरे $(km, kn)$। लश्कर$j$ कम से कम ऐसा हो कि यह रास्ता हिट हो $(jm, jn)$ और नीचे रहता है $my = nx$इसके बाद। फिर बैठक बिंदु से पहले के कदम, अंतिम क्षैतिज कदम को छोड़कर, सूचकांक के साथ सम्मन में द्विपदीय गुणांक द्वारा गिना गया एक मनमाना मार्ग बनाते हैं।$j$, और बचे हुए चरणों के द्वारा गिना एक पथ बनाते हैं $\phi_{k-j}$।