नारायण संख्या

नारायण संख्या

Named after	Tadepalli Venkata Narayana
No. of known terms	infinity
Formula	$\operatorname {N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}$
OEIS index	A001263 Triangle of Narayana

साहचर्य में, नारायण संख्याएँ $\operatorname {N} (n,k),n\in \mathbb {N} ^{+},1\leq k\leq n$ प्राकृतिक संख्याओं की एक त्रिकोणीय सरणी बनाएं, जिसे नारायण त्रिकोण कहा जाता है, जो विभिन्न संयोजन गणना में होती है। इनका नाम कनाडाई गणितज्ञ टी. वी. नारायण (1930-1987) के नाम पर रखा गया है।

सूत्र

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

$\operatorname {N} (n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}$

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

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

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)

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

डाइक शब्द

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

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

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

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

$\operatorname {N} (n,k)=\operatorname {N} (n,n-k+1)$

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

$\operatorname {N} (n,1)+\operatorname {N} (n,2)+\operatorname {N} (n,3)+\cdots +\operatorname {N} (n,n)=C_{n}$

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

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

निम्नलिखित आंकड़े नारायण संख्याओं का प्रतिनिधित्व करते हैं $\operatorname {N} (4,k)$, उपर्युक्त समरूपताओं को दर्शाता है।

$\operatorname {N} (4,k)$	Paths
N(4,1) = 1 path with 1 peak
N(4,2) = 6 paths with 2 peaks:
N(4,3) = 6 paths with 3 peaks:
N(4,4) = 1 path with 4 peaks:

कुल मिलाकर $\operatorname {N} (4,k)$ 1 + 6 + 6 + 1 = 14 है, जो कि चौथी कैटलन संख्या है, $C_{4}$. यह योग कैटलन संख्याओं की व्याख्या के साथ मिलता है, जो कि किनारों के साथ एकदिष्ट पथों की संख्या है $n\times n$ जाल जो विकर्ण के ऊपर से नहीं गुजरता था।

जड़ वाले पेड़

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

बिना समतल वाले पेड़ों की संख्या(ग्राफ सिद्धांत)क्रमित पेड़(ग्राफ सिद्धांत)जड़युक्त पेड़ $n$ किनारों और $k$ पत्तियां बराबर हैं $\operatorname {N} (n,k)$.

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

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

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

विभाजन

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

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

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

जनरेटिंग फलन

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

$\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}}\;.$

यह भी देखें

• कैटलन नंबर
• डेलानॉय नंबर
• मोत्ज़किन संख्या
• श्रोडर संख्या
• पास्कल का त्रिकोण
• Learning materials related to Partition related number triangles at Wikiversity

संदर्भ

• 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.