Catalan 数

[[ slider_text ]]

[[ item.c ]]

发布时间 2025-03-15 作者：秋千月 来源：算法小站

dp计数 生成函数

## 生成函数初步
### 二项式处理方法
**取一半**
![](/media/content_img/OGF01.png)
![](/media/content_img/OGF02.png)

## 2n 中选 n，Catalan 数
### Catalan 数定义
**Catalan 数常用组合模型**
考虑$$n$$个$$+1$$和$$n$$个$$-1$$组成的序列
```math
a_1, a_2, \cdots, a_{2n}
```
其中前缀和总是满足$$a_1 + a_2 + \cdots + a_k \geqslant 0 \quad (k = 1, 2, \cdots, 2n)$$
这样的序列的方案数，等于第$$n$$个 Catalan 数
```math
\displaystyle
C(n) = \dfrac{1}{n+1} \binom{2n}{n}
```

> 证明如下

实际上是分成两类，每类$$n$$个元素，将$$2n$$个元素分成两类，每类$$n$$个元素的方案数$$\displaystyle \binom{2n}{n}$$

但其中一部分可行，一部分不可行，将可行的方案记为$$A_n$$，不可行的记为$$U_n$$
```math
\displaystyle
A_n + U_n = \binom{2n}{n}
```
先来计算$$U_n$$，什么方案不可行呢？当且仅当能找到第一个$$k$$，满足
```math
a_1 + a_2 +\cdots + a_k < 0 \\
a_1 + a_2 + \cdots + a_{k-1} = 0, \quad a_k = -1
```

除了$$a_k$$之外，剩下的元素是$$n-1$$个$$-1$$，$$n$$个$$+1$$
我们需要求**不可行的方案数**，和具体的元素值没有关系

**注意到**，每一个方案，每个元素，**不是 +1 就是 -1**，并且它们分别都有$$n$$个
说明一定可以找到一个位置$$k \in [1\cdots n]$$，使得
```math
a_1 + a_2 + \cdots + a_{k-1} = 0
```
并且$$k$$是奇数

> 用**打包分组法**

把$$a_k$$单独拎出来，剩下的$$n-1$$个$$-1$$打包，然后接着$$a_k \cup \\{其他 n 个 +1\\}$$打包
这样就构造出了不合法的方案
```math
U_n = \displaystyle \dfrac{(2n)!}{(n-1)!(n+1)!}
```

综上，这样的方案数定义为 Catalan 数
```math
\displaystyle
C(n) = \binom{2n}{n} - \binom{2n}{n-1} = \dfrac{1}{n+1} \binom{2n}{n}
```

### Catalan 数的简单应用

> 有$$2n$$个人进入剧场，入场费是$$50$$美分，有$$n$$个人有$$50$$美分的一枚硬币
另外$$n$$个人有$$1$$美元的纸币，问排队方案，使得每当有$$1$$美元的人买票时，总能够有$$50$$美分找零

首先不难发现，第一个买票的人肯定要是$$50$$美分，那么这样$$2n$$个人，$$n$$组，并且第一组要满足特定限制
这种问题可以用 Catalan 数来求解

**假设不需要区分这些人**
需要把 50 美分看成$$+1$$，1 美元看成$$-1$$，答案就是 Catalan 数$$\displaystyle \dfrac{1}{n+1} \binom{2n}{n}$$

如果需要区分呢？$$(n!)(n!) \cdot \displaystyle \dfrac{1}{n+1}\binom{2n}{n}$$

> 网格行走问题

![](/media/content_img/catalan01.png)

根据上面的分析，很显然有限制，第一步一定要往上走，那么这样的计数问题，考虑 Catalan 数
记往右走为$$-1$$，往上走为$$+1$$，每条路线对应序列$$a\_1,a\_2, \cdots, a\_{2n}$$

那么必须有$$\sum\_{i \in [1, k]} a_i \geqslant 0, \quad (k = 1, 2, \cdots, 2n)$$

> Catalan 数递推

```math
\displaystyle
\dfrac{C(n)}{C(n-1)} = \dfrac{4n-2}{n+1} \\
```
其中$$C_0 = 1$$

### 拟 Catalan 数
定义一个新数列
```math
G_n = n!C_{n-1} \quad (n = 1, 2, 3, \cdots)
```
我们有$$G_1 = 1$$
```math
G_n = n! C_{n-1} = n!\dfrac{4n - 6}{n} C_{n-2} = (4n - 6)(n-1)!C_{n-2} = (4n-6)G_{n-1}
```
拟 Catalan 数的递推由以下关系确定
```math
G_1 = 1 \\
G_n = (4n - 6)G_{n-1}
```
另外，根据 Catalan 数的定义，也可以直接求出
```math
\displaystyle
G_n = \dfrac{(2n-2)!}{(n-1)!}
```

### 拟 Catalan 数的一些应用
> 乘法方案

假设有$$a_1, a_2, \cdots, a_n$$，现在需要进行乘法，一个乘法方案需要进行$$n-1$$次乘法
记方案数为$$dp_n$$，那么很显然$$dp_2 = 2$$，因为有$$(a_1 \times a_2)$$和$$(a_2 \times a_1)$$

这样的方案数怎么求呢？
直接做的话，考虑先按照某种顺序排列$$a_1, a_2, \cdots, a_n$$，然后插入$$n-1$$对括号
使得每一对括号，都指定两个因子，我们以递归的方式来考察

