卡特兰数（Catalan number）是组合数学中一个常在各种计数问题中出现的数列，以比利时的数学家欧仁·查理·卡塔兰（1814–1894）命名。清代数学家明安图（1692年~1763年）在其《割圜密率捷法》中最早用到“卡塔兰数”，远远早于卡塔兰。卡特兰数有多种公式和应用，下面是一些常见的公式及其解释：

卡特兰数的基础公式

定义式：f[n]=∑i=0n−1f[i]f[n−1−i]。这个公式表示第n个卡特兰数是由前n-1个卡特兰数两两相乘后求和得到的。

组合数公式：f[n]=C2nn−C2nn−1。这里C2nn表示从2n个不同项中取出n个的组合数。这个公式通过组合数的方式计算卡特兰数。

卡特兰数的应用

卡特兰数在各种实际问题中有广泛的应用，包括但不限于：

括号匹配问题：n个左括号和n个右括号，对于每一个位置，左括号数大于等于右括号数的方案总数。这可以用卡特兰数来计算。

满二叉树形态数：n个非叶节点的满二叉树的形态数。满二叉树是将括号匹配问题中的每个子节点的空儿子上都加上叶子形成的，因此也可以用卡特兰数来计算。

网格路径问题：在一个n*n的正方形网格中，每次只能向右或向上移动一格，从左下角到右上角所有在副对角线右下方的路径总数也是卡特兰数。

卡特兰数的递推关系

卡特兰数也满足递推关系，即每一个卡特兰数都可以由前面的卡特兰数计算得到。例如，第n个卡特兰数f(n)可以由f(0)到f(n-1)计算得出。

卡特兰数的数列

卡特兰数列的前几项是：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796