डेलानॉय नंबर: Difference between revisions

From Vigyanwiki
No edit summary
Line 9: Line 9:
गणित में, एक '''डेलानॉय संख्या''' <math>D</math> एक आयताकार ग्रिड के दक्षिण-पश्चिम कोण (0, 0) से उत्तर-पूर्व कोण (''m'', ''n'')) तक पथों की संख्या का वर्णन करता है, जिसमें उत्तर, उत्तर-पूर्व या पूर्व में केवल एक ही चरण का उपयोग किया जाता है। डेलानॉय नंबरों का नाम फ्रांसीसी सेना अधिकारी और अनुभवहीन गणितज्ञ [[हेनरी डेलानॉय]] के नाम पर रखा गया है।<ref>{{citation |last1=Banderier |first1=Cyril |last2=Schwer |first2=Sylviane |title=Why Delannoy numbers? |year=2005 |journal=Journal of Statistical Planning and Inference |volume=135 |issue=1 |pages=40–54 |arxiv=math/0411128 |doi=10.1016/j.jspi.2005.02.004|s2cid=16226115 |mr = 2202337}}</ref>
गणित में, एक '''डेलानॉय संख्या''' <math>D</math> एक आयताकार ग्रिड के दक्षिण-पश्चिम कोण (0, 0) से उत्तर-पूर्व कोण (''m'', ''n'')) तक पथों की संख्या का वर्णन करता है, जिसमें उत्तर, उत्तर-पूर्व या पूर्व में केवल एक ही चरण का उपयोग किया जाता है। डेलानॉय नंबरों का नाम फ्रांसीसी सेना अधिकारी और अनुभवहीन गणितज्ञ [[हेनरी डेलानॉय]] के नाम पर रखा गया है।<ref>{{citation |last1=Banderier |first1=Cyril |last2=Schwer |first2=Sylviane |title=Why Delannoy numbers? |year=2005 |journal=Journal of Statistical Planning and Inference |volume=135 |issue=1 |pages=40–54 |arxiv=math/0411128 |doi=10.1016/j.jspi.2005.02.004|s2cid=16226115 |mr = 2202337}}</ref>