1.取$$a\_1, a\_2, \cdots, a\_{n-1}$$的一种方案，有$$dp(n-1)$$种不同的选择
然后考虑将$$a\_n$$插入其中，注意到这里有$$n-2$$个$$\times$$号，形如$$a \times b$$
选一个括号插入，方案数是$$\displaystyle \binom{n-2}{1}$$，插入的位置呢？选$$a$$还是$$b$$？
又有两种选择，假设选择了$$a$$，那么放在$$a$$前面还是后面？又有两种
所以这种情况的方案数有$$2 \cdot 2 \cdot (n-2) = 4(n-2)$$种

2.直接乘上$$a_n$$，即$$a_n$$放开头或者结尾，有$$2$$种

综上所述，有递推$$dp(n) = (4n - 6) \cdot dp(n-1)$$，恰好是$$G_n$$

> 进一步地，如果$$(a_1 \times a_2 \times a_3)$$，只要是这 3 个数乘起来，不同的顺序算一种方案呢？

这样只需要除去$$n$$的全排列即可，这样的乘法方案数记为$$g_n$$

不难发现，$$g_n = \displaystyle \dfrac{dp_n}{n!} = \dfrac{G_n}{n!} = C(n-1)$$，恰好是$$n-1$$项 Catalan 数

> 考虑 Catalan 数的另一种递推

不难发现，在$$a_1, a_2, \cdots, a_n$$的乘法方案中，我们任选一种，有$$\displaystyle \binom{g_n}{1}$$种

现在这种方案一定有最后一次乘法，形如
```math
(a_1 \cdots a_k \text{的乘法方案}) \times (a_{k+1}\cdots a_n \text{的乘法方案})
```
不难发现，$$a\_1\cdots a\_k$$有$$g\_k$$种选择，而$$a\_{k+1}\cdots a\_{n}$$有$$g\_{n-k}$$种
```math
g_n = g_1g_{n-1} + g_2g_{n-2} + \cdots + g_{n-1}g_{1} \quad (n \geqslant 2) \\
g_1 = 1
```
根据之前的分析
```math
\displaystyle
C_{n-1} = C_0C_{n-2} + C_1C_{n-3} + \cdots + C_{n-2}C_0 \\
C_n = C_0C_{n-1} + C_1C_{n-2} + \cdots + C_{n-1}C_0 = \sum_{k = 0}^{n-1} C_kC_{n-1-k} \quad (n \geqslant 1)
```

> 三角划分

![](/media/content_img/catalan02.png)

不难发现递推式
```math
\displaystyle
h_n = \sum_{k = 1}^{n-1} h_k h_{n-k}
```
恰好是第$$n-1$$项 Catalan 数

**说明**
一般 Catalan 数的递推
```math
\displaystyle
C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k}
```
注意到$$k$$从$$0$$开始的，而上述$$h\_n$$对应的$$k$$却是从$$1$$开始，只要令$$k \leftarrow k - 1$$
之后就发现$$h\_n = C\_{n-1}$$

实际上，相当于$$h\_n$$每一项向左平移（idx 都`-1`），恰好为$$C\_{n-1}$$

## 生成函数求 Catalan 递推
![](/media/content_img/catalanOGF-01.png)
![](/media/content_img/catalanOGF-02.png)

## Catalan 数的扩展
### Dyck 路径
![](/media/content_img/catalan03.png)

### 买票问题
> 问题描述，令$$n \geqslant m$$，且$$m, n$$非负，有$$m+n$$个人要进入剧院，入场费是 50 美分
但是这些人中，有$$n$$个人有 50 美分的硬币，另外$$m$$个人只有 1 美元钞票，收银机一开始空的
证明，这些人的排列，满足每个人需要时候总有零钱找的方案数是

```math
\displaystyle
\dfrac{n-m+1}{n+1} \binom{m+n}{m}
```

**从 Dyck 路径的角度来考虑**

> 这里我们让向右走记为$$+1$$，向上走记为$$-1$$，要求路径前缀和$$\geqslant 0$$

![](/media/content_img/dyck01.png)
![](/media/content_img/dyck02.png)

综上所述，这样的方案数是
```math
\displaystyle
\binom{m+n}{m} - \binom{m+n}{m-1} = \dfrac{n-m+1}{n+1} \binom{m+n}{m}
```

## Educational Codeforces Round 170
### E
**[E. Card Game](https://codeforces.com/contest/2025/problem/E)**
给你$$n \times m$$的牌，每张牌用二元组`(花色， rank)`来表示，其中花色`[1...n]`，`rank = [1...m]`
注意这里`m`为偶数

一张牌`(a, b)`打败另一张`(c, d)`，即`(a, b) > (c, d)`，当且仅当以下 2 种情况
第一，$$a = 1, c \neq 1$$
第二，$$a = c, b > d$$

第一位玩家获胜，当且仅当对于第二位玩家的**所有牌**，第一位玩家手中都有一张能够打败它的牌
（每张牌只能用一次）
反过来就是第二位玩家获胜

现在问，要使得第一位玩家获胜，有多少种不同的方案？一张牌如果被分到不同的玩家手上，视为不同方案

**算法分析**
![](/media/content_img/edu170-e1.png)
![](/media/content_img/edu170-e2.png)

上一篇：2025年2月写的一些codeforces题（二）下一篇：2025年三月算法竞赛选题（一）

看完文章有啥想法