卡特兰数是组合数学中的一种著名数列，通常用如下通项式表示：
递推表示：
组合表示:
1.一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
2.有一个长度为2n的01序列，其中1,0各n个，要求对于任意的整数k∈[1,n]，数列的前k个数中，1的个数不少于0。
构造:从坐标（0，0）到（2n，0），每一步两种走法：(x+1 , y+1)或(x-1 , y-1).条件：任何时候y不能小于0.求多少走法.
解：就是说走的路径不应该穿过x轴，即直线y=0，也就是不接触y=?1于是我们把与y=?1的接触点的右边整条路径以y=?1为对称轴翻折，于是终点变为了(2n,?2)
那么此时，从(0,0)到(2n,?2)的路径必定至少穿过一次y=?1，不满足条件，那么此时的路径数量即为总路径数中不符合题意的路径数，那么我们用总路径数减去不符合的路径数，就是最终的答案。
1.洛谷1641 生成字符串
2.Loj10238网格
3.洛谷P2532 树屋阶梯
4.洛谷P3200 有趣的数列
原文：https://www.cnblogs.com/nonames/p/12825101.html