卡特兰数,一个特殊的数列。通项公式为:
\[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) \]最后是一些常用的卡特兰数模型: