पुनरावृत्ति संबंध

एक पुनरावृत्ति संबंध एक अनुक्रम के प्रत्येक पद को पहले के पदों के संदर्भ में परिभाषित करता है, और जनक फलन (generating functions) बंद-रूप समाधानों (closed-form solutions) के लिए एक व्यवस्थित मार्ग प्रदान करते हैं।

Definition

एक पुनरावृत्ति संबंध एक समीकरण है जो एक अनुक्रम के प्रत्येक पद को एक या अधिक पूर्ववर्ती पदों के फलन के रूप में व्यक्त करता है, साथ ही प्रारंभिक शर्तों के साथ जो अनुक्रम को विशिष्ट रूप से निर्धारित करती हैं।

Scope

यह विषय स्थिर गुणांकों वाले रैखिक पुनरावृत्तियों और उनके अभिलक्षणिक-समीकरण (characteristic-equation) समाधानों, फाइबोनैचि और कैटलन पुनरावृत्तियों, डिवाइड-एंड-कॉन्कर (divide-and-conquer) पुनरावृत्तियों, और जनक-फलन विधि (generating-function method) को शामिल करता है जो एक पुनरावृत्ति को एक बीजगणितीय समीकरण में परिवर्तित करती है। यह प्रारंभिक गणना और वृद्धि दरों के विश्लेषणात्मक अध्ययन के बीच सेतु का काम करता है।

Core questions

• एक अनुक्रम को पहले के पदों और प्रारंभिक मानों से पुनरावर्ती रूप से कैसे परिभाषित किया जाता है?
• अभिलक्षणिक समीकरण स्थिर गुणांकों के साथ एक रैखिक पुनरावृत्ति को कैसे हल करता है?
• जनक फलन एक पुनरावृत्ति को एक हल करने योग्य बीजगणितीय समीकरण में कैसे परिवर्तित करते हैं?
• डिवाइड-एंड-कॉन्कर पुनरावृत्तियाँ एल्गोरिथम के चलने के समय का वर्णन कैसे करती हैं?

Key concepts

• स्थिर गुणांकों के साथ रैखिक पुनरावृत्ति
• अभिलक्षणिक समीकरण
• फाइबोनैचि संख्याएँ
• कैटलन संख्याएँ
• डिवाइड-एंड-कॉन्कर पुनरावृत्तियाँ
• जनक-फलन समाधान

Key theories

अभिलक्षणिक-समीकरण विधि

स्थिर गुणांकों के साथ एक रैखिक पुनरावृत्ति को उसके अभिलक्षणिक बहुपद (characteristic polynomial) के मूलों को ज्ञात करके हल किया जाता है; सामान्य समाधान उन मूलों और प्रारंभिक शर्तों द्वारा निर्धारित घातीय पदों का एक संयोजन होता है।

जनक-फलन समाधान

एक पुनरावृत्ति को एक औपचारिक चर से गुणा करना और योग करना इसे जनक फलन के लिए एक बीजगणितीय समीकरण में बदल देता है, जिसका विस्तार अनुक्रम के लिए एक बंद रूप देता है, जैसा कि कैटलन और फाइबोनैचि संख्याओं के लिए होता है।

Clinical relevance

पुनरावृत्ति संबंध पुनरावर्ती एल्गोरिदम (recursive algorithms) के चलने के समय का वर्णन करते हैं, जहाँ डिवाइड-एंड-कॉन्कर पुनरावृत्तियाँ और मास्टर प्रमेय जटिलता की सीमाएँ देते हैं, और वे असतत गतिशील और जनसंख्या प्रक्रियाओं को मॉडल करते हैं।

History

फाइबोनैचि की 13वीं सदी की खरगोश समस्या ने पुरातन पुनरावृत्ति को जन्म दिया; डी मोइवर और यूलर ने जनक-फलन और अभिलक्षणिक-मूल (characteristic-root) विधियों का विकास किया जो मानक समाधान तकनीकें बनी हुई हैं।

Key figures

• Leonardo of Pisa (Fibonacci)
• Abraham de Moivre
• Eugene Catalan

Seminal works

• stanley2011

Frequently asked questions

कैटलन संख्याएँ क्या हैं?

कैटलन संख्याएँ कई संयोजनात्मक वस्तुओं - संतुलित कोष्ठक, त्रिकोणीयकरण (triangulations), बाइनरी ट्री - की गणना करती हैं और एक द्विघात पुनरावृत्ति को संतुष्ट करती हैं जिसे जनक फलनों द्वारा हल करके एक बंद द्विपद रूप प्राप्त किया जा सकता है।

पुनरावृत्तियों को हल करने के लिए जनक फलनों का उपयोग क्यों करें?

वे पुनरावर्ती समीकरणों के एक अनंत परिवार को एक एकल बीजगणितीय समीकरण में परिवर्तित करते हैं, जिससे प्रत्येक पद के लिए एक बंद-रूप व्यंजक एक साथ निकाला जा सकता है।