In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).

The n^th Catalan number is given directly in terms of binomial coefficients by

{\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}=\prod \limits _{k=2}^{n}{\frac {n+k}{k}}\qquad {\text{for }}n\geq 0.}

The first Catalan numbers for n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, …

Given N (N > 1 and N is even number) dots spaced on the circumfence of a circle, find out how many lines can be connected between any two points without crossing others.

Sample Input:

N = 6

Sample Output:

Catalan Numbers

As shown in the above image, there are only 5 ways to connect lines with 6 points without crossing lines.

数据结构和算法：初级练习题 #62 卡塔兰数和组合

卡塔兰数是组合数学中一种常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。1730年左右被蒙古族数学家明安图 (1692-1763) 使用于对三角函数幂级数的推导而首次发现。

其数学计算公式和二项式系数直接相关：

其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, ….

给定圆周上的 N 个点（N为2的倍数），计算两两连线并且所有连线都不能交叉的情况有多少种。

输入样例：

N = 6

输出样例：

用六个点画三条线并且没有交叉的情形只有五种，如上图所示。

Python Solution

Catalan Numbers