10种比较常见的卡特兰数题
问题1：括号匹配
n对括号有多少种有效配对方式？ 比如n=2是，合法的配对方式有下列两种：
“( )( )” , “( ( ) )” 下列方式是不合法的： “)( )(” “) ) ( (” “) )( )” “( )))” ......
问题2：链乘
P=A1×A2×A3×……×An，依据乘法结合律，不改变其顺序，只用 括号表示成对的乘积，试问有几种括号化的方案？
例如， A1×A2×A3×A4 有下列5种方案： (A1×(A2×(A3×A4))) (A1×((A2×A3)×A4)) ((A1×A2)×(A3×A4)) (((A1×A2)×A3)×A4) ((A1×(A2×A3))×A4)
问题3：进出栈 有n个整数1,2,...,n和一个栈，进栈顺序为1,2,...,n,每个数字都 要出入一次栈，用S表示数字入栈， X表示数字出栈，那么那么合法的序列 有多少个。
比如： n=2,合法的出入栈顺序有： S1 S2 X2 X1 S1 X1 S2 X2
例题4：排队 12个高矮不同的人，排成两排，每排必须是从矮到高排列，而且 第二排比对应的第一排的人高，问排列方式有多少种？
以6个人排队为例，下面是一种合法的排队：
第一排： 1 5 7 第二排： 2 6 8
例题5：二叉树
n个节点构成的二叉树，共有多少种不同情形？
例题6：圆上连点
在圆上选择2n个点，将这些点成对连接起来使得所得到的n条 线段不相交的方法数？
例题7：凸多边形的划分
将一个凸多边形划分成三角形总共有多少种方法？
例题8：找零
有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票， 另外n人只有10元钞票，问题是剧院售票处现在一分钱也没有（没有任何钞 票），问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？
例题9：上班
一位大城市的律师在他住所以北n个街区和以东n个街区处工作，每天她走 2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线， 那么有多少条可能的道路？
例题10：填充
用n个长方形填充一个高度为n的阶梯状图形的方法个数？