नारायण संख्या: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 55: Line 55:
=== डाइक शब्द ===
=== डाइक शब्द ===


गिनती की समस्या का एक उदाहरण जिसका समाधान नारायण संख्याओं के संदर्भ में दिया जा सकता है <math>\operatorname{N}(n, k)</math>, युक्त शब्दों की संख्या है {{tmath|n}} कोष्ठकों के जोड़े, जो सही ढंग से मिलता हैं (डिक शब्द के रूप में जाने जाते हैं) और जिनमें सम्मिलित होता हैं {{tmath|k}} अलग-अलग घोंसले होते है। उदाहरण के लिए, <math>\operatorname{N}(4, 2) = 6</math>, चूंकि कोष्ठकों के चार जोड़े के साथ, छह अनुक्रम बनाए जा सकते हैं जिनमें से प्रत्येक में उप-पैटर्न की दो घटनाएं होती हैं {{code|()}}:
गिनती की समस्या का उदाहरण जिसका समाधान नारायण संख्याओं के संदर्भ में दिया जा सकता है <math>\operatorname{N}(n, k)</math>, युक्त शब्दों की संख्या है {{tmath|n}} कोष्ठकों के जोड़े, जो सही ढंग से मिलता हैं (डिक शब्द के रूप में जाने जाते हैं) और जिनमें सम्मिलित होता हैं {{tmath|k}} अलग-अलग घोंसले होते है। उदाहरण के लिए, <math>\operatorname{N}(4, 2) = 6</math>, चूंकि कोष्ठकों के चार जोड़े के साथ, छह अनुक्रम बनाए जा सकते हैं जिनमें से प्रत्येक में उप-प्रतिरूप की दो घटनाएं होती हैं {{code|()}}:


  (()(())) ((()())) ((())())
  (()(())) ((()())) ((())())
  ()((())) (())(()) ((()))()
  ()((())) (())(()) ((()))()


इस उदाहरण से यह स्पष्ट होना चाहिए कि <math>\operatorname{N}(n, 1) = 1</math>, चूंकि एकल उप-पैटर्न प्राप्त करने का एकमात्र तरीका है {{code|()}} पहले में सभी आरंभिक कोष्ठक रखना है {{tmath|n}} स्थिति, उसके बाद सभी समापन कोष्ठक भी <math>\operatorname{N}(n, n) = 1</math>, जैसा {{tmath|n}} विशिष्ट घोंसला केवल दोहराए जाने वाले पैटर्न द्वारा ही प्राप्त किया जा सकता है {{code|()()()…()}}.
इस उदाहरण से यह स्पष्ट होना चाहिए कि <math>\operatorname{N}(n, 1) = 1</math>, चूंकि एकल उप-पैटर्न प्राप्त करने का एकमात्र तरीका है {{code|()}} पहले में सभी आरंभिक कोष्ठक रखना है {{tmath|n}} स्थिति, उसके बाद सभी समापन कोष्ठक भी <math>\operatorname{N}(n, n) = 1</math>, जैसा {{tmath|n}} विशिष्ट घोंसला दोहराए जाने वाले प्रतिरूप द्वारा ही प्राप्त किया जा सकता है {{code|()()()…()}}.


अत्यधिक सामान्यतः, यह दिखाया जा सकता है कि नारायण त्रिकोण सममित होता है:
अत्यधिक सामान्यतः,यह दिखाया जा सकता है कि नारायण त्रिकोण सममित होता है:


:<math>\operatorname{N}(n, k) = \operatorname{N}(n, n-k+1)</math>
:<math>\operatorname{N}(n, k) = \operatorname{N}(n, n-k+1)</math>
Line 70: Line 70:




=== मोनोटोनिक जाली पथ ===
=== मोनोटोनिक जाली पाथ ===


