曾彪彪的个人博客 -- 卡特兰数(catalan number)

## 概述

卡特兰数(catalan number)是组合数学中常见的数列，它出现在很多计数问题中，比如合法括号匹配，二叉树可能性统计，路劲问题，以及出栈可能性等问题中。

## 公式
卡特兰数常见的表示方式有两种：递推公式和组合公式

### 递推公式：
$$C_{n+1}= \sum_{i=0}^n C_i \cdot C_{n-i}$$
$$C_0=1$$

我们来理解这个递推公式是怎么来的，以合法的括号数为例。
对于n对括号，我们这里以n=3为例，合法的括号是：
(()())
((()))
(())()
()(())
()()()
一共5中。
我们以$S=(())()$为例，那么$S$可以表示成$S=(S_a)S_b$，其中$S_a=(),S_b=()$。
那么再来看$S=(()())=(S_a)S_b$，其中$S_a=()()，S_b=$空。
所以可以得出，任意括号对，可以表示成$S=(S_a)S_b$。
对于任意$S_a$，都可以表示成$S_a=(S_{aa})S_{ab}$，这样形成递归。对于$S(n=3)$举例如下：
$$
S_3=(S_0)S_2\\
S_3=(S_1)S_1\\
S_3=(S_2)S_0\\
$$
对于$S_2$，有
$$
S_2=(S_0)S_1\\
S_2=(S_1)S_0
$$

其中$S_0=$空，$S_1=()$
那么
$$
S_2=(S_0)S_1=()()\\
S_2=(S_1)S_0=(())\\
$$

把$S_0,S_1,S_2$代入$S_3$中，有
$$
\begin{align}
S_3&=(S_0)S_2=(S_0)(S_0)S_1&=()()()\\
S_3&=(S_0)S_2=(S_0)(S_1)S_0&=()(())\\
S_3&=(S_1)S_1&=(())()\\
S_3&=(S_2)S_0=(S_2)=((S_0)S_1)&=(()())\\
S_3&=(S_2)S_0=(S_2)=((S_1)S_0)&=((()))\\
\end{align}
$$

可以看出，对于$S_3$，有：
$$
C_3=\sum_{0}^2 C_i \cdot C_{2-i}
$$
其中$C_3$表示$S_3$中所有合法组合的总数。
那么，那么对于任意的n，我们有：
$$
C_n+1=\sum_{0}^n C_i \cdot S_{C-i}
$$
至此，卡特兰数的递推式就已经得到了。

### 组合公式

接下来我们看卡特兰数的组合公式。
$$
C_n=\binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1} \cdot \binom{2n}{n}
$$
这个公式怎么得到的呢，我们以Dyck路径为例。
Dyck路径是这样定义的：
在一个坐标轴上，如果要走2n步，每次只能向上或者向下走一步，并且向上走的步数=向下走的步数，并且不允许走到x轴下方。
这里我们展开合法的括号数，假设左括号表示向上走，右括号向下走。如果对于任何的前缀，左括号的数量>=右括号的数量，那么这个括号对就是合法的。
同理对应数字$\{1，2，3，...n\}$按顺序入栈，那么合理的出栈顺序中，任何时刻，出栈的次数不能大于入栈的次数。这些都符合卡特兰数。
我们以Dyck路径为例，要求出合法的步数组合，我们这样理解：
总共走2n步，向上走n步，向下走n步，那么所有可能性是$\binom{2n}{n}$。
$$合法路径方案数+非法路径方案数=\binom{2n}{n}$$。
合法路径方案数无法直接求得，那么
$$
合法路径方案数=\binom{2n}{n}-非法路径方案数
$$
这里的关键是求得 $非法路径方案数$。

先来理解什么是非法路径数，我们执行n步向上走，再执行n步向下走，只要走到x轴以下，就是一条非法路径。我们n=6为例：
第一步，向下走，走到(1,-1)，已经走到x轴下方了，这就是非法路径。
如果前三步是：上下下，那么第三步就走到了(3,-1)，也是非法路径。
虽然最终会走到(6,0)坐标，但是只要中间走到过x轴下方，都是非法路径。

对于非法路径，我们假设第k步走到x轴下方，那么从k+1步开始，所有的操作都翻转，原来向上走的，改成向下走，原来向下走的，改成向上走。那么等我们走完2n步，一定向下走了n+1步，向上走了n-1步，并且一定走到(2n,-2)。这里翻转k步之后所有的步骤，和不翻转，它们在概率上是一样的，也就是说，在数它们的时候等价。只是翻转之后，走到了(2n,-2)，不翻转，走到了(2n,0)。而如果走到(2n,-2)，我们就可以算出这种走法的概率，因为它一定向上走了n-1步，向下走了n+1步。所以我们只要统计，最终能走到(2n,-2)的路径，就是非法路径。这个方法，叫做反射法。
反射法之所以成立，是因为
- 当走到x下方之后，对之后的所有步数翻转，以及不翻转，数它们等价。
- 另外也可以通过走到(2n,-2)中的任何路径，可以完全还原走到(2n,0)的路径，而这一条路径，就是非法路径。

如果需要走到(2n,-2)坐标，那么一定向下走n+1步，向上走n-1步，其方案数是$\binom{2n}{n+1}$。
所以
$$
合法的方案数 = C_n = \binom{2n}{n}-\binom{2n}{n+1}=\frac{1}{n+1} \cdot \binom{2n}{n}。
$$
这里合法的方案数，就是卡特兰数。

## 应用场景

卡特兰数是一类递归结构计数的典型答案，如果满足以下条件，考虑使用卡特兰数来解决问题：
- 有左右对称或分割成两部分的结构
- 有不能越界的约束
- 常常和括号，路径，树，出栈顺序等相关。

常见的应用场景包括：
- 合法的括号匹配数量，这个在递推公式中阐述过。
- Dyck路径，在组合公式中阐述过。
- 出栈的可能情况，在组合公式中阐述过。
- n个节点组成的二叉树的可能性
  - 通过递推公式来理解，
    - 可以认为树的左子树有i个节点，那么其右子树必右n-1-i个节点
    - i的取值范围是[0,n-1]
    - 所有可能相加，即为卡特兰数的组合公式
  - 通过组合公式来理解
    - 每个节点是一对括号，左子树节点对应的括号写在根节点对应的括号内，右子树节点对应的括号写在根节点对应的括号后。与我们组合公式推导中，括号数量情况对应。
    - 根据上面规则，以3个节点的二叉树为例，对应各个二叉树的括号情况如下：
      - 根左左 高度为3  ((()))
      - 根左右 高度为3  (()())
      - 根左右 高度为2  (())()
      - 根右右 高度为3  ()()()
      - 根右左 高度为3  ()(())

卡特兰数(catalan number)

评论(0)