K-सममित अनुक्रम: Difference between revisions

From Vigyanwiki
No edit summary
 
(13 intermediate revisions by 4 users not shown)
Line 13: Line 13:


===रैखिक संयोजन===
===रैखिक संयोजन===
एक अनुक्रम s(n) k-नियमित है यदि सभी e के लिए एक पूर्णांक E मौजूद है<sub>''j''</sub> > ई और 0 ≤ आर<sub>''j''</sub> ≤ क<sup>e<sub>''j''</sub></sup> − 1, फॉर्म s(k) के s का प्रत्येक अनुवर्ती<sup>e<sub>''j''</sub></sup>n+r<sub>''j''</sub>) R'-[[रैखिक संयोजन]] के रूप में व्यक्त किया जा सकता है <math>\sum_{i} c_{ij} s(k^{f_{ij}}n + b_{ij})</math>, जहां सी<sub>''ij''</sub> एक पूर्णांक है, एफ<sub>''ij''</sub> ≤ ई, और 0 ≤ बी<sub>''ij''</sub> ≤ क<sup>f<sub>''ij''</sub></sup> - 1.<ref name=AS22>Allouche & Shallit (1992), Theorem 2.2.</ref>
एक अनुक्रम s(n) k-सममित है यदि सभी e के लिए पूर्णांक E उपस्थित है सभी e<sub>''j''</sub> > E और 0 ≤ r<sub>''j''</sub> ≤ k<sup>e<sub>''j''</sub></sup> − 1, s(k) के s<sup>e<sub>''j''</sub></sup>n+r<sub>''j''</sub>) का प्रत्येक अनुवर्ती निर्मित करता हैं R'-[[रैखिक संयोजन]] <math>\sum_{i} c_{ij} s(k^{f_{ij}}n + b_{ij})</math> के रूप में व्यक्त किया जा सकता है, जहां c<sub>''ij''</sub> एक पूर्णांक है, f<sub>''ij''</sub> ≤ E, और 0 ≤ b<sub>''ij''</sub> ≤ k<sup>f<sub>''ij''</sub></sup> - 1होता हैं।<ref name=AS22>Allouche & Shallit (1992), Theorem 2.2.</ref>
वैकल्पिक रूप से, एक अनुक्रम s(n) k-नियमित है यदि कोई पूर्णांक r और अनुवर्ती s मौजूद है<sub>1</sub>(एन), ..., एस<sub>''r''</sub>(n) ऐसा कि, सभी 1 ≤ i ≤ r और 0 ≤ a ≤ k − 1 के लिए, प्रत्येक अनुक्रम s<sub>''i''</sub>(kn + a) k-कर्नेल K में<sub>''k''</sub>(s) अनुवर्ती s का एक R′-रैखिक संयोजन है<sub>''i''</sub>(एन)।<ref name=AS22 />


वैकल्पिक रूप से, अनुक्रम s(n) k-सममित है यदि कोई पूर्णांक r और अनुवर्ती s<sub>1</sub>(n), ..., s<sub>''r''</sub>(n) उपस्थित हैं जैसे की, सभी 1 ≤ i ≤ r और 0 ≤ a ≤ k − 1 के लिए, प्रत्येक अनुक्रम s<sub>''i''</sub>(kn + a) k-कर्नेल K<sub>''k''</sub>(s) अनुवर्ती s<sub>''i''</sub>(n) का R′-रैखिक संयोजन है।<ref name="AS22" />


===औपचारिक शृंखला===
 
चलो एक्स<sub>0</sub>, ..., एक्स<sub>''k''&nbsp;−&nbsp;1</sub> k नॉन-कम्यूटिंग वेरिएबल्स का एक सेट बनें और τ को स्ट्रिंग x पर कुछ प्राकृतिक संख्या n भेजने वाला एक मानचित्र बनने दें<sub>''a''<sub>0</sub></उप>...एक्स उप>ए<sub>''e''&nbsp;−&nbsp;1</sub></sub>, जहां x का आधार-k प्रतिनिधित्व स्ट्रिंग a है<sub>''e''&nbsp;−&nbsp;1</sub>...ए<sub>0</sub>. तब एक अनुक्रम s(n) k-नियमित होता है यदि और केवल यदि [[औपचारिक शक्ति श्रृंखला]] हो <math>\sum_{n \geq 0} s(n) \tau (n)</math> है <math>\mathbb{Z}</math>-तर्कसंगत श्रृंखला.<ref name=AS43>Allouche & Shallit (1992), Theorem 4.3.</ref>
 