नारायण संख्याएँ जाली पथ की संख्या की भी गणना करती हैं <math>(0, 0)</math> को <math>(2n, 0)</math>, केवल उत्तर-पूर्व और दक्षिण-पूर्व में सीढ़ियाँ हैं, नीचे नहीं भटक रही हैं {{mvar|x}}-अक्ष, साथ {{tmath|k}} चोटियाँ.
नारायण संख्याएँ जाली पाथ की संख्या की भी गणना करती हैं <math>(0, 0)</math> को <math>(2n, 0)</math>, उत्तर-पूर्व और दक्षिण-पूर्व में सीढ़ियाँ हैं, नीचे नहीं भटक रही हैं {{mvar|x}}-अक्ष, साथ {{tmath|k}} चोटियाँ.


निम्नलिखित आंकड़े नारायण संख्याओं का प्रतिनिधित्व करते हैं <math>\operatorname{N}(4, k)</math>, उपर्युक्त समरूपताओं को दर्शाता है।
निम्नलिखित आंकड़े नारायण संख्याओं का प्रतिनिधित्व करते हैं <math>\operatorname{N}(4, k)</math>, उपर्युक्त समरूपताओं को दर्शाता है।
Line 81: Line 81:
! Paths
! Paths
|-
|-
| ''N''(4,1) = '''1''' path with 1 peak
| ''N''(4,1) = '''1''' पाथ with 1 peak
| [[File:Narayana N(4, 1).svg]]
| [[File:Narayana N(4, 1).svg]]
|-
|-
| ''N''(4,2) = '''6''' paths with 2 peaks:
| ''N''(4,2) = '''6''' पाथ with 2 peaks:
| [[File:Narayana N(4, 2).svg]]
| [[File:Narayana N(4, 2).svg]]
|-
|-
| ''N''(4,3) = '''6''' paths with 3 peaks:
| ''N''(4,3) = '''6''' पाथ with 3 peaks:
| [[File:Narayana N(4, 3).svg]]
| [[File:Narayana N(4, 3).svg]]
|-
|-
| ''N''(4,4) = '''1''' path with 4 peaks:
| ''N''(4,4) = '''1''' पाथ with 4 peaks:
| [[File:Narayana N(4, 4).svg]]
| [[File:Narayana N(4, 4).svg]]
|}
|}
कुल मिलाकर <math>\operatorname{N}(4, k)</math> 1 + 6 + 6 + 1 = 14 है, जो कि चौथी कैटलन संख्या है, <math>C_4</math>. यह योग कैटलन संख्याओं की व्याख्या के साथ मिलता है, जो कि किनारों के साथ मोनोटोनिक पथों की संख्या है <math>n \times n</math> ग्रिड जो विकर्ण के ऊपर से नहीं गुजरता था।
कुल मिलाकर <math>\operatorname{N}(4, k)</math> 1 + 6 + 6 + 1 = 14 है, जो कि चौथी कैटलन संख्या है, <math>C_4</math>. यह योग कैटलन संख्याओं की व्याख्या के साथ मिलता है, जो कि किनारों के साथ एकदिष्ट पथों की संख्या है <math>n \times n</math> जाल जो विकर्ण के ऊपर से नहीं गुजरता था।


=== जड़ वाले पेड़ ===
=== रूटेड ट्री ===


[[File:Unlabeled ordered rooted trees of 4 edges and 2 leaves.svg|thumb|नारायण संख्या N(4, 2) के अनुरूप, 4 किनारों और 2 पत्तियों वाले 6 क्रमबद्ध जड़ वाले पेड़]]बिना स्तर वाले पेड़ों की संख्या(ग्राफ सिद्धांत)क्रमित_पेड़(ग्राफ सिद्धांत)जड़युक्त_पेड़ <math>n</math> किनारों और <math>k</math> पत्तियां बराबर हैं <math>\operatorname{N}(n, k)</math>.
[[File:Unlabeled ordered rooted trees of 4 edges and 2 leaves.svg|thumb|नारायण संख्या N(4, 2) के अनुरूप, 4 किनारों और 2 पत्तियों वाले 6 क्रमबद्ध जड़ वाले पेड़]]बिना समतल वाले ट्री  की संख्या (ग्राफ सिद्धांत) क्रमित रूटेड ट्री युक्त ट्री  <math>n</math> किनारों और <math>k</math> पत्तियां बराबर हैं <math>\operatorname{N}(n, k)</math>.


