{"id":26119,"date":"2017-10-26T19:58:27","date_gmt":"2017-10-26T14:28:27","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26119"},"modified":"2017-10-26T19:58:27","modified_gmt":"2017-10-26T14:28:27","slug":"java-programming-program-nth-catalan-number","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-program-nth-catalan-number\/","title":{"rendered":"Java Programming – Program for nth Catalan Number"},"content":{"rendered":"

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

1)<\/strong> Count the number of expressions 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 with n keys (See this<\/a>)<\/p>\n

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

The first few Catalan numbers 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>
\nFollowing is the implementation of above recursive formula.<\/p>\n

Java Program<\/span> <\/div> 
class CatalnNumber {     \/\/ A recursive function to find nth catalan number     int catalan(int n) {        int res = 0;                 \/\/ Base case        if (n <= 1) {            return 1;        }        for (int i = 0; i < n; i++) {            res += catalan(i) * catalan(n - i - 1);        }        return res;    }     public static void main(String[] args) {        CatalnNumber cn = new CatalnNumber();        for (int i = 0; i < 10; i++) {            System.out.print(cn.catalan(i) + " ");        }    }}<\/code><\/pre> <\/div>\n
Output :<\/p>\n
1 1 2 5 14 42 132 429 1430 4862<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Java Programming – Program for nth Catalan Number – Mathematical Algorithms – Catalan numbers are a sequence of natural numbers that occurs in many interest<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1,2139,74058],"tags":[77161,77196,77193,77131,77137,77134,77153,77129,77133,77138,77167,77159,77152,77045,74979,77188,77147,77184,77164,77190,77150,77151,77189,77136,77156,77155,77185,77154,77183,77127,77186,77157,77145,77125,74983,70056,74289,77168,77124,77158,77148,77187,77182,77195,77192,77128,77191,77194,74298,77132],"class_list":["post-26119","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","category-java","category-mathematical-algorithms","tag-ambiguous-in-a-sentence","tag-ambiguous-sentences","tag-ambiguous-sentences-examples","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-in-english","tag-factorial-program-in-python","tag-fibonacci-python","tag-following-sentence","tag-frame-sentences-given-words","tag-frame-sentences-in-english","tag-frame-sentences-using-following-words","tag-free-grammar","tag-grammar-analysis","tag-grammar-sentences","tag-grammar-tree","tag-grammar-usage-sentence-structuring","tag-how-to-make-english-sentence","tag-how-to-make-sentences","tag-immediate-constituent-analysis","tag-make-sentences-with-given-words","tag-might-sentences-examples","tag-parse-meaning-in-english","tag-parse-tree","tag-phrase-examples","tag-python-faculty","tag-python-parser-example","tag-python-recursion","tag-recursion","tag-recursive-function","tag-sentence-construction","tag-sentence-formation","tag-sentence-formation-in-english-with-grammar","tag-sentence-structure","tag-sentence-structure-in-english","tag-shift-reduce-parsing","tag-simple-sentences-in-english","tag-structural-analysis-book","tag-structure-of-sentences","tag-use-ambiguous-in-a-sentence","tag-verb-phrase-structure","tag-what-is-a-recursive-function","tag-words-sentences-in-english"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26119","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=26119"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26119\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26119"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26119"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26119"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}