KV熵的Blog

什么是卡特兰数

卡特兰数是一类特殊的数列，常用于解决组合数学中的一些计数问题。

能解决哪些问题

举个例子：有一个数$x$，初始值为 0，我们可以对$x$进行 $n$次操作，每次操作只能给$x$加 1 或减 1，并且始终保证$x \ge 0$，有几种操作方法。

这个问题的答案就是卡特兰数的第$n$项。

公式

令卡特兰数第$n$项为$h(n)$

• 定义式：点击查看
• 通项公式：$h(n) = \frac{C^n_{2n}}{n+1}$
• 递推公式：$h(0) = 1, h(n) = \frac{4n-2}{n+1} \times h(n-1)$