यह उपरोक्त उदाहरणों के अनुरूप होता है:
यह उपरोक्त उदाहरणों के अनुरूप होता है:


* प्रत्येक डाइक शब्द को जड़ वाले पेड़ के रूप में दर्शाया जा सकता है। हम नोड से प्रारम्भ करते हैं - रूट नोड होता है। यह प्रारंभ में सक्रिय नोड है. शब्द को बाएं से दाएं पढ़ते समय, जब प्रतीक प्रारंभिक कोष्ठक होता है, तो सक्रिय नोड में एक बच्चा जोड़ें और इस बच्चे को सक्रिय नोड के रूप में  समुच्चय करता है। जब प्रतीक समापन कोष्ठक है, तो सक्रिय नोड के पैरेंट को सक्रिय नोड के रूप में समुच्चय करता है। इस तरह हम पेड़ प्राप्त करते हैं, जिसमें प्रत्येक गैर-रूट नोड कोष्ठकों की एक मिलान जोड़ी से मिलता है, और इसके बच्चे इन कोष्ठकों के भीतर क्रमिक डाइक शब्दों के अनुरूप नोड्स हैं। लीफ नोड्स खाली कोष्ठकों से मिलता हैं: {{code|()}}. इसी प्रकार, हम गहराई-पहली खोज के माध्यम से जड़ वाले पेड़ से डाइक शब्द का निर्माण कर सकते हैं। इस प्रकार,डाइक शब्दों और जड़ वाले पेड़ों के बीच समरूपता होता है।
* प्रत्येक डाइक शब्द को रूटेड ट्री के रूप में दर्शाया जा सकता है। हम नोड से प्रारम्भ करते हैं - रूट नोड होता है। यह प्रारंभ में सक्रिय नोड है. शब्द को बाएं से दाएं पढ़ते समय, जब प्रतीक प्रारंभिक कोष्ठक होता है, तो सक्रिय नोड में एक बच्चा जोड़ें और इस बच्चे को सक्रिय नोड के रूप में  समुच्चय करता है। जब प्रतीक समापन कोष्ठक है, तो सक्रिय नोड के मूल को सक्रिय नोड के रूप में समुच्चय करता है। इस तरह हम पेड़ प्राप्त करते हैं, जिसमें प्रत्येक गैर-रूट नोड कोष्ठकों की एक मिलान जोड़ी से मिलता है, और इसके बच्चे इन कोष्ठकों के भीतर क्रमिक डाइक शब्दों के अनुरूप नोड्स हैं। लीफ नोड्स खाली कोष्ठकों से मिलता हैं: {{code|()}}. इसी प्रकार, हम गहराई-पहली खोज के माध्यम से रूटेड ट्री से डाइक शब्द का निर्माण कर सकते हैं। इस प्रकार,डाइक शब्दों और रूटेड ट्री के बीच समरूपता होता है।


