长沙7喜 / 信息课 / 计算机界的精灵:Catalan 数

分享

   

计算机界的精灵:Catalan 数

2022-01-09  长沙7喜

Catalan 数

卡特兰数(Catalan Number)被称为计算机界的精灵。

Catalan 数是一个自然数序列,1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,...... 。它出现在许多有趣的计数问题中:

1、计算包含 n 对括号且正确匹配的表达式的数量。对于 n=3,可能的表达式包含 ((())), ()(()), ()()(), (())(), (()()) 5 种情况。

2、一个栈(无穷大)的进栈序列为 1,2,3,...,n,有多少个不同的出栈序列呢?

图片

简单一点,如上图所示,已知一个进栈序列 1,2,3,4,可能的出栈序列有 {{1,2,3,4},{2,1,3,4},{2,1,4,3},{3,2,1,4},{4,3,2,1}} 5 种情况。如果随着进栈序列 n 的不断增加,可能的出栈序列是🤔?

3、通过连接顶点可以将 n+2 条边的凸多边形拆分为三角形的方式数。如下图所示,n=4 时,可能的方式有 14 种。

图片

4、具有 n+1 个叶子的满二叉树的数量。当 n=3 时,包含 4 个叶子的满二叉树的数量为 5:

图片

5、对于 的矩形网格上从左下角 (n-1,0) 到右上角 (0,n-1) ,且不在主对角线上方相交的,具有 2n 个台阶的路径数。如下图所示,对于 n = 4 的网格,从左下角到右上角且不穿过对角线的路径数为 15 。

图片

6、包含 n 个数的点阵集合 {1,2,3,...,n} 的非交叉划分的数目。比如集合 {{1,4},{2,3}} 就是非交叉划分,但是 {{1,3},{2,4}} 就是交叉划分。下图为 n=4 时共包含的 14 种非交叉点阵集合。

图片

7、使用 n 个矩形平铺高度为 n 的楼梯形状的方法数。下图说明了n=4的情况:

图片

8、使用 n 条上笔划 “/” 和 n 条下笔划 “\' 可以构成 “山脉” 的方式数。注意山脉永远不会低于地平线奥。如下图所示:

图片

以上提及的 8 个问题都可以用 Catalan 数来计数。到 2010 年 8 月 21日,R. Stanley 找到了190 种[1]不同问题结构都可以用 Catalan 数来计数。将其称为计算机界的精灵也不言过其实。

Catalan 数的递归定义

至于这个公式的证明,感兴趣的小伙伴可以参考清华大学组合数学[2]课程。我们仅关注于让计算机帮我们计算 Catalan 数。

递归法

已知上面的递归定义,“照猫画虎” ,我们不难写出如下计算 Catalan 数的递归写法:

class CatalnNumber {
    // 计算第 n 个 Catalan 数的递归实现
    int catalan(int n)
    
{
        int res = 0;
        // 递归出口
        if (n <= 1) {
            return 1;
        }
        // 递归方程
        for (int i = 0; i < n; i++) {
            res += catalan(i) * catalan(n - i - 1);
        }
        return res;
    }
    
    public static void main(String[] args)
    
{
        CatalnNumber cn = new CatalnNumber();
        for (int i = 0; i < 10; i++) {
            System.out.print(cn.catalan(i) + ' ');
        }
    }
}

该实现的时间复杂度与 Catalan 数的递归定义一个量级:

同为指数级别。

动态规划

上面的递归实现存在大量的重复计算(我们可以尝试绘制递归树)。

图片

因为存在重叠子问题,我们可以考虑用动态规划解决:

public class CatalanNumDP {
    public static int catalanDP(int n)
    
{
        // DP table 存储重叠子问题
        int[] catalan = new int[n + 2];

        // 初始化 DP table 的前两个值
        catalan[0] = 1;
        catalan[1] = 1;

        // 自底向上计算第 n 个 Catalan 数
        for (int i = 2; i <= n; i++) {
            catalan[i] = 0;
            for (int j = 0; j < i; ++j) {
                catalan[i] += catalan[j] * catalan[i - j - 1];
            }
        }
        
        return catalan[n];
    }

    public static void main(String[] args)
    
{
        for (int i = 0; i < 10; i++) {
            System.out.print(catalanDP(i) + ' ');
        }
    }
}

以上自底向上的动态规划的实现方法的时间复杂度为 ,相比递归的指数级别,已经提升了一个很大的量级,为了理解方便,我们一起计算一下 catalan(5) :

图片

二项式系数

我们也可以使用下面的公式计算第 n 个 Catalan 数:

有了这个公式,计算 Catalan 数的难点就转化为了计算 二项式系数了。

public class CatalanNumBC {
    // 返回 C(n, k) 的结果
    static long binomialCoefficient(int n, int k) {
        long res = 1;

        if ( k > n - k) {
            k = n - k;
        }
        // 计算 n*(n-1)*(n-2)....*(n-k+1) 除以 k*(k-1)*...*1
        for (int i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }

        return res;
    }

    static long catalan(int n) {
        long res = binomialCoefficient(2*n, n);
        return res / (n+1);
    }

    public static void main(String[] args)
    
{
        for (int i = 0; i < 10; i++) {
            System.out.print(catalan(i) + ' ');
        }
    }
}

该实现的时间复杂度为

除此以外,我们还已知  和 之间的关系:

因此我们也可以自底向上计算得到第 n 个 Catalan 数。

比如

public class CatalanNum {

    static int catalan(int n)
    
{
        int res = 1;

        // 迭代计算第 n 个卡特兰数
        for (int i = 1; i <= n; i++)
        {
            res *= (4 * i - 2);
            res /= (i + 1);
        }
        return res;
    }

    public static void main(String args[])
    
{
        System.out.println(catalan(5));
    }
}

时间复杂度为 ,空间复杂度为

使用 BigInteger

查找第 n 个 Catalan 数,如果 的时候,使用 long 类型将无法存储第 n 个 Catalan 数,此时可以考虑 Java 提供的 BigInteger.

下面的实现我们使用二项式系数的计算方法。

package com.google;

import java.math.*;
public class BigCatalan {
        public static BigInteger findCatalan(int n)
        
{
            // 初始化
            BigInteger b = new BigInteger('1');

            // 计算 n!
            for (int i = 1; i <= n; i++) {
                b = b.multiply(BigInteger.valueOf(i));
            }

            // 计算 n! * n!
            b = b.multiply(b);

            BigInteger d = new BigInteger('1');

            // 计算 (2n)!
            for (int i = 1; i <= 2 * n; i++) {
                d = d.multiply(BigInteger.valueOf(i));
            }

            //计算 (2n)! / (n! * n!)
            BigInteger ans = d.divide(b);

            // 计算 (2n)! / ((n! * n!) * (n+1))
            ans = ans.divide(BigInteger.valueOf(n + 1));
            return ans;
        }
        
        public static void main(String[] args)
        
{
            System.out.println(findCatalan(48));
        }
}

关于 Catalan 数的更多应用及文中所提及的公式推导大家可以参考

维基百科:Catalan 数[3]

参考资料

[1]

Catalan 数的190种应用: http://www-math.mit.edu/~rstan/ec/catalan.pdf

[2]

清华大学组合数学: https://www.xuetangx.com/course/THU08091000450/7753948?channel=i.area.recent_search

[3]

Catalan Number: https://en.jinzhao.wiki/wiki/Catalan_number#Applications_in_combinatorics

作者:景禹,一个求极致的共享主义者,想带你一起拥有更美好的生活,化作你的一把伞。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多