===प्रारूपिक श्रेणी ===
माना x<sub>0</sub>, ..., x<sub>''k''&nbsp;−&nbsp;1</sub> k अरूपांतरित चर का समुच्चय बनाया और τ को श्रृंखला x<sub>''a''<sub>0</sub> ... Xa<sub>''e''&nbsp;−&nbsp;1</sub></sub>पर कुछ प्राकृतिक संख्या n भेजने वाला मानचित्र बनाते हैं, जहां x का आधार-k प्रतिनिधित्व श्रृंखला a<sub>''e''−1</sub>...a<sub>0</sub> है। तब एक अनुक्रम s(n) k-सममित होता है यदि और केवल यदि [[औपचारिक शक्ति श्रृंखला|प्रारूपिक श्रेणी]] <math>\sum_{n \geq 0} s(n) \tau (n)</math> है <math>\mathbb{Z}</math>- परिमेय होती हैं।<ref name=AS43>Allouche & Shallit (1992), Theorem 4.3.</ref>




===ऑटोमेटा-सैद्धांतिक===
===ऑटोमेटा-सैद्धांतिक===
के-नियमित अनुक्रम की औपचारिक श्रृंखला परिभाषा मार्सेल-पॉल शुट्ज़ेनबर्गर | शुट्ज़ेनबर्गर की मैट्रिक्स मशीन के समान एक ऑटोमेटन लक्षण वर्णन की ओर ले जाती है।<ref name=AS44>Allouche & Shallit (1992), Theorem 4.4.</ref><ref>{{citation | last = Schützenberger | first = M.-P. | title = On the definition of a family of automata | journal = Information and Control | volume = 4 | issue = 2–3 | year = 1961 | pages = 245–270 | doi=10.1016/S0019-9958(61)80020-X | doi-access = free }}.</ref>
k-सममित अनुक्रम की प्रारूपिक श्रेणी शुट्ज़ेनबर्गर की आव्यूह मशीन के समान ऑटोमेटन लक्षण वर्णन की तरफ ले जाती है।<ref name=AS44>Allouche & Shallit (1992), Theorem 4.4.</ref><ref>{{citation | last = Schützenberger | first = M.-P. | title = On the definition of a family of automata | journal = Information and Control | volume = 4 | issue = 2–3 | year = 1961 | pages = 245–270 | doi=10.1016/S0019-9958(61)80020-X | doi-access = free }}.</ref>




==इतिहास==
==इतिहास==
के-नियमित अनुक्रमों की धारणा की जांच सबसे पहले अल्लोचे और शैलिट द्वारा पत्रों की एक जोड़ी में की गई थी।<ref name=AS>Allouche & Shallit (1992, 2003).</ref> इससे पहले, बर्स्टेल और रयूटेनॉयर ने तर्कसंगत श्रृंखला के सिद्धांत का अध्ययन किया था, जो कि के-नियमित अनुक्रमों से निकटता से संबंधित है।<ref>{{cite book | last1 = Berstel | first1 = Jean | last2 = Reutenauer | first2 = Christophe | title = तर्कसंगत श्रृंखला और उनकी भाषाएँ| volume = 12 | series = EATCS Monographs on Theoretical Computer Science | year = 1988 | isbn = 978-3-642-73237-9 | publisher = [[Springer Science+Business Media|Springer-Verlag]] }}</ref>
k-सममित अनुक्रमों की धारणा की जांच सबसे पहले अल्लोचे और शैलिट द्वारा पत्रों की एक जोड़ी में की गई थी।<ref name=AS>Allouche & Shallit (1992, 2003).</ref> इससे पहले, बर्स्टेल और रयूटेनॉयर ने परिमेय श्रृंखला के सिद्धांत का अध्ययन किया था, जो कि k-नियमित अनुक्रमों से निकटता से संबंधित है।<ref>{{cite book | last1 = Berstel | first1 = Jean | last2 = Reutenauer | first2 = Christophe | title = तर्कसंगत श्रृंखला और उनकी भाषाएँ| volume = 12 | series = EATCS Monographs on Theoretical Computer Science | year = 1988 | isbn = 978-3-642-73237-9 | publisher = [[Springer Science+Business Media|Springer-Verlag]] }}</ref>




Line 32: Line 34:


