卡特兰数

卡特兰数是一种经典的组合数，经常出现在各种计算中，其前几项为 :
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组括号的排列方式：1
  （）

• 2组括号的排列方式：2
  （）（）
  （（））

• 3组括号的排列方式：5
  （）（）（）
  （）（（））
  （（））（）
  （（（）））
  （（）（））

其数值依次为1、2、5...是卡特兰数序列

括号组合问题就是（、）的排序。显然，（、）的排序不像数字一样可以以任意方式进行组合，从而以全排列进行计数。
）的出现数必须少于（，显然，（的情况影响着）的出现情况，所以（、）的顺序是有映射关系的。
那么我们就可以通过卡特兰数来计算n个括号所构成的所有序列数。