卡塔兰数

卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡特兰（1814–1894）命名。历史上，清朝数学家明安图（1692年－1763年）在其《割圜密率捷法》中最先发明这种计数方式，远远早于卡塔兰。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。

卡塔兰数的一般项公式为

${\displaystyle C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n+1)!n!}}$的另一个表达形式为

${\displaystyle C_n=(\genfrac{}{}{0ex}{}{2n}{n})-<!--\; -\; -->(\genfrac{}{}{0ex}{}{2n}{n+1})\text{ for }n\ge <!--\; \ge \; -->1}$是一个自然数；这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。（见https://en.wikipedia.org/wiki/Catalan_number#Second_proof。）

递推关系：

它也满足

这提供了一个更快速的方法来计算卡塔兰数。

卡塔兰数的渐近增长为

它的含义是当 → ∞时，左式除以右式的商趋向于1。（这可以用!的斯特灵公式来证明。）

所有的奇卡塔兰数都满足${\displaystyle n=2^k-<!--\; -\; -->1}$令1表示进栈，0表示出栈，则可转化为求一个位、含个1、个0的二进制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含个1、个0的位二进制数共有${\displaystyle (\genfrac{}{}{0ex}{}{2n}{n})}$个1、个0的2n位二进制数，扫描到第位上时有个0和个1（容易证明一定存在这样的情况），则后面的0-1排列中必有个1和个0。将及其以后的部分0变成1、1变成0，则对应一个个0和个1的二进制数。反之亦然（相似的思路证明两者一一对应）。

从而${\displaystyle C_n=(\genfrac{}{}{0ex}{}{2n}{n})-<!--\; -\; -->(\genfrac{}{}{0ex}{}{2n}{n+1})=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})}$的取值为多少，×的汉克尔矩阵:${\displaystyle A_{i,j}=C_{i+j-<!--\; -\; -->2}.}$ = 4 时我们有

进一步，无论的取值为多少，如果矩阵被移动成${\displaystyle A_{i,j}=C_{i+j-<!--\; -\; -->1}.}$ = 4 时我们有

同时，这两种情形合在一起唯一定义了卡塔兰数。