1、简介

1.1 何为卡特兰数

卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学 中一个常在各种计数问题中出现的数列。

前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

1.2 卡特兰数的通项公式

$k(0)=1,k(1)=1$ 时，如果接下来的项满足：

$k(n)=k(0)\ast k(n-1)+k(1)\ast k(n-2)+...+k(n-2)\ast k(1)+k(n-1)\ast k(0)$

或者

$k(n)=C_{2n}^n-C_{2n}^{n-1}$

或者

$k(n)=C_{2n}^n/(n+1)$

就说这个表达式，满足卡特兰数，常用的是范式1和2，3几乎不会使用到

2、应用

2.1 题目1：括号合法

题目描述

给定 $N$ 个左括号，$N$ 个右括号，它们自由组合，必须全部使用，能得到多少个合法的组合？

思路分析

“合法”的定义是对于自由排列的组合，只要保证任意的前缀，右括号数量 $\le$ 左括号数量，那么它最终一定是合法的。原理就是左括号比右括号多的时候，一旦出现右括号就能将多的左括号配对，最终一定会全部配对成功。反之则不行。

先讨论一个数学思想：如何确定两个集合相等

【集合A 和 集合B 可以是完全不相干的两个可数集合，只要能找到一个映射$f$，使得A集合中的一个对应B集合中的一个，又能找到一个和 $f$ 毫不相干的映射 $g$ 使得 B集合中的一个对应 A集合中的一个，如果存在这样一组映射，那么A集合数量和B集合数量一定相等。】

借此，来讨论括号组合的合法问题。合法的组合数量不好算，那就可以先选出不合法的组合数量，然后使用总的排列方法 减去 不合法的，就是合法的。

总的排列方法数为 $C_{2n}^n$，意思是一共 $2n$ 个位置，选择其中的 $n$ 个放左括号，剩下的 $n$ 个位置放右括号。

