Golang 实现卡特兰数
卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。前20项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190。
原理
-
令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=2h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5 -
另类递推式:
h(n)=h(n-1)*(4*n-2)/(n+1) -
递推关系的解为：
h(n)=C(2n,n)/(n+1) (n=0,1,2,…) -
递推关系的另类解为：
h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,…)
性质
卡塔兰数的一般项公式为：
Cn的另一个表达形式为：
递推关系：
它也满足
这提供了一个更快速的方法来计算卡塔兰数。
应用
实质上都是递推等式的应用
其实我们只需要记住它的一般项公式就好了，平时用到一般只需要用到它。
-
括号化
矩阵连乘： 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的二进制数。反之亦然（相似的思路证明两者一一对应）。
从而
证毕。
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
}
