最后更新日期：2010-12-02
读了我的文章一个 Lua 的凑24程序的读者可能会产生这样的疑问：
- 为什么由 4 个数字和 3 个运算符组成的合法的逆波兰式就只有那 5 种？你是怎么穷举的？
- 为什么不写程序自动求出所有的合法逆波兰式，而非要手算？
为了讨论这两个问题，我们先来看下面的问题：
问题1（出栈序列问题）：数 1 ~ n 按顺序入栈（栈是后进先出的），任何时刻你可以选择让下一个数入栈，或者让当前栈顶元素出栈（若栈非空）。求所有可能的出栈序列的个数。
例：
若 n = 2，有两种：
- 进进出出，得到出栈序列：2 1
- 进出进出，得到出栈序列：1 2
若 n = 3，有五种：（下面以 1 表示进栈，-1 表示出栈）
- 1 -1 1 -1 1 -1，得到：1 2 3
- 1 -1 1 1 -1 -1，得到：1 3 2
- 1 1 -1 -1 1 -1，得到：2 1 3
- 1 1 -1 1 -1 -1，得到：2 3 1
- 1 1 1 -1 -1 -1，得到：3 2 1
我们注意到：n = 3 时的出栈序列有 5 种，正好跟 4 个数字和 3 个运算符构成的逆波兰式个数相等！
于是我们猜想：这两个问题是等价的。
为了证实这个猜想，我们把出栈序列问题改写成下面的形式：
问题2（1，-1排列问题）：将 n 个 1 和 n 个 -1 排成序列 S_{2n}，使得对任意的 k \in [1, 2n]，满足 \sum_{i=1}^{k}{s_i \geq 0} ，。求所有排列的个数。
注意到在问题1中，若出栈入栈操作的排列顺序不同，则最后得到的数字序列也一定不同，因此出栈序列数就等于操作的排列个数，于是问题1与问题2等价。
回顾逆波兰式的计算过程：每当遇到一个数字，就入栈，相当于栈中元素个数 +1，而每遇到一个运算符就出栈两个数字，运算后结果入栈，相当于栈中元素个数 -1。我们还要求中间任何一步时栈中元素个数 >= 1。
如果把入栈操作（或 1）对应于逆波兰式中的数字，出栈操作（或 -1）对应于逆波兰式中的运算符，我们立即得到：
n + 1 个数字和 n 个运算符组成的合法逆波兰式的个数问题，与 n 个数的出栈序列问题等价。不同之处在于逆波兰式问题中，栈里始终有一个数字。
再做进一步联想，逆波兰式相当于对表达式树做后序遍历，于是我们不禁要问：逆波兰式的个数问题与表达式树，或者说二叉树的个数问题是否等价？
问题3（二叉树计数）：求 n 个结点的二叉树的个数。
例：当 n = 3 时，有 5 种：
为了进一步讨论这个问题，我们先来看一下如何求 n 个数的出栈序列的个数 Cn。
为此我们将 1，-1 排列问题改写成下面的 x ≥ y 格路问题。
问题4（x≥y格路问题）如图在 n * n 的方格中每次只能要么向右走，要么向上走。在 x ≥ y 的区域中，从 A 到 B 有多少种走法？
将 1 与向右对应，-1 与向上对应，不难看出这两个问题的等价性。
下面就来求解这个问题。
设走法数为 Cn，考虑寻找 Cn 的递推公式。
以下将 A 到 B 的那条斜线称为“大斜线”，斜线上的点记为 A0(= A), A1, A2, … , An(= B)。
有如下推论：从 A 到 B，且不经过 A1, A2, … , An-1 中任何一点的走法有 Cn-1 种。
证：从 A 到 B，且不经过 A1, A2, … , An-1 中任何一点相当于从 D 走到 E 的 x≥y格路问题，故有 Cn-1 种走法。证毕。
对于从 A 到 B 的任意一条路径，记这条路径中，第一次碰到大斜线的那个点为 F。则我们可以把 A 到 B 的所有路径分成如下 n 类：
F = A1
F = A2
…
F = An = B
注意前面 F 的定义是第一次碰到大斜线，故 F 之前的路径都没碰到。易证对于任意一条 A 到 B 的路径 L，它一定属于某一个分类，而且不可能同时属于两个不同的分类。可见这些分类是互不相交的，而且正好完全覆盖了 A 到 B 的所有路径。
于是我们可以分别计算每一类的数量。
对 F = Ai，显然 A 到 F 以及 F 到 B 可以看成 i 阶和 n - i 阶 x≥y格路问题，又由于 A 到 F 时没有碰大斜线，故有 Ci-1 种，而 F 到 B 有 Cn-i 种，故由乘法原理，第 i 类有：Ci-1Cn-i 种。加起来得：
C_n = C_0 C_{n-1} + C_1 C_{n-2} + ... + C_{n-1}C_0, \ \ C_0 = 1 \ \ (1)
这样我们就得到了 Cn 的递推公式。
下面再来看二叉树计数问题。设 n 个结点的二叉树有 Cn 种，除去根之后还有 n-1 个结点，给左子树分 i 个结点，则右子树有 n-1-i 个结点。显然左右子树分别化为两个低阶的二叉树计数问题。于是令 i 从 0 取到 n-1，我们得到：
C_n = C_0 C_{n-1} + C_1 C_{n-2} + ... + C_{n-1}C_0, \ \ C_0 = 1
与上面的递推公式一样。故：二叉树计数问题与逆波兰式计数问题等价。
问题5（多边形划分）：将 n+2 边凸多边形划分成三角形，只能在两个顶点之间连线，每个顶点看作是不同的。有多少种划分方法？
例：n = 3 时，五边形显然有五种划分，即从每个顶点连出两条线。
这个问题与前面几个问题的等价性留给读者自证。
下面我们就来求解递推关系 (1) 式。
问题6：已知：C_0 = 1，C_n = C_0 C_{n-1} + C_1 C_{n-2} + ... + C_{n-1}C_0。求：C_n。
解：（母函数法）
将数列 {C_n} 作为形式幂级数的系数，构造出数列 {C_n} 的母函数：
f(x) = C_0 + C_1 x + C_2 x^2 + ... + C_n x^n + ...
于是：
\begin{aligned} f^2(x) &= (C_0 + C_1 x + C_2 x^2 + ... + C_2 x^n + ...)(C_0 + C_1 x + C_2 x^2 + ... + C_n x^n + ...) \\ &= C_0 C_0 + (C_0 C_1 + C_1 C_0)x + (C_0 C_2 + C_1 C_1 + C_2 C_0)x^2 + ... \\ &= C_1 + C_2 x + C_3 x^2 + ... + C_{n+1} x^n + ... \end{aligned}
将上式两边同乘以 x，再加 C_0 (= 1)，得：
\begin{aligned} 1 + xf^2(x) &= C_0 + C_1 x + C_2 x^2 + ... + C_{n+1}x^{n+1} + ... \\ &= f(x) \end{aligned}
于是我们得到关于 f(x) 的方程：
1 + xf^2(x) = f(x)
解之，得：
f(x) = \frac{1\pm\sqrt{1-4x}}{2x} \ \ (2)
对上式作泰勒展开（准确说是形式幂级数展开，反正就那个东西）：
回顾泰勒公式：
(1+x)^a = 1 + ax + \frac{a(a-1)}{2!}x^2 + ... + \frac{a(a-1)(a-n+1)}{n!}x^n + ...
令 x = -4x，a = 1/2 代入，得：
\sqrt{1-4x} = 1 + \frac12(-4)x + ... + \frac{\frac12(\frac12-1)(\frac12-n+1)}{n!}(-4)^n x^n + ...
其通项可化为：
\begin{aligned} - \frac{\frac12(1-\frac12)...(n-1-\frac12)}{n!}4^n x^n &= - \frac{1\cdot 3 \cdot 5 \cdots [2(n-1)-1]}{2^n n!}4^n x^n \\ &= - \frac{(2n-3)!}{2\cdot 4 \cdots [2(n-2)]n!}2^n x^n \\ &= - \frac{(2n-3)!}{2^{n-2}(n-2)!n!}2^n x^n \end{aligned}
由于 C_n > 0，故可知 (2) 式中应取负号。上面的通项取负后，再除以 2x，得到 f(x) 的通项：
\frac{2(2n-3)!}{n!(n-2)!}x^{n-1}
故：
C_{n-1} = \frac{2(2n-3)!}{n!(n-2)!} = \frac{(2n-2)!}{n!(n-1)!}
C_n = \frac{(2n)!}{n!(n+1)!} = \frac1{n+1}\binom{2n}{n}
这个数在组合数学中被称为卡塔兰数。
由此我们看到，从一个看似简单的逆波兰式计数问题，可以挖掘出这么多东西，其实写程序枚举所有合法的逆波兰式是可以的，相当于枚举所有满足要求的 1，-1 序列。只不过对于一个凑24程序来说太复杂，就省了。
下面是我的枚举 1，-1 序列程序：
#include <stdbool.h>
#include <stdio.h>
/**
* 根据当前的序列和 n，得到下一个序列。
* 对这个函数来说，第一个序列是 1，-1 交错状态，
* 最后一个序列是前面全是 1，后面全是 -1。
*
* @param ar 当前序列值，必须有 2n 项
* @param n
* @return true若下一个序列存在，false若当前已经是最后一个序列
*/
bool nextSeq(int ar[], int n)
{
int sm1, s1;
int i = 2 * n - 1;
while (ar[i] == -1) // 寻找末尾连续的 -1
{
i--;
}
sm1 = 2 * n - i;
while ((ar[i] == 1)&&(i >= 0)) // 寻找 -1 之后连续的 1
{
i--;
}
if (i < 0)
{
return false;
}
s1 = 2 * n - 1 - i - sm1;
ar[i] = 1; // 将这个 -1 改成 1
i++;
int j;
// 填充剩下的
for (j = sm1 - s1; j > 0; j--)
{
ar[i] = -1;
i++;
}
for (j = s1; j > 0; j--)
{
ar[i] = 1;
ar[i + 1] = -1;
i += 2;
}
return true;
}
int main(int argc, char *argv[])
{
int n = 4;
int ar[2 * n];
int i;
int count = 0;
for (i = 0; i < n; i++)
{
ar[2 * i] = 1;
ar[2 * i + 1] = -1;
}
do
{
for (i = 0; i < 2 * n; i++)
{
printf("%d ", ar[i]);
}
printf("\n");
count++;
} while(nextSeq(ar, n));
printf("count: %d\n", count);
return 0;
}这个程序用 C 语言编写，用到了部分 C99 特性，比如 bool 型，栈上的动态大小数组等，编译器用的是 GCC 4.5。codepad 的运行结果：http://codepad.org/3u8eLcar
修改 main 函数中 n 的值可以输出不同的 n 的值的结果。nextSeq() 函数根据当前的序列计算下一个序列，时间复杂度 O(n)。