而不合法的特征一定存在一个最初的前缀：右括号数量 = 左括号数量 + 1，如 ())(()，最初前缀就是 ())。那么在该前缀后的就是 右括号数量 + 1 = 左括号数量 （因为左右括号的数量相等）。以这个最初前缀为分界线，后面的所有括号进行反转，即右括号变成左括号，左括号变成右括号，就变成了())))(，那么分界线后的左括号数量 + 1 = 右括号数量。如此一来，整体的 右括号数量 = 左括号数量 + 2。

定义两个集合，A集合放所有不合法的情况，B集合是 $n+1$ 个右括号，$n-1$个左括号 组合得到的所有情况 （该集合的来源不深究），也就是说通过上面的括号反转，A集合中任意一个不合法的元素通过该映射都能变出一个B集合的某一个元素；而B集合中的每个元素都能变成A集合其中的一个，如))))((，最初的不合法前缀为)，以该前缀为分界线后面的所有括号反转。最终得到)((())。

所以 “$n$ 个左括号 和 $n$ 个右括号组合不合法的数量” = “$n+1$个右括号 和 $n-1$个左括号组合的所有数量”，即 $C_{2n}^{n+1}$。

所以，$n$ 个左括号和 $n$ 个右括号组合的合法数量 = $C_{2n}^n-C_{2n}^{n+1}$，而 $C_{2n}^{n+1}=C_{2n}^{n-1}$，因此合法的组合数量也可以是 $C_{2n}^n-C_{2n}^{n-1}$。

也就是说，括号类型的违规可以转换为卡特兰数进行计算，因为$C_{2n}^n-C_{2n}^{n-1}$ 是卡特兰数的通项公式之一。

2.2 题目2：进出栈的方式

2.2.1 题目描述

$n$ 个数字要进出栈，一共有多少种进出栈的方式？

2.2.2 思路分析

例如，给定数字[1, 2]，进出栈的方式：

合法的情况：

1. 1进(↓），1出(↑)，2进(↓)，2出(↑)
2. 1进(↓)，2进(↓)，2出(↑)，1出(↑)
只用记录箭头

不合法的情况：

1. ↑ ↑ ↓ ↓ （没有数字进栈是无法出栈的）

考察箭头组合的合法数量，这其实就是括号问题。进栈是左括号，出栈是右括号。合法的条件就是在任何时候，右括号数量不能大于左括号数量，也就是任意时刻出栈次数 $\le$ 进栈次数就是合法的进出栈方式，就是卡特兰数。

再举个例子：某个公司的股票有上涨和下跌，问有多少种交易方式可以使得股票不会跌到X轴以下？

这也是一个卡特兰数问题，往上就是左括号，往下就是右括号，就是在问左右括号合理的结合方式。

2.3 题目3：合法的序列

2.3.1 题目描述

假设给你 $N$ 个 0，和 $N$ 个 1，你必须用全部数字拼序列。

返回有多少个序列满足：任何前缀串，1的数量都不少于0的数量

2.3.2 思路分析

这个就是 “括号合法” 模型问题，1是左括号，0是右括号，任意时刻满足左括号数量 $\ge$ 右括号数量。

直接使用卡特兰数的通项公式解决即可。

2.3.3 代码实现

import java.util.LinkedList;public class 10Ways {//方法1：暴力递归public static long ways1(int N) {int zero = N;int one = N;LinkedList<Integer> path = new LinkedList<>();LinkedList<LinkedList<Integer>> ans = new LinkedList<>();process(zero, one, path, ans);long count = 0;for (LinkedList<Integer> cur : ans) {int status = 0;for (Integer num : cur) {if (num == 0) {status++;} else {status--;}if (status < 0) {break;}}if (status == 0) {count++;}}return count;}public static void process(int zero, int one, LinkedList<Integer> path, LinkedList<LinkedList<Integer>> ans) {if (zero == 0 && one == 0) {LinkedList<Integer> cur = new LinkedList<>();for (Integer num : path) {cur.add(num);}ans.add(cur);} else {if (zero == 0) {path.addLast(1);process(zero, one - 1, path, ans);path.removeLast();} else if (one == 0) {path.addLast(0);process(zero - 1, one, path, ans);path.removeLast();} else {path.addLast(1);process(zero, one - 1, path, ans);path.removeLast();path.addLast(0);process(zero - 1, one, path, ans);path.removeLast();}}}//方法2：卡特兰数的通项公式解决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);}public static void main(String[] args) {System.out.println("test begin");for (int i = 0; i < 10; i++) {long ans1 = ways1(i);long ans2 = ways2(i);if (ans1 != ans2) {System.out.println("Oops!");}}System.out.println("test finish");}
}

2.4 题目4：不同二叉树的数量

2.4.1 题目描述

有 $N$ 个二叉树节点，每个节点彼此之间无任何差别。返回由 $N$ 个二叉树节点，组成的不同结构数量是多少？

2.4.2 思路分析

如果 0 个节点，只能组成空树，1种；
如果 1 个节点，只能组成1个节点的树，1种；
如果 2 个节点，只有2种结构。

n 个节点组成二叉树的情况：

1）第 1 种划分：头结点1个，左子树0个，右子树 $n-1$ 个

在这种划分下，不同结构的数量为：[0个节点组成的方法数] $\times$ [$n-1$个节点组成的方法数]

2）第 2 种划分：头结点左边1个节点，右边 $n-2$ 个节点

在这种划分下，不同结构的数量为：[1个节点组成的方法数] $\times$ [$n-2$个节点组成的方法数]

这个规律就是卡特兰数的第1个通项公式，所以这就是卡特兰数。 那么直接用卡特兰数的第2个通项公式计算即可，因为卡特兰数的三个通项公式是等效的。

2.4.3 代码实现

public class DifferentBTNum {//	k(0) = 1, k(1) = 1
//
//	k(n) = k(0) * k(n - 1) + k(1) * k(n - 2) + ... + k(n - 2) * k(1) + k(n - 1) * k(0)
//	或者
//	k(n) = c(2n, n) / (n + 1)
//	或者
//	k(n) = c(2n, n) - c(2n, n-1)//方法1public static long num1(int N) {if (N < 0) {return 0;}if (N < 2) {return 1;}long[] dp = new long[N + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= N; i++) {for (int leftSize = 0; leftSize < i; leftSize++) {dp[i] += dp[leftSize] * dp[i - 1 - leftSize];}}return dp[N];}//方法2：卡特兰数public static long num2(int N) {if (N < 0) {return 0;}if (N < 2) {return 1;}long a = 1;long b = 1;for (int i = 1, j = N + 1; i <= N; i++, j++) {a *= i;b *= j;long gcd = gcd(a, b);a /= gcd;b /= gcd;}return (b / a) / (N + 1);}public static long gcd(long m, long n) {return n == 0 ? m : gcd(n, m % n);}public static void main(String[] args) {System.out.println("test begin");for (int i = 0; i < 15; i++) {long ans1 = num1(i);long ans2 = num2(i);if (ans1 != ans2) {System.out.println("Oops!");}}System.out.println("test finish");}
}

3、总结

1. 要对卡特兰数的通项公式1和公式2烂熟于心；
2. 对“括号合法”模型（左右括号数量相等的合法性问题）要有敏感度；
3. 加强对卡特兰数通项公式1的敏感度的训练，如题目4，符合公式1等同于公式2，而通常可能是写出了暴力递归才会发现公式1，就要求对暴力解法有了解。

补充：

数学结论：所有整数和所有偶数数量相等。因为任何整数乘以2后等于某个偶数，而任意偶数除以2后等于某个整数，二者建立了一一映射关系，所以整数数量和偶数数量就是一样多的。在数学上，它叫作“等势”。

5米的线和10米的线上的点数量一样多。在两条线之外找某一个定点，5米线上找任意一个点和定点连线能对应到10米中的一个点，10米的任意一个点和定点连线能对应到5米中的一个点，所以5米的线和10米的线点一样多。

点是无长度的，无长度的东西有可能有无限个点。更多可以查看希尔伯特旅馆悖论。

总而言之，牵扯到一个非常重要的思想，两个可数集合A和B，能互相建立一种映射关系，那它们的数量就是一样多的。