* जाली पथों के उपरोक्त आंकड़ों में, क्षैतिज रेखा से प्रत्येक ऊपरी किनारा ऊंचाई पर है {{tmath|y}} को {{tmath|y}}{{tmath|+1}} नोड के बीच किनारे से मिलता है {{tmath|y}} और उसका बच्चा. नोड {{tmath|y}} के उतने ही बच्चे हैं, जितने ऊंचाई पर क्षैतिज रेखा से ऊपर की ओर जाने वाले किनारे हैं {{tmath|y}}. उदाहरण के लिए, पहले पथ में <math>\operatorname{N}(4, 3)</math>, नोड्स {{math|0}} और {{math|1}} दो-दो बच्चे होंगे; अंतिम (छठे) पथ में, node {{math|0}} के तीन बच्चे होंगे और नोड {{math|1}} बच्चा होगा. जाली पथ से जड़ वाले पेड़ का निर्माण करने के लिए और इसके विपरीत, हम पिछले पैराग्राफ में उल्लिखित एल्गोरिदम के समान एक एल्गोरिदम नियोजित कर सकते हैं। डाइक शब्दों की तरह, जाली पथों और जड़ वाले पेड़ों के बीच समरूपता है।
* जाली पथों के उपरोक्त आंकड़ों में, क्षैतिज रेखा से प्रत्येक ऊपरी किनारा ऊंचाई पर है {{tmath|y}} को {{tmath|y}}{{tmath|+1}} नोड के बीच किनारे से मिलता है {{tmath|y}} और उसका बच्चा. नोड {{tmath|y}} के उतने ही बच्चे हैं, जितने ऊंचाई पर क्षैतिज रेखा से ऊपर की ओर जाने वाले किनारे हैं {{tmath|y}}. उदाहरण के लिए, पहले पथ में <math>\operatorname{N}(4, 3)</math>, नोड्स {{math|0}} और {{math|1}} दो-दो बच्चे होंगे; अंतिम (छठे) पथ में, नोड {{math|0}} के तीन बच्चे होंगे और नोड {{math|1}} बच्चा होगा. जाली पथ से जड़ वाले पेड़ का निर्माण करने के लिए और इसके विपरीत, हम पिछले पैराग्राफ में उल्लिखित एल्गोरिदम के समान एक एल्गोरिदम नियोजित कर सकते हैं। डाइक शब्दों की तरह, जाली पथों और रूटेड ट्री के बीच समरूपता है।


== विभाजन ==
== विभाजन ==
[[File:Noncrossing partitions 4; Hasse.svg|thumb|4-तत्व समुच्चय के 1,2,3,4 ब्लॉक के साथ 1,6,6,1 [[गैर-क्रॉसिंग विभाजन]]]]विभाजनों के अध्ययन में, हम देखते हैं कि समुच्चय में {{tmath|n}}तत्व, हम उस समुच्चय को विभाजित कर सकते हैं <math>B_n</math> अलग-अलग तरीके, कहां <math>B_n</math> है {{tmath|n}}<sup>वें</sup>[[बेल नंबर]]. इसके अलावा, किसी समुच्चय को सटीक रूप से विभाजित करने के तरीकों की संख्या {{tmath|k}} ब्लॉक में हम दूसरे प्रकार के स्टर्लिंग नंबरों का उपयोग करते हैं <math>S(n, k)</math>. ये दोनों अवधारणाएँ विषय से थोड़ी हटकर हैं, लेकिन नारायण संख्याओं के उपयोग को समझने के लिए आवश्यक आधार होता हैं। उपरोक्त दोनों में दो धारणाओं को पार करने वाले विभाजनों को ध्यान में रखा गया है।
[[File:Noncrossing partitions 4; Hasse.svg|thumb|4-तत्व समुच्चय के 1,2,3,4 ब्लॉक के साथ 1,6,6,1 [[गैर-क्रॉसिंग विभाजन]]]]विभाजनों के अध्ययन में, हम देखते हैं कि समुच्चय में {{tmath|n}}तत्व, हम उस समुच्चय को विभाजित कर सकते हैं <math>B_n</math> अलग-अलग तरीके, कहां <math>B_n</math> है {{tmath|n}} घंटी संख्या. इसके अतिरिक्त,किसी समुच्चय को सटीक रूप से विभाजित करने के तरीकों की संख्या {{tmath|k}} ब्लॉक में हम दूसरे प्रकार के स्टर्लिंग संख्या का उपयोग करते हैं <math>S(n, k)</math>. ये दोनों अवधारणाएँ विषय से थोड़ी हटकर हैं, लेकिन नारायण संख्याओं के उपयोग को समझने के लिए आवश्यक आधार होता हैं। उपरोक्त दोनों में दो धारणाओं को पार करने वाले विभाजनों को ध्यान में रखा गया है।


