逆波兰式与卡塔兰数

最后更新日期：2010-12-02

　　读了我的文章一个 Lua 的凑24程序的读者可能会产生这样的疑问：

1. 为什么由 4 个数字和 3 个运算符组成的合法的逆波兰式就只有那 5 种？你是怎么穷举的？
2. 为什么不写程序自动求出所有的合法逆波兰式，而非要手算？

　　为了讨论这两个问题，我们先来看下面的问题：

问题1（出栈序列问题）：数 1 ~ n 按顺序入栈（栈是后进先出的），任何时刻你可以选择让下一个数入栈，或者让当前栈顶元素出栈（若栈非空）。求所有可能的出栈序列的个数。

若 n = 2，有两种：

1. 进进出出，得到出栈序列：2 1
2. 进出进出，得到出栈序列：1 2

若 n = 3，有五种：（下面以 1 表示进栈，-1 表示出栈）

1. 1 -1 1 -1 1 -1，得到：1 2 3
2. 1 -1 1 1 -1 -1，得到：1 3 2
3. 1 1 -1 -1 1 -1，得到：2 1 3
4. 1 1 -1 1 -1 -1，得到：2 3 1
5. 1 1 1 -1 -1 -1，得到：3 2 1

　　我们注意到：n = 3 时的出栈序列有 5 种，正好跟 4 个数字和 3 个运算符构成的逆波兰式个数相等！

　　于是我们猜想：这两个问题是等价的。

　　为了证实这个猜想，我们把出栈序列问题改写成下面的形式：

问题2（1，-1排列问题）：将 n 个 1 和 n 个 -1 排成序列 S2nS_{2n}S2n​，使得对任意的 k∈[1,2n]k \in [1, 2n]k∈[1,2n]，满足 ∑i=1ksi≥0\sum_{i=1}^{k}{s_i \geq 0}∑i=1k​si​≥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 种。加起来得：

Cn=C0Cn−1+C1Cn−2+...+Cn−1C0,C0=1(1) C_n = C_0 C_{n-1} + C_1 C_{n-2} + ... + C_{n-1}C_0, \ \ C_0 = 1 \ \ (1) Cn​=C0​Cn−1​+C1​Cn−2​+...+Cn−1​C0​,  C0​=1  (1)

　　这样我们就得到了 Cn 的递推公式。

　　下面再来看二叉树计数问题。设 n 个结点的二叉树有 Cn 种，除去根之后还有 n-1 个结点，给左子树分 i 个结点，则右子树有 n-1-i 个结点。显然左右子树分别化为两个低阶的二叉树计数问题。于是令 i 从 0 取到 n-1，我们得到：

Cn=C0Cn−1+C1Cn−2+...+Cn−1C0,C0=1 C_n = C_0 C_{n-1} + C_1 C_{n-2} + ... + C_{n-1}C_0, \ \ C_0 = 1 Cn​=C0​Cn−1​+C1​Cn−2​+...+Cn−1​C0​,  C0​=1

　　与上面的递推公式一样。故：二叉树计数问题与逆波兰式计数问题等价。

问题5（多边形划分）：将 n+2 边凸多边形划分成三角形，只能在两个顶点之间连线，每个顶点看作是不同的。有多少种划分方法？

例：n = 3 时，五边形显然有五种划分，即从每个顶点连出两条线。

　　这个问题与前面几个问题的等价性留给读者自证。

　　下面我们就来求解递推关系 (1) 式。

问题6：已知：C0=1C_0 = 1C0​=1，Cn=C0Cn−1+C1Cn−2+...+Cn−1C0C_n = C_0 C_{n-1} + C_1 C_{n-2} + ... + C_{n-1}C_0Cn​=C0​Cn−1​+C1​Cn−2​+...+Cn−1​C0​。求：CnC_nCn​。

解：（母函数法）

　　将数列 {CnC_nCn​} 作为形式幂级数的系数，构造出数列 {CnC_nCn​} 的母函数：

f(x)=C0+C1x+C2x2+...+Cnxn+... f(x) = C_0 + C_1 x + C_2 x^2 + ... + C_n x^n + ... f(x)=C0​+C1​x+C2​x2+...+Cn​xn+...

