卡特兰数

题：
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?

解：

• 01串表示排队情况
  1-12个数字来表示从低到高的12个人，使用12位的01串表示对应数字位的排队情况，0表示站前排，1表示站后排。
  如001100110101表示：
  前排：12569B
  后排：3478AC
  6个0、6个1组成的12位串总共有C(12,6)种情况。
• 不符合约束的01串
  现在排除其中不符合条件的串。12位01串从第一位到任一位的子串中0的个数不小于1的个数，否则就会出现某列前排为高个儿后排为低个儿的情况。可以这么理解，排队时从第一个人开始放置，优先往前排放置，如果某列前排为空而往后排放置，则未安置的人中无论谁过去都会违背约束。
  如011000001111表示：
  前排：145678
  后排：239ABC
  从第一位到第三位的子串011中1的个数多于0的个数，其对应的排队不符合要求。
  现需要找到所有这种不符合约束的01串。
• 5个1、7个0组成的01串
  对不符合约束的01串，按如下规则进行转换：找到不满足约束的位，将从第一位到这一位的01子串中的0换为1，1换为0。
  如上例中的011000001111，其子串011不满足约束，将其转换为100，此时整个01串为100000001111，这个新串中有5个1、7个0。
  按照这种转换规则，任意一个5个1、7个0的12位01串都可以转换（逆转换）为唯一对应的6个1、6个0的12位01串，且这个串一定是违背约束的01串。因此，所有违背约束的01串的个数为C(12,5)。
• 符合要求的排队方式有
  132=C(12,6)-C(12,5)=(1/(n+1))C(2n,n) 其中n=6

Catalan数(卡特兰数)

Cn = ( 1 / (n + 1))C(2n,n)

Catalan数包含一种递推关系，但个人感觉还是01串、出入栈这两种思维方式更形象更容易理解。下面介绍用出入栈方式理解并解决问题。

题：
进栈序列为1、2、3、……、n，有多少种出栈序列？

解：
总共需要进行n次入栈、n次出栈，用0表示入栈、1表示出栈，则出栈序列可以用2n长度的01串来表示，且从第一位到m(1<m<=n)位的子串中，0的个数不小于1的个数（否则会出现空栈时出栈的情形）。同上可得序列数为
Cn = C(2n,n) - C(2n,n-1) = ( 1 / (n + 1))C(2n,n)

题：
在一场激烈的足球赛开始前，售票工作正在紧张地进行中。每张球票为50元。现有2n个人排队购票，其中有n个人手持50元的钞票，另外n个人手持100元的钞票，假设开始售票时售票处没有零钱。问这2n个人有多少种排队方式，不至使售票处出现找不开钱的局面？

解：
50元买票相当于入栈，100元买票相当于出栈，思路同上，总排队方式数为：
Cn = C(2n,n) - C(2n,n-1) = ( 1 / (n + 1))C(2n,n)

题：
在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数？

解：
1-n个点，01串表示，0表示入栈，1表示出栈。如：0011表示2-3连、1-4连；0101表示1-2连、3-4连。结果同上。