使用卡特兰数来解决的问题
作者：Grey
原文地址：
通项公式
k(0) = 1, k(1) = 1，如果接下来的项满足：
k(n) = k(0) x k(n - 1) + k(1) x k(n - 2) + …… + k(n - 2) x k(1) + k(n - 1) x k(0) 或者
k(n) = C(2n, n) - C(2n, n-1) 或者
k(n) = C(2n, n) / (n + 1) 就说这个表达式，满足卡特兰数。
比如
n 个左括号，n 个右括号，有多少种合法的组合方式？合法的定义是任何一个前缀串，右括号的数量必须小于左括号的数量。
合法的不好求，我们可以先求不合法的，因为总的方法数是C(2n,n)（先安排 n 个左括号，另外的位置自然成为右括号的位置）
不合法的情况是：一定存在一个前缀，右括号的数量 = 左括号的数量 + 1，即不合法的数量等于C(2n, n+1),
所以合法的数量等于C(2n,n) - C(2n,n+1)，即C(2n,n) - C(2n,n-1)。
满足卡特兰数。
再如
给定 n 个数字，且每个数字都必须入栈，也必须出栈，求这些数合法的出栈入栈的顺序有多少种？
由于每个数字有出栈和入栈两个操作，所以，一共的操作组合有（包括不合法的方式）C(2n,n),
由于出栈的次数一定不可能大于入栈的次数，所以，不合法的组合方式中：一定存在一个出入栈的方式，出栈的次数 = 入栈次数 + 1，即C(2n, n + 1)，合法的出入栈次数是C(2n,n) - C(2n, n + 1)，即C(2n, n) - C(2n, n - 1)，满足卡特兰数。
类似的还有
曲线在第一象限，可上升，可下降，求有多少种组合方式？
也满足卡特兰数。
N个节点有多少种形态的二叉树
有N个二叉树节点，每个节点彼此之间无任何差别，返回由N个二叉树节点，组成的不同结构数量是多少？
题目链接：
LintCode 163 · Unique Binary Search Trees
LeetCode 96. Unique Binary Search Trees
主要思路
有 0 个节点的时候，只有 1 种方法，即空树
有 1 个节点的时候，只有 1 种方法，即只有一个节点的树
有 2 个节点的时候，有 2 种方法，分别是
即: k(0) = 1, k(1) = 1, k(2) = 2
当数量为 n 时，有如下一些情况，根节点占一个节点，然后
左树 0 个节点 ，右数 n - 1 个节点；
左树 1 个节点，右数 n - 2 个节点；
左树 2 个节点，右数 n - 3 个节点；
……
左树 n - 1 个节点 ，右数 0 个节点；
左树 n - 2 个节点，右数 1 个节点；
左树 n - 3 个节点，右数 2 个节点；
即：k(n) = k(0) x k(n - 1) + k(1) x k(n - 2) + …… + k(n - 2) x k(1) + k(n - 1) x k(0)，满足卡特兰数。
完整代码如下
import java.math.BigInteger; public class Solution { /** * @param n: An integer * @return: An integer */ public static int numTrees(int n) { if (n < 0) { return BigInteger.ZERO.intValue(); } if (n < 2) { return BigInteger.ONE.intValue(); } BigInteger a = BigInteger.ONE; BigInteger b = BigInteger.ONE; for (int i = 1, j = n + 1; i <= n; i++, j++) { a = a.multiply(BigInteger.valueOf(i)); b = b.multiply(BigInteger.valueOf(j)); BigInteger gcd = gcd(a, b); a = a.divide(gcd); b = b.divide(gcd); } return (b.divide(a)).divide(BigInteger.valueOf(n + 1)).intValue(); } public static BigInteger gcd(BigInteger m, BigInteger n) { return n.equals(BigInteger.ZERO) ? m : gcd(n, m.mod(n)); } private static int numTrees2(int n) { if (n < 0) { return BigInteger.ZERO.intValue(); } if (n < 2) { return BigInteger.ONE.intValue(); } BigInteger a = BigInteger.valueOf(n + 1); BigInteger b = BigInteger.valueOf(1); for (int i = n + 2; i <= (2 * n); i++) { a = a.multiply(BigInteger.valueOf(i)); } for (int i = 1; i <= n; i++) { b = b.multiply(BigInteger.valueOf(i)); } return a.divide(b).divide(BigInteger.valueOf(n + 1)).intValue(); } } 1 0 前缀串数量问题
假设给你 n 个 0 和 n 个 1，你必须用全部数字拼序列,返回有多少个序列满足：任何前缀串，1 的数量都不少于 0 的数量
n 个 1 和 n 个 0，所有的排列组合是C(2n,n)，由于合法数量 = 所有组合 - 非法数量，即
C(2n,n) - C(2n,n-1) 完整代码如下
package snippet; import java.util.*; //假设给你N个0，和N个1，你必须用全部数字拼序列 // 返回有多少个序列满足：任何前缀串，1的数量都不少于0的数量 // 卡特兰数 public class Code_10Ways { public static long ways2(int N) { if (N < 0) { return 0; } if (N < 2) { return 1; } long a = 1; long b = 1; long limit = N << 1; for (long i = 1; i <= limit; i++) { if (i <= N) { a *= i; } else { b *= i; } } return (b / a) / (N + 1); } } 类似的问题
偶数（2N）个人排队，排两行，任何一个排在后面的人都不能比排在前面的人小，有几种排列方式？
其本质就是：前面N个人编号成0，后面N个人编号成1，任何前缀串，1的数量不小于0的数量