f2(x)=(C0+C1x+C2x2+...+C2xn+...)(C0+C1x+C2x2+...+Cnxn+...)=C0C0+(C0C1+C1C0)x+(C0C2+C1C1+C2C0)x2+...=C1+C2x+C3x2+...+Cn+1xn+...\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}f2(x)​=(C0​+C1​x+C2​x2+...+C2​xn+...)(C0​+C1​x+C2​x2+...+Cn​xn+...)=C0​C0​+(C0​C1​+C1​C0​)x+(C0​C2​+C1​C1​+C2​C0​)x2+...=C1​+C2​x+C3​x2+...+Cn+1​xn+...​

　　将上式两边同乘以 xxx，再加 C0(=1)C_0 (= 1)C0​(=1)，得：

1+xf2(x)=C0+C1x+C2x2+...+Cn+1xn+1+...=f(x)\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}1+xf2(x)​=C0​+C1​x+C2​x2+...+Cn+1​xn+1+...=f(x)​

　　于是我们得到关于 f(x)f(x)f(x) 的方程：

1+xf2(x)=f(x) 1 + xf^2(x) = f(x) 1+xf2(x)=f(x)

　　解之，得：

f(x)=1±1−4x2x(2) f(x) = \frac{1\pm\sqrt{1-4x}}{2x} \ \ (2) f(x)=2x1±1−4x​​  (2)

　　对上式作泰勒展开（准确说是形式幂级数展开，反正就那个东西）：

　　回顾泰勒公式：

(1+x)a=1+ax+a(a−1)2!x2+...+a(a−1)(a−n+1)n!xn+... (1+x)^a = 1 + ax + \frac{a(a-1)}{2!}x^2 + ... + \frac{a(a-1)(a-n+1)}{n!}x^n + ... (1+x)a=1+ax+2!a(a−1)​x2+...+n!a(a−1)(a−n+1)​xn+...

　　令 x=−4xx = -4xx=−4x，a=1/2a = 1/2a=1/2 代入，得：

1−4x=1+12(−4)x+...+12(12−1)(12−n+1)n!(−4)nxn+... \sqrt{1-4x} = 1 + \frac12(-4)x + ... + \frac{\frac12(\frac12-1)(\frac12-n+1)}{n!}(-4)^n x^n + ... 1−4x​=1+21​(−4)x+...+n!21​(21​−1)(21​−n+1)​(−4)nxn+...

　　其通项可化为：

−12(1−12)...(n−1−12)n!4nxn=−1⋅3⋅5⋯[2(n−1)−1]2nn!4nxn=−(2n−3)!2⋅4⋯[2(n−2)]n!2nxn=−(2n−3)!2n−2(n−2)!n!2nxn\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}−n!21​(1−21​)...(n−1−21​)​4nxn​=−2nn!1⋅3⋅5⋯[2(n−1)−1]​4nxn=−2⋅4⋯[2(n−2)]n!(2n−3)!​2nxn=−2n−2(n−2)!n!(2n−3)!​2nxn​

　　由于 Cn>0C_n > 0Cn​>0，故可知 (2) 式中应取负号。上面的通项取负后，再除以 2x2x2x，得到 f(x)f(x)f(x) 的通项：

2(2n−3)!n!(n−2)!xn−1 \frac{2(2n-3)!}{n!(n-2)!}x^{n-1} n!(n−2)!2(2n−3)!​xn−1

Cn−1=2(2n−3)!n!(n−2)!=(2n−2)!n!(n−1)! C_{n-1} = \frac{2(2n-3)!}{n!(n-2)!} = \frac{(2n-2)!}{n!(n-1)!} Cn−1​=n!(n−2)!2(2n−3)!​=n!(n−1)!(2n−2)!​

Cn=(2n)!n!(n+1)!=1n+1(2nn) C_n = \frac{(2n)!}{n!(n+1)!} = \frac1{n+1}\binom{2n}{n} Cn​=n!(n+1)!(2n)!​=n+11​(n2n​)

　　这个数在组合数学中被称为卡塔兰数。

　　由此我们看到，从一个看似简单的逆波兰式计数问题，可以挖掘出这么多东西，其实写程序枚举所有合法的逆波兰式是可以的，相当于枚举所有满足要求的 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)。