क्रॉसिंग विभाजनों को अस्वीकार करने और गैर-क्रॉसिंग विभाजनों को गिनने के लिए, हम सभी के गैर-क्रॉसिंग विभाजनों को गिनने के लिए [[कैटलन संख्या]]ओं का उपयोग कर सकते हैं {{tmath|n}} समुच्चय के तत्व, <math>C_n</math>.उन गैर-क्रॉसिंग विभाजनों की गणना करने के लिए जिनमें समुच्चय को सटीक रूप से विभाजित किया गया है {{tmath|k}} ब्लॉक, हम नारायण संख्या का उपयोग करते हैं <math>\operatorname{N}(n, k)</math>.
क्रॉसिंग विभाजनों को अस्वीकार करने और गैर-क्रॉसिंग विभाजनों को गिनने के लिए, हम सभी के गैर-क्रॉसिंग विभाजनों को गिनने के लिए [[कैटलन संख्या]]ओं का उपयोग कर सकते हैं {{tmath|n}} समुच्चय के तत्व, <math>C_n</math>.उन गैर-क्रॉसिंग विभाजनों की गणना करने के लिए जिनमें समुच्चय को सटीक रूप से विभाजित किया गया है {{tmath|k}} ब्लॉक, हम नारायण संख्या का उपयोग करते हैं <math>\operatorname{N}(n, k)</math>.


== जनरेटिंग फ़ंक्शन ==
== जनरेटिंग फलन ==
नारायण संख्याओं के लिए जनक फलन होता है | {{sfn|Petersen|2015|p=25}}
नारायण संख्याओं के लिए जनरेटिंग फलन होता है | {{sfn|Petersen|2015|p=25}}
:<math>
:<math>
\sum_{n=1}^\infty \sum_{k=1}^n \operatorname{N}(n, k) z^n t^{k-1} = \frac{1-z(t+1) - \sqrt{1-2z(t+1)+z^2(t-1)^2}}{2tz} \;.
\sum_{n=1}^\infty \sum_{k=1}^n \operatorname{N}(n, k) z^n t^{k-1} = \frac{1-z(t+1) - \sqrt{1-2z(t+1)+z^2(t-1)^2}}{2tz} \;.
Line 122: Line 122:


==यह भी देखें==
==यह भी देखें==
* कैटलन नंबर
* कैटलन संख्या
* [[डेलानॉय नंबर]]
* [[डेलानॉय नंबर|डेलानॉय संख्या]]  
* [[ मोत्ज़किन संख्या ]]
* [[ मोत्ज़किन संख्या ]]
* श्रोडर संख्या
* श्रोडर संख्या
Line 138: Line 138:


{{Classes of natural numbers}}
{{Classes of natural numbers}}
[[Category: संख्याओं के त्रिकोण]] [[Category: पूर्णांक क्रम]] [[Category: भाज्य और द्विपद विषय]] [[Category: क्रमपरिवर्तन]]


 
[[Category:Collapse templates]]
 
[[Category: Machine Translated Page]]
[[Category:Created On 09/07/2023]]
[[Category:Created On 09/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Mathematics navigational boxes]]
[[Category:Navbox orphans]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Translated in Hindi]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:क्रमपरिवर्तन]]
[[Category:पूर्णांक क्रम]]
[[Category:भाज्य और द्विपद विषय]]
[[Category:संख्याओं के त्रिकोण]]

Latest revision as of 17:25, 8 August 2023

नारायण संख्या
Named afterTadepalli Venkata Narayana
No. of known termsinfinity
Formula
OEIS index

साहचर्य में, नारायण संख्याएँ प्राकृतिक संख्याओं की एक त्रिकोणीय सरणी बनाएं, जिसे नारायण त्रिकोण कहा जाता है, जो विभिन्न संयोजन गणना में होती है। इनका नाम कनाडाई गणितज्ञ टी. वी. नारायण (1930-1987) के नाम पर रखा गया है।

सूत्र

नारायण संख्याओं को द्विपद गुणांक के रूप में व्यक्त किया जा सकता है:


