Golang 实现卡特兰数

Golang 实现卡特兰数

卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。前20项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190。

原理

1. 令h(0)=1,h(1)=1，catalan数满足递推式:

   h(n)= h(0)h(n-1)+h(1)h(n-2) + ... + h(n-1)*h(0) (n>=2)

   例如：

   h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2

   h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5

2. 另类递推式:

   h(n)=h(n-1)*(4*n-2)/(n+1)

3. 递推关系的解为：

   h(n)=C(2n,n)/(n+1) (n=0,1,2,…)

4. 递推关系的另类解为：

   h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,…)

性质

卡塔兰数的一般项公式为：

一般项公式.png ​
Cn的另一个表达形式为：
另一个表达式.png
递推关系： 递推关系.png

它也满足

这提供了一个更快速的方法来计算卡塔兰数。

应用

实质上都是递推等式的应用

其实我们只需要记住它的一般项公式就好了，平时用到一般只需要用到它。

• 括号化

  矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)

• 出栈次序

  一个栈无穷大的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?(h(n)个)

  证明：

  令1表示进栈，0表示出栈，则可转化为求一个2n位、含n个1、n个0的二进制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含n个1、n个0的2n位二进制数共有

  二进制数.png

个，下面考虑不满足要求的数目。

考虑一个含n个1、n个0的2n位二进制数，扫描到第2m+1位上时有m+1个0和m个1（容易证明一定存在这样的情况），则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以后的部分0变成1、1变成0，则对应一个n+1个0和n-1个1的二进制数。反之亦然（相似的思路证明两者一一对应）。

从而 进栈.png

证毕。

• Cn表示有n个节点组成不同构二叉树的方案数。**

• Cn表示有2n+1个节点组成不同满二叉树（full binary tree）的方案数。**

• dyck word

  Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的前缀字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:

  ​ XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

• n对括号正确匹配数目

  将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数：

  ​ ((())) ()(()) ()()() (())() (()())

• 其他应用还用很多，可以去百度百科和维基百科上看，这里就不赘述了。

用 Golang 实现

import (
    "fmt"
    "math/big"
)
// 由于阶乘结果的数超出 int64 的范围，所以用到了 math/big 包来实现大数。


// 输出前20个卡特兰数
func main() {
    for i := int64(0); i < 20; i++ {
        fmt.Println(catalan(i))
    }
}
// 求卡特兰数
func catalan(n int64) *big.Int {
    one := big.NewInt(1) // 过渡值

    denominator := factorial(2 * n)
    divisor := one.Mul(factorial(n+1), factorial(n))
    return one.Div(denominator, divisor)
}
// 阶乘
func factorial(n int64) *big.Int {
    sum := big.NewInt(1)
    for i := int64(1); i <= n; i++ {
        sum.Mul(sum, big.NewInt(i))
    }
    return sum
}

参考

• 卡特兰数-百度百科
• 卡塔兰数-维基百科