===रूलर अनुक्रम===
===रूलर अनुक्रम===
होने देना <math>s(n) = \nu_2(n+1)</math> पी-एडिक मूल्यांकन हो | <math>2</math>- का आदिक मूल्यांकन <math>n+1</math>. शासक क्रम <math>s(n)_{n \geq 0} = 0, 1, 0, 2, 0, 1, 0, 3, \dots</math> ({{OEIS2C|id=A007814}}) है <math>2</math>-नियमित, और <math>2</math>-कर्नेल
माना <math>s(n) = \nu_2(n+1)</math> <math>n+1</math> का '''2'''-अभिन्नकल्प मूल्यांकन होता हैं | रूलर अनुक्रम <math>s(n)_{n \geq 0} = 0, 1, 0, 2, 0, 1, 0, 3, \dots</math> ({{OEIS2C|id=A007814}}) <math>2</math>-सममित, और <math>2</math>-कर्नेल है
:<math>\{s(2^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq 2^e - 1\}</math>
:<math>\{s(2^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq 2^e - 1\}</math>
द्वारा उत्पन्न द्वि-आयामी वेक्टर स्थान में समाहित है <math>s(n)_{n \geq 0}</math> और निरंतर क्रम <math>1, 1, 1, \dots</math>. ये आधार तत्व पुनरावृत्ति संबंधों की ओर ले जाते हैं
द्वारा उत्पन्न द्वि-आयामी सदिश समष्टि में समाहित है <math>s(n)_{n \geq 0}</math> और निरंतर क्रम <math>1, 1, 1, \dots</math>होता हैं। ये आधार अवयव पुनरावृत्ति संबंधों की तरफ ले जाते हैं
:<math>
:<math>
\begin{align}
\begin{align}
Line 42: Line 44:
\end{align}
\end{align}
</math>
</math>
जो, प्रारंभिक शर्तों के साथ <math>s(0) = 0</math> और <math>s(1) = 1</math>, अनुक्रम को विशिष्ट रूप से निर्धारित करें।<ref name=ASe8>Allouche & Shallit (1992), Example 8.</ref>
जो, प्रारंभिक स्थितियों <math>s(0) = 0</math> और <math>s(1) = 1</math> के साथ, अनुक्रम को विशिष्ट रूप से निर्धारित ककरता हैं।<ref name=ASe8>Allouche & Shallit (1992), Example 8.</ref>




===गुरु-मोर्स अनुक्रम===
===थ्यु-मोर्स अनुक्रम===
थ्यू-मोर्स अनुक्रम t(n) ({{OEIS2C|id=A010060}}) रूपवाद 0 → 01, 1 → 10 का [[निश्चित बिंदु (गणित)]] है। यह ज्ञात है कि थ्यू-मोर्स अनुक्रम 2-स्वचालित है। इस प्रकार, यह 2-नियमित भी है, और इसका 2-कर्नेल भी है
थ्यू-मोर्स अनुक्रम t(n) ({{OEIS2C|id=A010060}}) रूपवाद 0 → 01, 1 → 10 का [[निश्चित बिंदु (गणित)]] है। यह ज्ञात है कि थ्यू-मोर्स अनुक्रम 2-स्वचालित है। इस प्रकार, यह भी 2-सममित है, और इसका भी 2-कर्नेल है
:<math>\{t(2^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq 2^e - 1\}</math>
:<math>\{t(2^e n + r)_{n \geq 0} : e \geq 0 \text{ and } 0 \leq r \leq 2^e - 1\}</math>
अनुवर्ती से मिलकर बनता है <math>t(n)_{n \geq 0}</math> और <math>t(2 n + 1)_{n \geq 0}</math>.
अनुवर्ती <math>t(n)_{n \geq 0}</math> और <math>t(2 n + 1)_{n \geq 0}</math> से मिलकर बनता है।


===कैंटर संख्या===
===कैंटर संख्या===
[[कैंटर सेट]] का क्रम c(n) ({{OEIS2C|id=A005823}}) में वे संख्याएँ शामिल होती हैं जिनके [[टर्नरी अंक प्रणाली]] विस्तार में कोई 1 नहीं होता है। यह दिखाना सीधा है
[[कैंटर सेट|कैंटर संख्याओं]] का क्रम c(n) ({{OEIS2C|id=A005823}}) में वे संख्याएँ सम्मलित होती हैं जिनके [[टर्नरी अंक प्रणाली]] विस्तार में कोई 1s नहीं होता है। यह सीधे तरह से दिखाया जा सकता हैं
:<math>
:<math>
\begin{align}
\begin{align}
Line 58: Line 60:
\end{align}
\end{align}
</math>
</math>
और इसलिए कैंटर संख्याओं का क्रम 2-नियमित है। इसी प्रकार [[स्टेनली अनुक्रम]]
और इसलिए कैंटर संख्याओं का क्रम 2-सममित है। इसी प्रकार [[स्टेनली अनुक्रम]]
:0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... {{OEIS|A005836}}
:0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... {{OEIS|A005836}}
उन संख्याओं की संख्या जिनके त्रिक विस्तार में कोई 2s नहीं है, वह भी 2-नियमित है।<ref name=ASe3>Allouche & Shallit (1992), Examples 3 and 26.</ref>
उन संख्याओं की संख्या जिनके त्रिक विस्तार में कोई 2s नहीं है, वह भी 2-सममित है।<ref name=ASe3>Allouche & Shallit (1992), Examples 3 and 26.</ref>




===संख्याओं को क्रमबद्ध करना===
===संख्याओं को क्रमबद्ध करना===
एल्गोरिदम के व्यापक अध्ययन के लिए के-नियमितता की धारणा का कुछ दिलचस्प अनुप्रयोग [[ मर्ज़ सॉर्ट ]] एल्गोरिदम के विश्लेषण में पाया जाता है। एन मानों की एक सूची को देखते हुए, मर्ज सॉर्ट एल्गोरिदम द्वारा की गई तुलनाओं की संख्या सॉर्टिंग संख्याएं हैं, जो पुनरावृत्ति संबंध द्वारा नियंत्रित होती हैं
एल्गोरिदम(कलन विधि) के व्यापक अध्ययन के लिए k-सममितता की धारणा का कुछ अच्छे अनुप्रयोग[[ मर्ज़ सॉर्ट ]]एल्गोरिदम(कलन विधि) के विश्लेषण में पाया जाता है। n मानों की सूची को देखते हुए, मर्ज सॉर्ट एल्गोरिदम(कलन विधि) द्वारा की गई तुलनाओं की संख्या सॉर्टिंग संख्याएं हैं, जो पुनरावृत्ति संबंध द्वारा नियंत्रित होती हैं
:<math>
:<math>
\begin{align}
\begin{align}
Line 71: Line 73:
\end{align}
\end{align}
</math>
</math>
परिणामस्वरूप, मर्ज सॉर्ट, टी(एन) के लिए पुनरावृत्ति संबंध द्वारा परिभाषित अनुक्रम, 2-नियमित अनुक्रम का गठन करता है।<ref name=ASe28>Allouche & Shallit (1992), Example 28.</ref>
परिणामस्वरूप, मर्ज सॉर्ट, T(n) के लिए पुनरावृत्ति संबंध द्वारा परिभाषित अनुक्रम, 2-सममित अनुक्रम का गठन करता है।<ref name=ASe28>Allouche & Shallit (1992), Example 28.</ref>




===अन्य अनुक्रम===
===अन्य अनुक्रम===
अगर <math>f(x)</math> तो, एक [[पूर्णांक-मूल्यवान बहुपद]] है <math>f(n)_{n \geq 0}</math> प्रत्येक के लिए k-नियमित है <math>k \geq 2</math>.
यदि <math>f(x)</math>, एक [[पूर्णांक-मूल्यवान बहुपद|पूर्णांक-मान बहुपद]] है तो <math>f(n)_{n \geq 0}</math> प्रत्येक <math>k \geq 2</math> के लिए k-सममित है।


गोल्ड का अनुक्रम|ग्लेशर-गोल्ड अनुक्रम 2-नियमित है। स्टर्न-ब्रोकॉट अनुक्रम 2-नियमित है।
ग्लेशर-गोल्ड अनुक्रम 2-सममित है। स्टर्न-ब्रोकॉट अनुक्रम 2-सममित है।


अल्लोचे और शैलिट अपने पेपर में के-रेगुलर अनुक्रमों के कई अतिरिक्त उदाहरण देते हैं।<ref name=AS />
अल्लोचे और शैलिट अपने पेपर में k-रेगुलर अनुक्रमों के कई अतिरिक्त उदाहरण देते हैं।<ref name=AS />




==गुण==
==गुण==
के-नियमित अनुक्रम कई दिलचस्प गुण प्रदर्शित करते हैं।
k-नियमित अनुक्रम कई अच्छे गुण प्रदर्शित करते हैं।
*प्रत्येक स्वचालित अनुक्रम|k-स्वचालित अनुक्रम k-नियमित है।<ref>Allouche & Shallit (1992), Theorem 2.3.</ref>
*प्रत्येक k-स्वचालित अनुक्रम k-सममित है।<ref>Allouche & Shallit (1992), Theorem 2.3.</ref>
*प्रत्येक k-सिंक्रोनाइज़्ड अनुक्रम|k-सिंक्रोनाइज़्ड अनुक्रम k-नियमित है।
*प्रत्येक k-सिंक्रोनाइज़्ड अनुक्रम k-सममित है।
*एक k-नियमित अनुक्रम सीमित रूप से कई मान लेता है यदि और केवल यदि यह k-स्वचालित है।<ref name=AS441>Allouche & Shallit (2003) p. 441.</ref> यह k-नियमित अनुक्रमों के वर्ग का k-स्वचालित अनुक्रमों के वर्ग का सामान्यीकरण होने का तात्कालिक परिणाम है।
*k-सममित अनुक्रम सीमित रूप से कई मान लेता है यदि और केवल यदि यह k-स्वचालित है।<ref name=AS441>Allouche & Shallit (2003) p. 441.</ref> यह k-नियमित अनुक्रमों के वर्ग का k-स्वचालित अनुक्रमों के वर्ग का सामान्यीकरण होने का तात्कालिक परिणाम है।
*के-रेगुलर अनुक्रमों का वर्ग टर्मवाइज जोड़, टर्मवाइज गुणन और [[कनवल्शन]] के तहत बंद है। के-नियमित अनुक्रमों का वर्ग भी अनुक्रम के प्रत्येक पद को एक पूर्णांक λ द्वारा स्केल करने के तहत बंद किया जाता है।<ref name=AS441 /><ref>Allouche & Shallit (1992), Theorem 2.5.</ref><ref>Allouche & Shallit (1992), Theorem 3.1.</ref><ref name=AS445>Allouche & Shallit (2003) p. 445.</ref> विशेष रूप से, के-नियमित पावर श्रृंखला का सेट एक रिंग बनाता है।<ref>Allouche and Shallit (2003) p. 446.</ref>
*k-सममित अनुक्रमों का वर्ग सिमा रूप से जोड़, सिमा रूप से गुणन और संवलन के अनुसार बंद है। k-नियमित अनुक्रमों का वर्ग भी अनुक्रम के प्रत्येक पद को पूर्णांक λ द्वारा मापने के अनुसार बंद किया जाता है।<ref name=AS441 /><ref>Allouche & Shallit (1992), Theorem 2.5.</ref><ref>Allouche & Shallit (1992), Theorem 3.1.</ref><ref name=AS445>Allouche & Shallit (2003) p. 445.</ref> विशेष रूप से, k-सममित घात श्रृंखला के समुच्चय का वलय बनाता है।<ref>Allouche and Shallit (2003) p. 446.</ref>
*अगर <math>s(n)_{n \ge 0}</math> k-नियमित है, तो सभी पूर्णांकों के लिए <math>m \ge 1</math>, <math>(s(n) \bmod{m})_{n \ge 0}</math> k-स्वचालित है. हालाँकि, बातचीत कायम नहीं है।<ref>Allouche and Shallit (2003) p. 441.</ref> *गुणात्मक रूप से स्वतंत्र k, l ≥ 2 के लिए, यदि कोई अनुक्रम k-नियमित और l-नियमित दोनों है, तो अनुक्रम एक रैखिक पुनरावृत्ति को संतुष्ट करता है।<ref>{{cite journal | first=J. | last=Bell | title=नियमित अनुक्रमों के लिए कोबम के प्रमेय का सामान्यीकरण| journal=Séminaire Lotharingien de Combinatoire | volume=54A | year=2006 }}</ref> यह उन अनुक्रमों के संबंध में कोबम के कारण परिणाम का सामान्यीकरण है जो के-स्वचालित और एल-स्वचालित दोनों हैं।<ref>{{cite journal | first=A. | last=Cobham | title=परिमित ऑटोमेटा द्वारा पहचाने जाने योग्य संख्याओं के सेट की आधार-निर्भरता पर| journal=Math. Systems Theory | volume=3 | issue=2 | year=1969 | pages=186–192 | doi=10.1007/BF01746527 | s2cid=19792434 }}</ref>
*यदि <math>s(n)_{n \ge 0}</math> k-सममित है, तो सभी पूर्णांकों <math>m \ge 1</math>, <math>(s(n) \bmod{m})_{n \ge 0}</math> के लिए k-स्वचालित है। यद्यपि की, परिवर्तन नहीं हो पता हैं।<ref>Allouche and Shallit (2003) p. 441.</ref>  
*पूर्णांकों के k-नियमित अनुक्रम का nवाँ पद n में अधिकतम बहुपद रूप से बढ़ता है।<ref>Allouche & Shallit (1992) Theorem 2.10.</ref>
**गुणात्मक रूप से स्वतंत्र k, l ≥ 2 के लिए, यदि कोई अनुक्रम k-सममित और ''l''-सममित दोनों है, तो अनुक्रम रैखिक पुनरावृत्ति को संतुष्ट करता है।<ref>{{cite journal | first=J. | last=Bell | title=नियमित अनुक्रमों के लिए कोबम के प्रमेय का सामान्यीकरण| journal=Séminaire Lotharingien de Combinatoire | volume=54A | year=2006 }}</ref> यह उन अनुक्रमों के संबंध में कोबम के कारण परिणाम का सामान्यीकरण है जो k-स्वचालित और ''l''-स्वचालित दोनों हैं।<ref>{{cite journal | first=A. | last=Cobham | title=परिमित ऑटोमेटा द्वारा पहचाने जाने योग्य संख्याओं के सेट की आधार-निर्भरता पर| journal=Math. Systems Theory | volume=3 | issue=2 | year=1969 | pages=186–192 | doi=10.1007/BF01746527 | s2cid=19792434 }}</ref>
*अगर <math>F</math> एक क्षेत्र है और <math>x \in F</math>, फिर शक्तियों का क्रम <math>(x^n)_{n \ge 0}</math> k-नियमित है यदि और केवल यदि <math>x = 0</math> या <math>x</math> एकता की जड़ है.<ref>Allouche and Shallit (2003) p. 444.</ref>
*पूर्णांकों के k-सममित अनुक्रम का nवाँ पद n में अधिकतम बहुपद रूप से बढ़ता है।<ref>Allouche & Shallit (1992) Theorem 2.10.</ref>
*यदि <math>F</math> क्षेत्र है और <math>x \in F</math>, फिर घातों का क्रम <math>(x^n)_{n \ge 0}</math> k-सममित है यदि और केवल यदि <math>x = 0</math> या <math>x</math> इकाई के मूल है।<ref>Allouche and Shallit (2003) p. 444.</ref>




==के-नियमितता को सिद्ध और असिद्ध करना==
==के-सममितता को सिद्ध और असिद्ध करना==
एक उम्मीदवार अनुक्रम दिया गया <math>s = s(n)_{n \ge 0}</math> इसे k-नियमित नहीं माना जाता है, k-नियमितता को आम तौर पर कर्नेल के तत्वों की गणना करके सीधे परिभाषा से सिद्ध किया जा सकता है <math>s</math> और यह सिद्ध करना कि प्रपत्र के सभी तत्व <math>(s(k^r n + e))_{n \ge 0}</math> साथ <math>r</math> पर्याप्त रूप से बड़ा और <math>0 \le e < 2^r</math> के स्थान पर छोटे घातांक वाले कर्नेल तत्वों के रैखिक संयोजन के रूप में लिखा जा सकता है <math>r</math>. यह आमतौर पर कम्प्यूटेशनल रूप से सीधा है।
एक पदानवेशी अनुक्रम <math>s = s(n)_{n \ge 0}</math> दिया गया हैं इसे k-सममित नहीं माना जाता है, k-सममितता को साधारण तौर पर कर्नेल <math>s</math> के अवयवों की गणना करके सीधे परिभाषा से सिद्ध किया जा सकता है और यह सिद्ध करना कि प्रपत्र के सभी अवयव <math>(s(k^r n + e))_{n \ge 0}</math> साथ <math>r</math> पर्याप्त रूप से बड़ा और <math>0 \le e < 2^r</math> के स्थान पर छोटे घातांक वाले कर्नेल <math>r</math> अवयवों के रैखिक संयोजन के रूप में लिखा जा सकता है। यह साधारण तौर पर अभिकलनीय रूप से स्पस्ट है।


दूसरी ओर, उम्मीदवार अनुक्रम की k-नियमितता को अस्वीकार करना <math>s</math> आमतौर पर एक का उत्पादन करने की आवश्यकता होती है <math>\mathbb{Z}</math>-के कर्नेल में रैखिक रूप से स्वतंत्र उपसमुच्चय <math>s</math>, जो आम तौर पर पेचीदा है। ऐसे प्रमाण का एक उदाहरण यहां दिया गया है।
दूसरी ओर, पदानवेशी अनुक्रम की k-सममितता <math>s</math> को अस्वीकार करना करता हैं, साधारण तौर पर <math>\mathbb{Z}</math>-के कर्नेल में रैखिक रूप से स्वतंत्र उपसमुच्चय <math>s</math> के उत्पादन करने की आवश्यकता होती है, जो साधारण तौर पर जटिल है। ऐसे प्रमाण का उदाहरण यहां दिया गया है।


होने देना <math>e_0(n)</math> की संख्या को निरूपित करें <math>0</math>के द्विआधारी विस्तार में है <math>n</math>. होने देना <math>e_1(n)</math> की संख्या को निरूपित करें <math>1</math>के द्विआधारी विस्तार में है <math>n</math>. क्रम <math>f(n) := e_0(n)-e_1(n)</math> 2-नियमित दिखाया जा सकता है। क्रम <math>g = g(n) := |f(n)|</math> हालाँकि, निम्नलिखित तर्क के अनुसार, 2-नियमित नहीं है। कल्पना करना <math>(g(n))_{n \ge 0}</math> 2-नियमित है. हम दावा करते हैं कि तत्व <math>g(2^k n)</math> के लिए <math>n \ge 1</math> और <math>k \ge 0</math> के 2-कर्नेल का <math>g</math> पर रैखिक रूप से स्वतंत्र हैं <math>\mathbb{Z}</math>. कार्यक्रम <math>n \mapsto e_0(n)-e_1(n)</math> पूर्णांकों पर विशेषण है, तो चलिए <math>x_m</math> ऐसा सबसे छोटा पूर्णांक बनें <math>e_0(x_m)-e_1(x_m) = m</math>. 2-नियमितता से <math>(g(n))_{n \ge 0}</math>, वहां है <math>b \ge 0</math> और स्थिरांक <math>c_i</math> ऐसा कि प्रत्येक के लिए <math>n \ge 0</math>,
माना <math>e_0(n)</math> की संख्या <math>0's</math> को बाइनरी विस्तार <math>n</math> में निरूपित करते हैं। माना <math>e_1(n)</math> <math>1's</math> की संख्या को बाइनरी विस्तार <math>n</math> में निरूपित करते हैं। क्रम <math>f(n) := e_0(n)-e_1(n)</math> 2-सममित दिखाया जा सकता है। यद्यपि की क्रम <math>g = g(n) := |f(n)|</math>, निम्नलिखित तर्क के अनुसार, 2-सममित नहीं है। कल्पना किया की <math>(g(n))_{n \ge 0}</math> 2-सममित है। हम दावा करते हैं कि अवयव <math>g(2^k n)</math> के लिए <math>n \ge 1</math> और <math>k \ge 0</math> के 2-कर्नेल का <math>g</math>, <math>\mathbb{Z}</math> पर रैखिक रूप से स्वतंत्र हैं। फलन <math>n \mapsto e_0(n)-e_1(n)</math> पूर्णांकों पर विशेषण है, तो चलिए <math>x_m</math> ऐसा <math>e_0(x_m)-e_1(x_m) = m</math> सबसे छोटा पूर्णांक बनता हैं। 2-सममितता से <math>(g(n))_{n \ge 0}</math>, वहां <math>b \ge 0</math> और स्थिरांक <math>c_i</math> ऐसा कि प्रत्येक के लिए <math>n \ge 0</math> हैं,
:<math>\sum_{0 \le i \le b} c_i g(2^i n) = 0.</math>
:<math>\sum_{0 \le i \le b} c_i g(2^i n) = 0.</math>
होने देना <math>a</math> जिसके लिए न्यूनतम मूल्य हो <math>c_a \ne 0</math>. फिर हर एक के लिए <math>n \ge 0</math>,
माना <math>a</math> जिसके लिए न्यूनतम मान हो <math>c_a \ne 0</math>. फिर प्रत्येक के लिए <math>n \ge 0</math>,
:<math>g(2^a n) = \sum_{a+1 \le i \le b} -(c_i/c_a) g(2^i n).</math>
:<math>g(2^a n) = \sum_{a+1 \le i \le b} -(c_i/c_a) g(2^i n).</math>
इस अभिव्यक्ति का मूल्यांकन पर <math>n = x_m</math>, कहाँ <math>m = 0,-1,1,2,-2</math> और इसी तरह क्रमिक रूप से, हम बायीं ओर प्राप्त करते हैं
इस अभिव्यक्ति का मूल्यांकन पर <math>n = x_m</math>, जहाँ <math>m = 0,-1,1,2,-2</math> और इसी तरह क्रमिक रूप से, हम बायीं ओर प्राप्त करते हैं
:<math>g(2^a x_m) = |e_0(x_m)-e_1(x_m)+a| = |m+a|,</math>
:<math>g(2^a x_m) = |e_0(x_m)-e_1(x_m)+a| = |m+a|,</math>
और दाहिनी ओर,
और दाहिनी ओर,
:<math>\sum_{a+1 \le i \le b} -(c_i/c_a)|m+i|.</math>
:<math>\sum_{a+1 \le i \le b} -(c_i/c_a)|m+i|.</math>
यह प्रत्येक पूर्णांक के लिए इसका अनुसरण करता है <math>m</math>,
यह प्रत्येक पूर्णांक <math>m</math> के लिए इसका अनुसरण करता है,
:<math>|m+a| = \sum_{a+1 \le i \le b} -(c_i/c_a) |m+i|.</math>
:<math>|m+a| = \sum_{a+1 \le i \le b} -(c_i/c_a) |m+i|.</math>
लेकिन के लिए <math>m \ge -a-1</math>, समीकरण का दाहिना भाग नीरस है क्योंकि यह फॉर्म का है <math>Am+B</math> कुछ स्थिरांक के लिए <math>A,B</math>, जबकि बाईं ओर नहीं है, जैसा कि क्रमिक रूप से प्लग इन करके जांचा जा सकता है <math>m = -a-1</math>, <math>m = -a</math>, और <math>m = -a+1</math>. इसलिए, <math>(g(n))_{n \ge 0}</math> 2-नियमित नहीं है.<ref>Allouche and Shallit (1993) p. 168–169.</ref>
लेकिन <math>m \ge -a-1</math> के लिए, समीकरण का दाहिना भाग नगण्य है क्योंकि यह <math>Am+B</math> कुछ स्थिरांक के लिए <math>A,B</math> प्रकार का है, जबकि बाईं ओर नहीं है, जैसा कि क्रमिक रूप <math>m = -a-1</math>, <math>m = -a</math>, और <math>m = -a+1</math> से प्लग इन करके जांचा जा सकता है इसलिए, <math>(g(n))_{n \ge 0}</math> 2-सममित  नहीं है।<ref>Allouche and Shallit (1993) p. 168–169.</ref>




Line 119: Line 122:
*{{citation | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | title = The ring of ''k''-regular sequences, II | journal = Theoret. Comput. Sci. | volume = 307 | year = 2003 | pages = 3–29 | doi=10.1016/s0304-3975(03)00090-2| doi-access = free }}.
*{{citation | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | title = The ring of ''k''-regular sequences, II | journal = Theoret. Comput. Sci. | volume = 307 | year = 2003 | pages = 3–29 | doi=10.1016/s0304-3975(03)00090-2| doi-access = free }}.
*{{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = [[Cambridge University Press]] | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}
*{{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = [[Cambridge University Press]] | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}
[[Category: शब्दों पर संयोजकता]] [[Category: ऑटोमेटा (गणना)]] [[Category: पूर्णांक क्रम]] [[Category: पुनरावृत्ति संबंध]]


[[Category: Machine Translated Page]]
[[Category:Created On 03/07/2023]]
[[Category:Created On 03/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with ignored display titles]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:ऑटोमेटा (गणना)]]
[[Category:पुनरावृत्ति संबंध]]
[[Category:पूर्णांक क्रम]]
[[Category:शब्दों पर संयोजकता]]

Latest revision as of 19:34, 21 July 2023

गणित और सैद्धांतिक कंप्यूटर विज्ञान में, k-सममित अनुक्रम रैखिक पुनरावृत्ति समीकरणों को संतुष्ट करने वाला अनुक्रम है जो पूर्णांकों के आधार-k निरूपण को परावर्तित करता हैं। k-सममित अनुक्रमों का वर्ग स्वचालित अनुक्रम के वर्ग को अनंत आकार के अक्षरों में सामान्यीकृत करता है|

परिभाषा

k-सममित अनुक्रमों के कई लक्षण उपस्थित हैं, जो सभी समतुल्य हैं। कुछ सामान्य लक्षण इस प्रकार हैं। प्रत्येक के लिए, हम R' को क्रमविनिमेय नोथेरियन वलय के रूप में लेते हैं और हम R को R' युक्त वलय (गणित) के रूप में लेते हैं।

k-कर्नेल

माना k ≥ 2. अनुक्रम का k-कर्नेल अनुवर्ती का समुच्चय है