卡特兰数是一个重要的数学概念，我们先看它的公式：
天哪这是什么？？
这样的公式不够直观，更直观的表现形式是：
好看多了
也就是 从2n里挑出n个元素的情况数 减去 从2n里挑出n+1个元素的情况数。这就是卡特兰数了。
卡特兰数的应用
基本模型
有一个长度为2n的01序列，其中1,0各n个，要求在任意位置1的总数不能大于0。求可能的01排序个数。
这里可以把0视为进栈，1视为出栈。栈必须非空才能出。
思路1：
01随机排2n的个数 C（2n n）
一旦出现第一个不满足条件的1（也就是此时有k个0，k+1个1），将后面的所有0变成1,1变成0。
通过这种变换，只要遇到非法情况，必有 n-1个0 与 n+1个1，所以非法情况个数是 C（2n n+1）
思路2：
我们建立直角坐标系，认为出现一个0为向右走一步，出现一个1为向上走一步。从（0,0）走到（n,n）。
不考虑条件共（2n n）种走法，也就是第个二公式的前面一半，下面只需减去不符合条件的走法即可。
很容易知道，符合条件的走法一定不会 越过y=x 这条线, 但是“越过”不好计算，我们转化成 碰到y=x+1
沿用思路一，一旦非法（碰到y=x+1），我们互换非法之后所有的01（与y=x+1镜像），此时线的终点为（n-1, n+1）
这就是说明只要非法，我们将到达（n-1, n+1）， 所有的非法情况 = 从 (0, 0) 到 (n - 1, n + 1) 的路径个数
不符合条件的走法个数 = 碰到y=x+1的走法个数 = 从（0,0）到点 （n-1,n+1）的走法个数 = C （2n n+1） 由此可得出卡特兰数
网友评论