Given an interger n; the task is to find the Catalan Number on that nth position. So, before doing the program we must know what is a Catalan Number?
Catlan numbers are the sequence of natural numbers, which occurs in the form of various counting number problems.
Catalan numbers C0, C1, C2,… Cn are driven by formula −
$$c_{n}=frac{1}{n+1}binom{2n}{n} = frac{2n!}{(n+1)!n!}$$
The few Catalan numbers for every n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
So if we entered n =3 we should get 5 as an output from the program
Some of few applications of Catalan numbers −
- Counting the number of possible binary search trees with n keys.
- Finding the number of expressions containing n pair of parenthesis which are correctly matched. Like for n = 3 the possible parenthesis expression would be ((())), ()(()), ()()(), (())(), (()()).
- Finding number of ways to connect point on circle disjoint chords, and many more.
Example
的中文翻译为：
示例
Input: n = 6
Output: 132
Input: n = 8
Output: 1430
登录后复制
解决给定问题的方法 −
- 输入n。
- 检查如果n
