卡特兰数

本文主要是介绍卡特兰数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

卡特兰数，一个特殊的数列。通项公式为：

\[Cat_n=\frac {C_{2n}^n}{n+1} \]

从\(0\)开始的前几项为：\(1,1,2,5,14,42,132,\cdots\)，所以有的题可以直接打个表看看（比如这个）

然后是它是怎么推出来的，最主要的就是从\((0,0)\)到\((n,n)\)不穿过直线\(y=x\)的路径计数（不想上图了，可以手画一个）。首先我们随便走的走法就是\(2n\)步里面选\(n\)步向上剩下\(n\)步向右，就是\(C_{2n}^n\)。

然后减去不合法的方案数。我们发现，如果穿过直线\(y=x\)，那必然接触直线\(y=x+1\)。然后我们把第一个接触点之后向右和向上的走法反转，那么它就会走到\((n-1,n+1)\)，走法数显然是\(C_{2n}^{n+1}\)。于是一个公式就是

\[Cat_n=C_{2n}^n-C_{2n}^{n+1} \]

还有一些其他的公式：

\[Cat_n=\frac {Cat_{n-1}(4n-2)}{n+1} \]

\[Cat_n=\sum_{i=1}^nCat_{i-1}Cat_{n-i}(n\ge 2) \]

最后是一些常用的卡特兰数模型：

1. 一个\(01\)串，\(n\)个\(0n\)个\(1\)。使任意前缀中\(0\)的个数不小于\(1\)的个数的方案数为\(Cat_n\)。
2. \(n\)个点的有标号二叉树的个数为\(Cat_n\)。
3. 一个栈的进栈序列为\(1,2,\cdots n,\)则不同的出栈序列个数为\(Cat_n\)。
4. 圆上\(2n\)个点，用\(n\)条线段成对连接，不相交的方案数为\(Cat_n\)。
5. 将一个凸多边形剖分成\(n\)个三角形的方案数为\(Cat_n\)。

这篇关于卡特兰数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！