也许更好的阅读体验

学卡特兰数我觉得可能比组合数要难一点，因为组合数可以很明确的告诉你那个公式是在干什么，而卡特兰数却像是在用大量例子来解释什么时卡特兰数 这里，我对卡特兰数做一点自己的理解 卡特兰数是一个在组合数学里经常出现的一个数列，它并没有一个具体的意义，却是一个十分常见的数学规律

对卡特兰数的初步理解：有一些操作，这些操作有着一定的限制，如一种操作数不能超过另外一种操作数，或者两种操作不能有交集等，这些操作的合法操作顺序的数量

为了区分组合数，这里用\(f_n\)表示卡特兰数的第\(n\)项 从零开始，卡特兰数的前几项为\(1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790\ldots\)

递归定义

\(f_n=f_0*f_{n-1}+f_1*f{n-2}+\ldots+f_{n-1}f_{0}\)，其中\(n\geq 2\)

递推关系

\(f_n=\frac{4n-2}{n+1}f_{n-1}\)

通项公式

\(f_n=\frac{1}{n+1}C_{2n}^{n}\)

经化简后可得

\(f_n=C_{2n}^{n}-C_{2n}^{n-1}\)

只要我们在解决问题时得到了上面的一个关系，那么你就已经解决了这个问题，因为他们都是卡特兰数列

先用一个最经典的问题来帮助理解卡特兰数 去掉了所有的掩饰，将问题直接写出来就是

在一个\(w\times h\)的网格上，你最开始在\(\left(0,0\right)\)上，你每个单位时间可以向上走一格，或者向右走一格，在任意一个时刻，你往右走的次数都不能少于往上走的次数，问走到\(\left(n,n\right),0\leq n\)有多少种不同的合法路径。

合法路径个数为\(C_{2n}^{n}-C_{2n}^{n-1}\)

直接求不好，考虑求有多少种不合法路径 路径总数为在\(2n\)次移动中选\(n\)次向上移动，即\(C_{2n}^{n}\)

画一下图，我们把\(y=x+1\)这条线画出来，发现所有的合法路径都是不能碰到这条线的，碰到即说明是一条不合法路径 先随便画一条碰到这条线的不合法路径，所有的不合法路径都会与这条线有至少一个交点，我们把第一个交点设为\(\left(a,a+1\right)\) 如图

我们把\(\left(a,a+1\right)\)之后的路径全部按照\(y=x+1\)这条线对称过去 这样，最后的终点就会变成\(\left(n-1,n+1\right)\)

由于所有的不合法路径一定会与\(y=x+1\)有这么一个交点 我们可以得出，所有不合法路径对称后都唯一对应着一条到\(\left(n-1,n+1\right)\)的路径 且所有到\(\left(n-1,n+1\right)\)的一条路径都唯一对应着一条不合法路径（只需将其对称回去即可） 所以不合法路径总数是\(C_{2n}^{n-1}\)

那么合法的路径总数为\(C_{2n}^{n}-C_{2n}^{n-1}\)

这是一个非常好用且重要的一个方法，其它的问题也可以用该方法解决 即找到不合法路径唯一对应的到另一个点的路径 如网格计数

先将方法写在前面吧 相信大家都听过烧开水这个数学小故事吧 和学习数学一样，转化是基本思路，将一个问题转化为另外一个已经解决了的问题是最重要的

你现在有\(n\)个\(0\)和\(n\)个\(1\)，问有多少个长度为\(2n\)的序列，使得序列的任意一个前缀中\(1\)的个数都大于等于\(0\)的个数 例如\(n=2\)时 有\(1100,1010\)两种合法序列 而\(1001,0101,0110,0011\)都是不合法的序列

合法的序列个数为\(C_{2n}^{n}-C_{2n}^{n-1}\)

我们把出现一个\(1\)看做向右走一格，出现一个\(0\)看做向上走一格，那么这个问题就和上面的例题\(1\)一模一样了

拓展 如果是\(n\)个\(1,m\)个\(0\)呢？ 不过是最后的终点变为了\(\left(n,m\right)\)罢了 如果是\(1\)的个数不能够比\(m\)少\(k\)呢 我们只需将\(y=x+1\)这条线上下移动即可

你有\(n\)个左括号，\(n\)个右括号，问有多少个长度为\(2n\)的括号序列使得所有的括号都是合法的

合法的序列个数为\(C_{2n}^{n}-C_{2n}^{n-1}\)

要使所有的括号合法，实际上就是在每一个前缀中左括号的数量都不少于右括号的数量 将左括号看做\(1\)，右括号看做\(0\)，这题又和上面那题一模一样了

有一个栈，我们有\(2n\)次操作，\(n\)次进栈，\(n\)次出栈，问有多少中合法的进出栈序列

合法的序列个数为\(C_{2n}^{n}-C_{2n}^{n-1}\)

要使序列合法，在任何一个前缀中进栈次数都不能少于出栈次数\(\ldots\) 后面就不用我说了吧，和上面的问题又是一模一样的了

一个长度为\(n\)的排列\(a\)，只要满足\(i