संख्यात्मक मान

नारायण त्रिकोण की पहली आठ पंक्तियाँ पढ़ी जाती हैं:

n k
1 2 3 4 5 6 7 8
1 1
2 1 1
3 1 3 1
4 1 6 6 1
5 1 10 20 10 1
6 1 15 50 50 15 1
7 1 21 105 175 105 21 1
8 1 28 196 490 490 196 28 1

(sequence A001263 in the OEIS)

संयुक्त व्याख्याएँ

डाइक शब्द

गिनती की समस्या का उदाहरण जिसका समाधान नारायण संख्याओं के संदर्भ में दिया जा सकता है , युक्त शब्दों की संख्या है कोष्ठकों के जोड़े, जो सही ढंग से मिलता हैं (डिक शब्द के रूप में जाने जाते हैं) और जिनमें सम्मिलित होता हैं अलग-अलग घोंसले होते है। उदाहरण के लिए, , चूंकि कोष्ठकों के चार जोड़े के साथ, छह अनुक्रम बनाए जा सकते हैं जिनमें से प्रत्येक में उप-प्रतिरूप की दो घटनाएं होती हैं ():

(()(())) ((()())) ((())())
()((())) (())(()) ((()))()

इस उदाहरण से यह स्पष्ट होना चाहिए कि , चूंकि एकल उप-पैटर्न प्राप्त करने का एकमात्र तरीका है () पहले में सभी आरंभिक कोष्ठक रखना है स्थिति, उसके बाद सभी समापन कोष्ठक भी , जैसा विशिष्ट घोंसला दोहराए जाने वाले प्रतिरूप द्वारा ही प्राप्त किया जा सकता है ()()()…().

अत्यधिक सामान्यतः,यह दिखाया जा सकता है कि नारायण त्रिकोण सममित होता है:

इस त्रिभुज में पंक्तियों का योग कैटलन संख्याओं के बराबर है:


मोनोटोनिक जाली पाथ

नारायण संख्याएँ जाली पाथ की संख्या की भी गणना करती हैं को , उत्तर-पूर्व और दक्षिण-पूर्व में सीढ़ियाँ हैं, नीचे नहीं भटक रही हैं x-अक्ष, साथ चोटियाँ.

निम्नलिखित आंकड़े नारायण संख्याओं का प्रतिनिधित्व करते हैं , उपर्युक्त समरूपताओं को दर्शाता है।

Paths
N(4,1) = 1 पाथ with 1 peak Narayana N(4, 1).svg
N(4,2) = 6 पाथ with 2 peaks: Narayana N(4, 2).svg
N(4,3) = 6 पाथ with 3 peaks: Narayana N(4, 3).svg
N(4,4) = 1 पाथ with 4 peaks: Narayana N(4, 4).svg

कुल मिलाकर 1 + 6 + 6 + 1 = 14 है, जो कि चौथी कैटलन संख्या है, . यह योग कैटलन संख्याओं की व्याख्या के साथ मिलता है, जो कि किनारों के साथ एकदिष्ट पथों की संख्या है जाल जो विकर्ण के ऊपर से नहीं गुजरता था।

रूटेड ट्री

नारायण संख्या N(4, 2) के अनुरूप, 4 किनारों और 2 पत्तियों वाले 6 क्रमबद्ध जड़ वाले पेड़

बिना समतल वाले ट्री की संख्या (ग्राफ सिद्धांत) क्रमित रूटेड ट्री युक्त ट्री किनारों और पत्तियां बराबर हैं .