डेलानॉय संख्या <math> D(m,n) </math> लंबाई <math>m</math> और <math>n</math> के दो अनुक्रमों के वैश्विक संरेखण की संख्या की भी गणना करती है, <ref>{{citation |last=Covington |first=Michael A. |year=2004 |title=The number of distinct alignments of two strings |journal=Journal of Quantitative Linguistics |volume=11 |issue=3 |pages=173–182 |doi=10.1080/0929617042000314921|s2cid=40549706 }}</ref> <math>m</math>-आयामी [[पूर्णांक जाली|पूर्णांक लैटिस]] या [[क्रॉस पॉलीटोप]] में बिंदुओं की संख्या जो मूल से अधिकतम ''n'' चरण पर होते हैं,<ref>{{citation
डेलानॉय संख्या <math> D(m,n) </math> लंबाई <math>m</math> और <math>n</math> के दो अनुक्रमों के वैश्विक संरेखण की संख्या की भी गणना करती है, <ref>{{citation |last=Covington |first=Michael A. |year=2004 |title=The number of distinct alignments of two strings |journal=Journal of Quantitative Linguistics |volume=11 |issue=3 |pages=173–182 |doi=10.1080/0929617042000314921|s2cid=40549706 }}</ref> <math>m</math>-आयामी [[पूर्णांक जाली|पूर्णांक लैटिस]] या [[क्रॉस पॉलीटोप]] में बिंदुओं की संख्या जो मूल से अधिकतम ''n'' चरण पर होते हैं,<ref>{{citation
  | last1 = Luther | first1 = Sebastian
  | last1 = Luther | first1 = Sebastian
  | last2 = Mertens | first2 = Stephan
  | last2 = Mertens | first2 = Stephan
Line 97: Line 97:
इस सरणी में, पहली पंक्ति की सभी संख्याएँ एक हैं, दूसरी पंक्ति की संख्याएँ [[विषम संख्या]]एँ हैं, तीसरी पंक्ति की संख्याएँ [[केन्द्रित वर्ग संख्या]]एँ हैं, और चौथी पंक्ति की संख्याएँ [[केन्द्रित अष्टफलकीय संख्या]]एँ हैं। वैकल्पिक रूप से, समान संख्याओं को पास्कल त्रिकोण के सदृश एक [[त्रिकोणीय सरणी]] में व्यवस्थित किया जा सकता है, जिसे ट्राइबोनाची त्रिकोण भी कहा जाता है,<ref>{{Cite OEIS|A008288|name=Square array of Delannoy numbers D(i,j) (i >= 0, j >= 0) read by antidiagonals}}</ref> जिसमें प्रत्येक संख्या अपने से ऊपर की तीन संख्याओं का योग है:
इस सरणी में, पहली पंक्ति की सभी संख्याएँ एक हैं, दूसरी पंक्ति की संख्याएँ [[विषम संख्या]]एँ हैं, तीसरी पंक्ति की संख्याएँ [[केन्द्रित वर्ग संख्या]]एँ हैं, और चौथी पंक्ति की संख्याएँ [[केन्द्रित अष्टफलकीय संख्या]]एँ हैं। वैकल्पिक रूप से, समान संख्याओं को पास्कल त्रिकोण के सदृश एक [[त्रिकोणीय सरणी]] में व्यवस्थित किया जा सकता है, जिसे ट्राइबोनाची त्रिकोण भी कहा जाता है,<ref>{{Cite OEIS|A008288|name=Square array of Delannoy numbers D(i,j) (i >= 0, j >= 0) read by antidiagonals}}</ref> जिसमें प्रत्येक संख्या अपने से ऊपर की तीन संख्याओं का योग है:


            1
      1
          11
      11
        1 3 1
    1 3 1
      1 5 5 1
    1 5 5 1
    1 7 13 7 1
  1 7 13 7 1
  1 9 25 25 9 1
  1 9 25 25 9 1
  1 11 41 63 41 11 1
  1 11 41 63 41 11 1


Line 113: Line 113:


===डेलानॉय संख्याएँ===
===डेलानॉय संख्याएँ===
<math> k </math> विकर्ण (अर्थात उत्तर-पूर्व) चरणों के लिए, बिंदु <math> m-k </math> तक पहुंचने के लिए <math> x </math> दिशा और <math> n-k </math> चरण और <math> y </math> बिंदु तक पहुँचने के लिए <math> (m, n) </math> चरण होने चाहिए; चूँकि ये चरण किसी भी क्रम में किए जा सकते हैं, ऐसे पथों की संख्या [[बहुपद गुणांक]] द्वारा दी गई है<math> \binom{m+n-k}{k , m-k , n-k} = \binom{m+n-k}{m} \binom{m}{k} </math>. इसलिए, किसी को संवृत रूप अभिव्यक्ति मिलती है
<math> k </math> विकर्ण (अर्थात उत्तर-पूर्व) चरणों के लिए, बिंदु <math> m-k </math> तक पहुंचने के लिए <math> x </math> दिशा और <math> n-k </math> चरण और <math> y </math> बिंदु तक पहुँचने के लिए <math> (m, n) </math> चरण होने चाहिए; चूँकि ये चरण किसी भी क्रम में किए जा सकते हैं, ऐसे पथों की संख्या [[बहुपद गुणांक]] द्वारा दी गई है<math> \binom{m+n-k}{k , m-k , n-k} = \binom{m+n-k}{m} \binom{m}{k} </math>. इसलिए, किसी को संवृत रूप अभिव्यक्ति मिलती है


:<math> D(m,n) = \sum_{k=0}^{\min(m,n)} \binom{m+n-k}{m} \binom{m}{k}  </math>
:<math> D(m,n) = \sum_{k=0}^{\min(m,n)} \binom{m+n-k}{m} \binom{m}{k}  </math>
Line 125: Line 125:


:<math> D(m,n) = \sum_{k=0}^{n} A(m,k), </math>
:<math> D(m,n) = \sum_{k=0}^{n} A(m,k), </math>
जहां {{OEIS|id=A266213}} के साथ <math> A(m,k) </math> दिया गया है
जहां {{OEIS|id=A266213}} के साथ <math> A(m,k) </math> दिया गया है


डेलानॉय संख्याओं के लिए मूल [[पुनरावृत्ति संबंध]] आसानी से देखा जा सकता है
डेलानॉय संख्याओं के लिए मूल [[पुनरावृत्ति संबंध]] आसानी से देखा जा सकता है
Line 133: Line 133:
:<math> \sum_{m,n = 0}^\infty D(m, n) x^m y^n = (1 - x - y - xy)^{-1} . </math>
:<math> \sum_{m,n = 0}^\infty D(m, n) x^m y^n = (1 - x - y - xy)^{-1} . </math>
===केंद्रीय डेलानॉय संख्या===
===केंद्रीय डेलानॉय संख्या===
स्थानापन्न ऊपर दिए गए पहले संवृत रूप अभिव्यक्ति में <math> m = n </math> को प्रतिस्थापित करते हुए, <math> k \leftrightarrow n-k </math>, को प्रतिस्थापित करने पर और अल्प बीजगणित, देता है
स्थानापन्न ऊपर दिए गए पहले संवृत रूप अभिव्यक्ति में <math> m = n </math> को प्रतिस्थापित करते हुए, <math> k \leftrightarrow n-k </math>, को प्रतिस्थापित करने पर और अल्प बीजगणित, देता है


:<math> D(n) = \sum_{k=0}^n \binom{n}{k} \binom{n+k}{k} , </math>
:<math> D(n) = \sum_{k=0}^n \binom{n}{k} \binom{n+k}{k} , </math>

Revision as of 01:14, 27 July 2023

डेलानॉय नंबर
Named afterHenri–Auguste Delannoy
No. of known termsinfinity
Formula
OEIS index

गणित में, एक डेलानॉय संख्या एक आयताकार ग्रिड के दक्षिण-पश्चिम कोण (0, 0) से उत्तर-पूर्व कोण (m, n)) तक पथों की संख्या का वर्णन करता है, जिसमें उत्तर, उत्तर-पूर्व या पूर्व में केवल एक ही चरण का उपयोग किया जाता है। डेलानॉय नंबरों का नाम फ्रांसीसी सेना अधिकारी और अनुभवहीन गणितज्ञ हेनरी डेलानॉय के नाम पर रखा गया है।[1]

डेलानॉय संख्या लंबाई और के दो अनुक्रमों के वैश्विक संरेखण की संख्या की भी गणना करती है, [2] -आयामी पूर्णांक लैटिस या क्रॉस पॉलीटोप में बिंदुओं की संख्या जो मूल से अधिकतम n चरण पर होते हैं,[3] और, सेलुलर ऑटोमेटन में, त्रिज्या n के -आयामी वॉन न्यूमैन निकटतम कोशिकाओं की संख्या[4] जबकि त्रिज्या n के एम-आयामी वॉन न्यूमैन द्वारा निकटतम की सतह पर कोशिकाओं की संख्या दी गई है (sequence A266213 in the OEIS)

उदाहरण

डेलानॉय संख्या D(3,3)) 63 के बराबर होता है। निम्नलिखित आंकड़ा (0, 0) से (3, 3) तक 63 डेलानॉय पथ दिखाता है:

Delannoy3x3.svgपथों का उपसमुच्चय जो SW-NE विकर्ण से ऊपर नहीं उठता, उसे संख्याओं के संबंधित श्रेणी, श्रोडर संख्याओं द्वारा गिना जाता है।

डेलनॉय सरणी

डेलानॉय सरणी डेलानॉय संख्याओं का एक अनंत आव्यूह होता है:[5]

 m
n 
0 1 2 3 4 5 6 7 8
0 1 1 1 1 1 1 1 1 1
1 1 3 5 7 9 11 13 15 17
2 1 5 13 25 41 61 85 113 145
3 1 7 25 63 129 231 377 575 833
4 1 9 41 129 321 681 1289 2241 3649
5 1 11 61 231 681 1683 3653 7183 13073
6 1 13 85 377 1289 3653 8989 19825 40081
7 1 15 113 575 2241 7183 19825 48639 108545
8 1 17 145 833 3649 13073 40081 108545 265729
9 1 19 181 1159 5641 22363 75517 224143 598417

इस सरणी में, पहली पंक्ति की सभी संख्याएँ एक हैं, दूसरी पंक्ति की संख्याएँ विषम संख्याएँ हैं, तीसरी पंक्ति की संख्याएँ केन्द्रित वर्ग संख्याएँ हैं, और चौथी पंक्ति की संख्याएँ केन्द्रित अष्टफलकीय संख्याएँ हैं। वैकल्पिक रूप से, समान संख्याओं को पास्कल त्रिकोण के सदृश एक त्रिकोणीय सरणी में व्यवस्थित किया जा सकता है, जिसे ट्राइबोनाची त्रिकोण भी कहा जाता है,[6] जिसमें प्रत्येक संख्या अपने से ऊपर की तीन संख्याओं का योग है:

      1
     11
    1 3 1
   1 5 5 1
  1 7 13 7 1
 1 9 25 25 9 1
1 11 41 63 41 11 1

केंद्रीय डेलानॉय संख्या

केंद्रीय डेलानॉय संख्याएँ D(n) = D(n,n) एक वर्ग n × n ग्रिड के लिए संख्याएँ होती हैं पहले कुछ केंद्रीय डेलानॉय नंबर (n=0 से प्रारंभ ) होते हैं:

1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, ... (sequence A001850 in the OEIS)

गणना

डेलानॉय संख्याएँ

विकर्ण (अर्थात उत्तर-पूर्व) चरणों के लिए, बिंदु तक पहुंचने के लिए दिशा और चरण और बिंदु तक पहुँचने के लिए चरण होने चाहिए; चूँकि ये चरण किसी भी क्रम में किए जा सकते हैं, ऐसे पथों की संख्या बहुपद गुणांक द्वारा दी गई है. इसलिए, किसी को संवृत रूप अभिव्यक्ति मिलती है

एक वैकल्पिक अभिव्यक्ति दी गई है

या अनंत श्रृंखला द्वारा

और भी

जहां (sequence A266213 in the OEIS) के साथ दिया गया है

डेलानॉय संख्याओं के लिए मूल पुनरावृत्ति संबंध आसानी से देखा जा सकता है

यह पुनरावृत्ति संबंध सीधे जनक फलन की ओर भी ले जाता है

केंद्रीय डेलानॉय संख्या

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

जबकि उपरोक्त दूसरी अभिव्यक्ति उत्पन्न होती है

केंद्रीय डेलानॉय संख्याएं आपस में तीन-अवधि के पुनरावृत्ति संबंध का भी समाधान करती हैं,[7]

और एक जनक फलन होता है

केंद्रीय डेलानॉय संख्याओं का प्रमुख उपगामी व्यवहार दिया गया है

जहाँ


और

.

यह भी देखें

संदर्भ

  1. Banderier, Cyril; Schwer, Sylviane (2005), "Why Delannoy numbers?", Journal of Statistical Planning and Inference, 135 (1): 40–54, arXiv:math/0411128, doi:10.1016/j.jspi.2005.02.004, MR 2202337, S2CID 16226115
  2. Covington, Michael A. (2004), "The number of distinct alignments of two strings", Journal of Quantitative Linguistics, 11 (3): 173–182, doi:10.1080/0929617042000314921, S2CID 40549706
  3. Luther, Sebastian; Mertens, Stephan (2011), "Counting lattice animals in high dimensions", Journal of Statistical Mechanics: Theory and Experiment, 2011 (9): P09026, arXiv:1106.1078, Bibcode:2011JSMTE..09..026L, doi:10.1088/1742-5468/2011/09/P09026, S2CID 119308823
  4. Breukelaar, R.; Bäck, Th. (2005), "Using a Genetic Algorithm to Evolve Behavior in Multi Dimensional Cellular Automata: Emergence of Behavior", Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO '05), New York, NY, USA: ACM, pp. 107–114, doi:10.1145/1068009.1068024, ISBN 1-59593-010-8, S2CID 207157009
  5. Sulanke, Robert A. (2003), "Objects counted by the central Delannoy numbers" (PDF), Journal of Integer Sequences, 6 (1): Article 03.1.5, Bibcode:2003JIntS...6...15S, MR 1971435
  6. Sloane, N. J. A. (ed.). "Sequence A008288 (Square array of Delannoy numbers D(i,j) (i >= 0, j >= 0) read by antidiagonals)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  7. Peart, Paul; Woan, Wen-Jin (2002). "डेलानॉय पुनरावृत्ति का एक विशेषण प्रमाण". Congressus Numerantium. 158: 29–33. ISSN 0384-9864. MR 1985142. Zbl 1030.05003.


बाहरी संबंध