1. 栈的输出序列数
一个栈的输入序列是 ，不可能的输出序列有哪些？算一下 的全排列有多少种，合法的出栈序列的个数是 Catalan 数，两者相减就是不可能的序列的个数。
Catalan 数（卡特兰数）的定义令 ，Catalan 数满足递归式：，该递推关系的解为：（其中 表示 个中取 个的组合数）。
问题描述：12 个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？
问题分析：我们先把这 12 个人从矮到高排列，然后，选择 6 个人排在第一排，那么剩下的 6 个肯定是在第二排。用 0 表示对应的人在第一排，用 1 表示对应的人在第二排，那么含有 6 个 0，6 个 1 的序列，就对应一种方案。
比如 就对应着
第一排：
第二排：
就对应着
第一排：
第二排：
问题转换为，这样的满足条件的 序列有多少个。观察 1 的出现，我们考虑这个 1 出现能不能放在第二排，显然，在这个 1 之前出现的那些 对应的人要么是在这个 1 左边，要么是在这个 1 前面。而肯定要有一个 0 的（即这个人若是第二排的排头，则他前面有一个人比他矮，也就是第一排的排头，因此，这个人前面至少要有一个 0），在这个 1 前面，统计在这个 1 之前的 0 和 1 的个数。也就是要求，0 的个数大于 1 的个数。
OK，问题已经解决。
如果把 0 看成入栈操作，1 看成出栈操作，就是说给定 6 个元素，合法的入栈出栈序列有多少个（此处的 6 个元素应该是任意的，但是入栈序列应该是确定的，合法的出栈序列有多少个）。这就是 Catalan 数，这里只是用于栈，等价地描述还有，二叉树的枚举、多边形分成三角形的个数、圆括弧插入公式中的方法数，其通项是 。
在《计算机程序设计艺术》，第三版，Donald E. Knuth著，苏运霖译，第一卷，508页，给出了证明：
问题大意是用 表示入栈， 表示出栈，那么合法的序列有多少个（ 的个数为 ），显然有 个含 各 个的序列，剩下的是计算不允许的序列数（它包含正确个数的 和 ，但是违背其它条件）。在任何不允许的序列中，定出使得 的个数超过 的个数的第一个 的位置。然后在导致并包括这个 的部分序列中，以 代替所有的 并以 代表所有的 。结果是一个有 个 和 个 的序列（此处的序列是指原序列的前面部分 $S$ 和 $X$ 互换后的完整序列）。反过来，对这种类型的每个序列，我们都能逆转这个过程，而且找出导致它的前一种类型的不允许序列。例如 必然来自 。这个对应说明，不允许的序列的个数是 ，因此答案为 。
验证：其中 表示前排， 表示后排，在枚举出前排的人之后，对应的就是后排的人了，然后再验证是不是满足后面的比前面对应的人高的要求。
#include <iostream>
using namespace std;
int bit_cnt(int n)
{
int result = 0;
for (; n; n &= n-1, ++result);
return result;
}
int main(void)
{
int F[6], B[6];
int i, j, k, state, ok, ans = 0;
for (state = 0; state < (1 << 12); ++state) {
if (bit_cnt(state) == 6) {
i = j = 0;
for (int k = 0; k < 12; ++k) {
if(state & (1 << k))
F[i++] = k;
else
B[j++] = k;
}
ok = 1;
for (k = 0; k < 6; ++k) {
if (B[k] < F[k]) {
ok = 0;
break;
}
}
ans += ok;
}
}
cout << ans << endl;
return 0;
}
结果：132
而 $C(12, 6)/7 = 12 times 11 times 10 times 9 times 8 times 7/(7 times 6 times 5 times 4 times 3 times 2) = 132$
注意：$C(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)$
有编号为 1 到 $n$（$n$ 可以很大，不妨在这里假定可以达到 10 亿）的若干个格子，从左到右排列。在某些格子中有一个棋子，不妨设第 $i$ 格有棋子（$1 leq i leq k, 1leq kleq n$），每次一个人可以把一个棋子往左移若干步，但是不能跨越其它棋子，也要保证每个格子至多只有一个棋子。两个人轮流移动，移动不了的为输，问先手是不是有必胜策略。
Catalan 数的典型应用：
1、括号化问题。矩阵链乘：$ P = A_1 times A_2times A_3 times cdots times A_n $，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
一个有 $n$ 个 $X$ 和 $n$ 个 $Y$ 组成的字符串，且所有的部分字符串皆满足 $X$ 的个数大于等于 $Y$ 的个数。以下为长度为 6 的字符串：</br>
$XXXYYY quad XYXXYY quad XYXYXY quad XXYYXY quad XXYXYY$</br>
将上例的 $X$ 换成左括号，$Y$ 换成右括号，$Cn$ 表示所有包含 $n$ 组括号的合法运算式的个数：
$ ((())) quad ()(()) quad ()()() quad (())() quad (()())$
2、将多边形划分为三角形问题。将一个凸多边形区域分成三角形区域（划分线不交叉）的方法数？类似：在圆上选择 $2n$ 个点，将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数？
3、出栈次序问题。一个栈（无穷大）的进栈序列为 $1,2,3,cdots,n$，有多少个不同的出栈序列？类似：有 $2n$ 个人排成一行进入剧场。入场费 5 元。其中只有 $n$ 个人有一张 5 元钞票，另外 $n$ 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？（将持 5 元者到达视作将 5 元入栈，持 10 元者到达视作使栈中某 5 元出栈）。类似：一位大城市的律师在他住所以北 $n$ 个街区和以东 $n$ 个街区处工作，每天她走 $2n$ 个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
分析：对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态 ‘1’，出栈设为状态 ‘0’。$n$ 个数的所有状态对应 $n$ 个 1 和 $n$ 个 0 组成的 $2n$ 位二进制数。由于等待入栈的操作数按照 $1, 2, cdots, n$ 的顺序排列、入栈的操作数 $b$ 大于等于出栈的操作数 $a, a≤b$，因此输出序列的总数目 $=$ 由左而右扫描由 $n$ 个 1 和 $n$ 个 0 组成的 $2n$ 位二进制数，1 的累计数不小于 0 的累计数的方案种数。
4、给定结点组成二叉树的问题。
给定 $N$ 个结点，能构成多少种形状不同的二叉树？（一定是二叉树！先取一个点作为顶点，然后左边依次可以取 0 至 $N-1$ 个相对应的，右边是 $N-1$ 到 0 个，两两配对相乘，就是 $h(1) h(n-1) + h(2) h(n-2) + cdots + h(n-1) h(0)=h(n)) $ （能构成 $h(N)$ 个）
在 $2n$ 位二进制数中填入 $n$ 个 1 的方案数为 $C(2n,n)$，不填 1 的其余 $n$ 位自动填 0。从中减去不符合要求（由左而右扫描，0 的累计数大于 1 的累计数）的方案数即为所求。
不符合要求的数的特征是由左而右扫描时，必然在某一奇数位 $2m+1$ 位上首先出现 $m+1$ 个 0 的累计数和 $m$ 个 1 的累计数，此后的 $2(n-m)-1$ 位上有 $n-m$ 个 1 和 $n-m-1$ 个 0。如若把后面这 $2(n-m)-1$ 位上的 0 和 1 互换，使之成为 $n-m$ 个 0 和 $n-m-1$ 个 1，结果得 1 个由 $n+1$ 个 0 和 $n-1$ 个 1 组成的 $2n$位数，即一个不合要求的数对应于一个由 $n+1$ 个 0 和 $n-1$ 个 1 组成的排列。
反过来，任何一个由 $n+1$ 个 0 和 $n-1$ 个 1 组成的 $2n$ 位二进制数，由于 0 的个数多 2 个，$2n$ 为偶数，故必在某一个奇数位上出现 0 的累计数超过 1 的累计数。同样在后面部分 0 和 1 互换，使之成为由 $n$ 个 0 和 $n$ 个 1 组成的 $2n$ 位数，即 $n+1$ 个 0 和 $n-1$ 个 1 组成的 $2n$ 位数必对应一个不符合要求的数。
因而不合要求的 $2n$ 位数与 $n＋1$ 个 0，$n－1$ 个 1 组成的排列一一对应。
显然，不符合要求的方案数为 $C(2n,n+1)$。由此得出输出序列的总数目 $=C(2n,n)-C(2n,n+1)=1/(n+1)C(2n,n)$。（这个公式的下标是从 $h(0)=1$ 开始的）
近期评论