{"id":26120,"date":"2017-10-26T19:55:00","date_gmt":"2017-10-26T14:25:00","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26120"},"modified":"2018-10-31T16:36:07","modified_gmt":"2018-10-31T11:06:07","slug":"python-programming-program-nth-catalan-number","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-program-nth-catalan-number\/","title":{"rendered":"Program for nth Catalan Number"},"content":{"rendered":"

Program for nth Catalan Number<\/strong><\/span><\/p>\n

Catalan numbers<\/a> are a sequence of natural numbers<\/strong> that occurs in many interesting counting problems like following.<\/span><\/p>\n

1)<\/strong> Count the number of expressions<\/strong> containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).<\/p>\n

2)<\/strong> Count the number of possible Binary Search Trees<\/a> <\/strong>with n keys<\/p>\n

3)<\/strong> Count the number of full binary trees<\/strong> (A rooted binary tree<\/a> is full if every vertex has either two children or no children) with n+1 leaves.<\/p>\n

The first few Catalan numbers<\/strong> for n = 0, 1, 2, 3, \u2026 are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \u2026<\/strong><\/p>\n

Recursive Solution<\/strong><\/span><\/h3>\n

Following is the implementation of above recursive<\/a> formula.<\/p>\n

Python Program<\/span> <\/div> 
# A recursive function to find nth catalan numberdef catalan(n):    # Base Case    if n <=1 :        return 1     # Catalan(n) is the sum of catalan(i)*catalan(n-i-1)    res = 0    for i in range(n):        res += catalan(i) * catalan(n-i-1)     return res # Driver Program to test above functionfor i in range(10):    print catalan(i),<\/code><\/pre> <\/div>\n
Output :<\/span><\/h3>\n
1 1 2 5 14 42 132 429 1430 4862<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Python Programming – Program for nth Catalan Number – Mathematical Algorithms – Catalan numbers are a sequence of natural numbers that occurs in many<\/p>\n","protected":false},"author":2,"featured_media":31259,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,74058,4148],"tags":[77126,77161,77131,77137,77134,77153,77129,77133,77138,77167,77159,77139,77152,77146,77045,74979,77149,77147,77164,77150,77151,77136,77156,77155,77154,77127,77140,77123,77157,77163,77145,77125,74983,77166,77168,77124,77158,77148,77142,77160,77141,77143,77162,77130,77128,77135,77144,77165,74298,77132],"class_list":["post-26120","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-coding","category-mathematical-algorithms","category-python","tag-1-2-5-14","tag-ambiguous-in-a-sentence","tag-bell-symbol","tag-best-english-sentences","tag-can-sentences-examples","tag-context-free-grammar","tag-english-sentence-formation","tag-english-sentence-patterns","tag-english-sentence-structure","tag-english-sentences-examples","tag-example-of-phrase","tag-examples-of-ambiguous-sentences","tag-examples-of-ambiguous-sentences-in-english","tag-examples-of-sentence-structure","tag-factorial-program-in-python","tag-fibonacci-python","tag-for-example-sentence","tag-frame-sentences-given-words","tag-frame-sentences-using-following-words","tag-grammar-analysis","tag-grammar-sentences","tag-grammar-usage-sentence-structuring","tag-how-to-make-english-sentence","tag-how-to-make-sentences","tag-make-sentences-with-given-words","tag-parse-meaning-in-english","tag-parse-tree-example","tag-parse-tree-generator","tag-phrase-examples","tag-phrase-examples-sentences","tag-python-faculty","tag-python-parser-example","tag-python-recursion","tag-sentence-building","tag-sentence-construction","tag-sentence-formation","tag-sentence-formation-in-english-with-grammar","tag-sentence-structure","tag-sentence-structure-english","tag-sentence-tree-diagram","tag-structural-analysis-examples","tag-structural-analysis-in-english","tag-structural-grammar","tag-structure-of-a-sentence-in-english","tag-structure-of-sentences","tag-syntax-tree-diagram-exercises-with-answers","tag-syntax-tree-diagram-generator","tag-syntax-tree-generator","tag-what-is-a-recursive-function","tag-words-sentences-in-english"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26120","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26120"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26120\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31259"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26120"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26120"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}