ACM模板——卡特兰数（Catalan）算法

一、什么是Catalan数（Catalan数是许多计数问题的最终形式）

Catalan序列是一个整数序列，其通项公式是：

递推公式 1：

C(n) = C(1)*C(n-1) + C(2)*C(n-2) + ... + C(n-1)C(1)，n>=2

递推公式 2：

令 h(0)=1,h(1)=1，Catalan数满足递推式：

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

举例，我们从中取出的 Cn 就叫做第 n 个 Catalan数，前几个 Catalan数 如下：

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, …

二、Catalan数 在组合计算中的应用

0、n对括号正确匹配数目？

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

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

3、n个节点构成的二叉树，共有多少种情形？

4、求一个凸多边形区域划分成三角形区域的方法数？

5、在圆上选择2n个点，将这些点成对链接起来使得所得到的n条线段不相交，一共有多少种方法？

6、n*n的方格地图中，从一个角到另外一个角，不跨越对角线的路径数为h(n)。例如：4×4方格地图中的路径有：

7、n层的阶梯切割为n个矩形的切法数也是Cn。如下图所示：

8、有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零？

9、甲乙两人比赛乒乓球，最后结果为20∶20，问比赛过程中甲始终领先乙的计分情形的种数。

10、2n个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？

三、AC 代码

import java.math.BigInteger;
import java.util.Scanner;
public class Main{
  public static void main(String[] args) {
    BigInteger h[]=new BigInteger[205];
    h[0]=h[1]=BigInteger.ONE;
    for(int i=2;i<205;i++)
      h[i]=(h[i-1].multiply(BigInteger.valueOf(4).multiply(BigInteger.valueOf(i)).subtract(BigInteger.valueOf(2)))).divide(BigInteger.valueOf(i+1));
//    for(int i=1;i<=15;i++) // 打印输出
//      System.out.println(h[i]);
    Scanner in=new Scanner(System.in);
    while (in.hasNext()) {
      int n=in.nextInt();
      if(n==-1) break;
      System.out.println(h[n]);
    }
  }
}