逆波兰式与卡塔兰数

最后更新日期: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 排成序列 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 = 1C_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 = -4xa = 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)。