卡特兰数(英语:Catalan number),又称卡塔兰数、明安图数,是组合数学中一种常出现

的数列，以比利时数学家卡塔兰（Catalan）命名。

卡特兰数常用来描述有趣的计数问题，如括号匹配序列、凸多边形三角剖分个数、山脉问题、矩阵链乘法次序等等。在计算机科学中，卡特兰数也有广泛的应用，如动态规划、回溯算法、组合计数等领域。

由于卡特兰数的计算比较复杂，因此在实际应用中一般采用递推或公式的方式来计算，其中递推的方法较为常用。

卡特兰数的第n项可以用以下递推式来计算：

C(n)=C(0)C(n-1)+C(1)C(n-2)+...+C(n-1)C(0)

其中C(0)=1，而C(n)表示第n个卡特兰数。该递推式的时间复杂度为O(n^2)，因此计算较大的卡特兰数时需要采用优化算法来提高效率。

卡特兰数还有许多有趣的性质，如下面几个：

1.卡特兰数满足递推式C(n)=C(n-1)(4n-2)/(n+1)，时间复杂度为O(n)。

2.卡特兰数的通项公式为C(n)=C(2n,n)/(n+1)，其中C(2n,n)表示2n个元素的排列组合数。

3.卡特兰数的生成函数为C(x)=1/(1-x)exp(x)。

总之，卡特兰数是组合计数中一种重要的数列，它不仅可以应用于实际问题的计数和统计，还可以作为算法设计和分析中的基本工具。