यह उपरोक्त उदाहरणों के अनुरूप होता है:

  • प्रत्येक डाइक शब्द को रूटेड ट्री के रूप में दर्शाया जा सकता है। हम नोड से प्रारम्भ करते हैं - रूट नोड होता है। यह प्रारंभ में सक्रिय नोड है. शब्द को बाएं से दाएं पढ़ते समय, जब प्रतीक प्रारंभिक कोष्ठक होता है, तो सक्रिय नोड में एक बच्चा जोड़ें और इस बच्चे को सक्रिय नोड के रूप में समुच्चय करता है। जब प्रतीक समापन कोष्ठक है, तो सक्रिय नोड के मूल को सक्रिय नोड के रूप में समुच्चय करता है। इस तरह हम पेड़ प्राप्त करते हैं, जिसमें प्रत्येक गैर-रूट नोड कोष्ठकों की एक मिलान जोड़ी से मिलता है, और इसके बच्चे इन कोष्ठकों के भीतर क्रमिक डाइक शब्दों के अनुरूप नोड्स हैं। लीफ नोड्स खाली कोष्ठकों से मिलता हैं: (). इसी प्रकार, हम गहराई-पहली खोज के माध्यम से रूटेड ट्री से डाइक शब्द का निर्माण कर सकते हैं। इस प्रकार,डाइक शब्दों और रूटेड ट्री के बीच समरूपता होता है।
  • जाली पथों के उपरोक्त आंकड़ों में, क्षैतिज रेखा से प्रत्येक ऊपरी किनारा ऊंचाई पर है को नोड के बीच किनारे से मिलता है और उसका बच्चा. नोड के उतने ही बच्चे हैं, जितने ऊंचाई पर क्षैतिज रेखा से ऊपर की ओर जाने वाले किनारे हैं . उदाहरण के लिए, पहले पथ में , नोड्स 0 और 1 दो-दो बच्चे होंगे; अंतिम (छठे) पथ में, नोड 0 के तीन बच्चे होंगे और नोड 1 बच्चा होगा. जाली पथ से जड़ वाले पेड़ का निर्माण करने के लिए और इसके विपरीत, हम पिछले पैराग्राफ में उल्लिखित एल्गोरिदम के समान एक एल्गोरिदम नियोजित कर सकते हैं। डाइक शब्दों की तरह, जाली पथों और रूटेड ट्री के बीच समरूपता है।

विभाजन

4-तत्व समुच्चय के 1,2,3,4 ब्लॉक के साथ 1,6,6,1 गैर-क्रॉसिंग विभाजन

विभाजनों के अध्ययन में, हम देखते हैं कि समुच्चय में तत्व, हम उस समुच्चय को विभाजित कर सकते हैं अलग-अलग तरीके, कहां है घंटी संख्या. इसके अतिरिक्त,किसी समुच्चय को सटीक रूप से विभाजित करने के तरीकों की संख्या ब्लॉक में हम दूसरे प्रकार के स्टर्लिंग संख्या का उपयोग करते हैं . ये दोनों अवधारणाएँ विषय से थोड़ी हटकर हैं, लेकिन नारायण संख्याओं के उपयोग को समझने के लिए आवश्यक आधार होता हैं। उपरोक्त दोनों में दो धारणाओं को पार करने वाले विभाजनों को ध्यान में रखा गया है।

क्रॉसिंग विभाजनों को अस्वीकार करने और गैर-क्रॉसिंग विभाजनों को गिनने के लिए, हम सभी के गैर-क्रॉसिंग विभाजनों को गिनने के लिए कैटलन संख्याओं का उपयोग कर सकते हैं समुच्चय के तत्व, .उन गैर-क्रॉसिंग विभाजनों की गणना करने के लिए जिनमें समुच्चय को सटीक रूप से विभाजित किया गया है ब्लॉक, हम नारायण संख्या का उपयोग करते हैं .

जनरेटिंग फलन

नारायण संख्याओं के लिए जनरेटिंग फलन होता है | [1]


यह भी देखें

उद्धरण

  1. Petersen 2015, p. 25.


संदर्भ

  • P. A. MacMahon (1915–1916). Combinatorial Analysis. Cambridge University Press.
  • Petersen, T. Kyle (2015). "Narayana numbers" (PDF). Eulerian Numbers. Birkhäuser Advanced Texts Basler Lehrbücher. Basel: Birkhäuser. doi:10.1007/978-1-4939-3091-3. ISBN 978-1-4939-3090-6.