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./~rstan/ec/catalan.pdf
[2]清华大学组合数学: https://www./course/THU08091000450/7753948?channel=i.area.recent_search
[3]Catalan Number: https://en./wiki/Catalan_number#Applications_in_combinatorics
