Davenport–Schinzel sequence
संयोजन विज्ञान में, एक डेवनपोर्ट-श्चिन्ज़ेल अनुक्रम प्रतीकों का एक क्रम है जिसमें किसी भी दो प्रतीकों के बारी-बारी से प्रकट होने की संख्या सीमित होती है। डेवनपोर्ट-श्चिन्ज़ेल अनुक्रम की अधिकतम संभव लंबाई इसके विशिष्ट प्रतीकों की संख्या से घिरी होती है जिसे एक छोटे लेकिन गैर-स्थिर कारक से गुणा किया जाता है जो अनुमत परिवर्तनों की संख्या पर निर्भर करता है। डेवनपोर्ट-श्चिन्ज़ेल अनुक्रमों को पहली बार 1965 में हेरोल्ड डेवनपोर्ट और आंद्रेज़ श्चिन्ज़ेल द्वारा रैखिक अंतर समीकरणों का विश्लेषण करने के लिए परिभाषित किया गया था। इन अनुक्रमों और उनकी लंबाई सीमा का पालन करना भी असतत ज्यामिति और ज्यामितीय एल्गोरिदम के विश्लेषण में एक मानक उपकरण बन गया है। परिभाषा एक परिमित अनुक्रम U = u1, u2, u3, को क्रम s का डेवनपोर्ट-श्चिन्ज़ेल अनुक्रम कहा जाता है यदि यह निम्नलिखित दो गुणों को संतुष्ट करता हैः अनुक्रम में कोई भी दो क्रमिक मान एक दूसरे के बराबर नहीं हैं। यदि अनुक्रम में आने वाले दो अलग-अलग मान x और y हैं, तो अनुक्रम में एक अनुक्रम. x,. y,., x,., y, नहीं होता है जिसमें x और y के बीच बारी-बारी से s + 2 मान होते हैं। उदाहरण के लिए, अनुक्रम 1,2,1,3,1,3,2,4,5,5,2,3 क्रम 3 का एक डेवनपोर्ट-श्चिन्ज़ेल अनुक्रम हैः इसमें लंबाई चार के बारी-बारी से अनुक्रम होते हैं, जैसे. 1,. 2,. 1,. 2,. (जो पूरे अनुक्रम के अनुक्रम के रूप में चार अलग-अलग तरीकों से दिखाई देता है) लेकिन इसमें लंबाई पांच के कोई वैकल्पिक अनुक्रम नहीं होते हैं। यदि क्रम s के डेवनपोर्ट-श्चिन्ज़ेल अनुक्रम में n विशिष्ट मान शामिल हैं, तो इसे एक (n, s) डेवनपोर्ट-श्चिन्ज़ेल अनुक्रम, या एक DS (n, s)-अनुक्रम कहा जाता है। लंबाई की सीमा DS (n, s)-अनुक्रम की जटिलता का विश्लेषण इस सीमा में असिम्प्टोटिक रूप से किया गया है क्योंकि n अनंत तक जाता है, इस धारणा के साथ कि s एक निश्चित स्थिरांक है, और लगभग तंग सीमाएँ सभी s के लिए जानी जाती हैं। मान लीजिए कि λs (n) सबसे लंबे DS (n, s)-अनुक्रम की लंबाई को दर्शाता है। λs पर ज्ञात सर्वोत्तम सीमाओं में व्युत्क्रम एकरमैन फलन α (n) = न्यूनतम {m। A (m, m) ≤ n} शामिल है, जहाँ A एकरमैन फलन है। एकरमैन फलन के बहुत तेजी से विकास के कारण, इसका व्युत्क्रम α बहुत धीरे-धीरे बढ़ता है, और किसी भी व्यावहारिक आकार की समस्याओं के लिए अधिकतम चार होता है। बिग ओ और बिग θ संकेतन का उपयोग करते हुए, निम्नलिखित सीमाएँ ज्ञात हैंः .. .. .. इस जटिलता को रेखा खंडों द्वारा 2 के कारक के भीतर महसूस किया जा सकता हैः समतल में n रेखा खंडों की व्यवस्था मौजूद है जिनके निचले लिफाफों में जटिलता ω (nα (n)) होती है। .. .. s ≤ 6 के सम और विषम दोनों मानों के लिए, जहाँ। λs (n) का मान तब भी ज्ञात होता है जब s परिवर्तनीय होता है लेकिन n एक छोटा स्थिरांक होता हैः जब s, n का फलन होता है तो डेवनपोर्ट-श्चिन्ज़ेल अनुक्रमों पर ऊपरी और निचली सीमाएँ तंग नहीं होती हैं। कब, और। कब,। कब,। एक वास्तविक चर x के कार्यों के एक समूह का निचला लिफाफा उनके बिंदुवार न्यूनतम द्वारा दिया गया फलन हैः f (x) = मिनी (x)। मान लीजिए कि ये कार्य विशेष रूप से अच्छी तरह से व्यवहार किए जाते हैंः वे सभी निरंतर हैं, और उनमें से कोई भी दो अधिकतम s मानों पर बराबर हैं। इन धारणाओं के साथ, वास्तविक रेखा को सीमित रूप से कई अंतरालों में विभाजित किया जा सकता है जिसके भीतर एक फलन के मान अन्य सभी कार्यों की तुलना में छोटे होते हैं। प्रत्येक अंतराल के भीतर न्यूनतम फलन द्वारा लेबल किए गए इन अंतरालों का अनुक्रम, क्रम s का एक डेवनपोर्ट-श्चिन्ज़ेल अनुक्रम बनाता है। इस प्रकार, इस क्रम के डेवनपोर्ट-श्चिन्ज़ेल अनुक्रम की जटिलता पर कोई भी ऊपरी सीमा भी निचले लिफाफे के इस प्रतिनिधित्व में अंतराल की संख्या को सीमित करती है। डेवनपोर्ट और शिन्ज़ेल के मूल अनुप्रयोग में, विचाराधीन फलन क्रम s के एक ही सजातीय रैखिक विभेदक समीकरण के लिए विभिन्न समाधानों का एक समूह था। किसी भी दो अलग-अलग समाधानों में अधिक से अधिक s मान समान हो सकते हैं, इसलिए n अलग-अलग समाधानों के एक समूह का निचला लिफाफा एक DS (n, s)-अनुक्रम बनाता है। एक निचले लिफाफे की समान अवधारणा को उन कार्यों पर भी लागू किया जा सकता है जो केवल टुकड़ों में निरंतर होते हैं या जिन्हें केवल वास्तविक रेखा के अंतराल पर परिभाषित किया जाता है; हालाँकि, इस मामले में, कार्यों के असंतुलन के बिंदु और अंतराल के अंतिम बिंदु जिनके भीतर प्रत्येक कार्य को परिभाषित किया जाता है, अनुक्रम के क्रम में जोड़ते हैं। उदाहरण के लिए, समतल में एक गैर-ऊर्ध्वाधर रेखा खंड की व्याख्या एक फलन के ग्राफ के रूप में की जा सकती है जो x मानों के अंतराल को उनके संबंधित y मानों के साथ मानचित्रित करता है, और रेखा खंडों के संग्रह का निचला लिफाफा क्रम तीन का डेवनपोर्ट-श्चिन्ज़ेल अनुक्रम बनाता है क्योंकि कोई भी दो रेखा खंड अधिकतम चार लंबाई के साथ एक वैकल्पिक अनुक्रम बना सकते हैं। स्क्वायरफ्री शब्द नोट्स संदर्भ भी देखें। .. .. .. .. .. .. .. .. .. .. .. .. .. .. मैथवर्ल्ड से बाहरी लिंक डेवनपोर्ट-श्चिन्ज़ेल सीक्वेंस। डेवनपोर्ट-श्चिन्ज़ेल सीक्वेंसेस, स्टीवन एम. लावाले की पुस्तक मोशन प्लानिंग का एक भाग है। शब्दों पर अनुक्रम और श्रृंखला संयोजन विविक्त ज्यामिति