卡特兰数

卡特兰数的基本公式

通项公式
$C(n)=\frac{C_{2n}^{n}}{n+1}$
变形公式
$C(n)=C_{2n}^{n}-C_{2n}^{n-1}$
递推公式
$C(n)=\sum_{i=0}^{n-1}C(i)\times C(n-i-1)$
$C(n+1)=\frac{4n+2}{n+2}C(n)$

基本形式

给出 $2n$ 个元素，其中 $n$ 个 $A$ 元素， $n$ 个 $B$ 元素，要求对于由两种元素按顺序排列组成的序列中，任意一个前缀 $B$ 的数量不少于 $A$ ,有多少种组合方式
个节点的二叉树共有多少个
- 可以将一棵二叉树分为根，左子树，右子树三部分，枚举左子树节点个数，则共有 $\sum_{i=0}^{n-1}C(i)\times C(n-i-1)$ 种不同的二叉树

数学-卡特兰数

卡特兰数

卡特兰数的基本公式

基本形式