浅谈卡特兰数

本篇随笔浅谈一下数学中的卡特兰数。

卡特兰数博大精深，由于博主时间、精力、水平都非常非常有限，所以只挑干货讲。

引入：

给定\(n\)个0，\(n\)个1，按某种顺序排成长度为\(2n\)的序列，求满足任意前缀中0的个数不少于1的个数的序列的数量。

答案即卡特兰数。

设第\(i\)项卡特兰数为\(Cat_i\)，其通项公式为：

常用的卡特兰数公式

抄公式啦！

卡特兰数的一些常见应用

比如引入。

\(n\)个0，\(n\)个1，组成的\(2n\)的序列，对于每个前缀都有0的个数不小于1的个数的序列个数。

同理，括号匹配也可以用这个东西。就把0变成左括号，1变成右括号即可。

也就是，\(n\)个左右括号组成的合法括号序列数量为\(Cat_n\)。

1-n经过一个栈，形成的合法出栈序列数量为\(Cat_n\)。

n个节点构成的不同二叉树数量为\(Cat_n\)。

在平面直角坐标系中，每一步只能向上走或者向右走，从\((0,0)\)走到\((n,m)\)并且除了两个端点外不接触\(y=x\)的路线数量为\(2Cat_{n-1}\)。

浅谈卡特兰数

原文：https://www.cnblogs.com/fusiwei/p/13751597.html