【组合数学】卡特兰数与折线法

· · 个人记录

本篇博文将对卡特兰数与折线法进行讲解。

Part 1. 卡特兰数

卡特兰数是一个用于解决一些对称问题的一种数，通项公式为 H(n)=\sum\limits_{i=1}^n H(i-1)\times H(n-i) 或者 H(n)=\begin{pmatrix}2n\\n\end{pmatrix}-\begin{pmatrix}2n\\n-1\end{pmatrix}。

下面我们来看一组题目：

一共要走 n+m 次，其中有 m 次向右操作，所以不同方案数为 \begin{pmatrix}n+m\\m\end{pmatrix}，即在这 n+m 次操作中任选 m 次向右。

我们将这些不合法序列画在纸上，发现是类似于下图的形式：

我们将其与这条直线的第一个交点以后的部分沿这条直线进行翻折，可以得到如下图：

我们发现这样终点变为了 (n-1,n+1)，而每条不合法的路径翻折后都会走到点 (n-1,n+1)，形成了一一对应的关系，所以不合法的方案数就是从 (0,0) 走到 (n-1,n+1) 的方案数，即 \begin{pmatrix}2n\\n+1\end{pmatrix}

所以答案为 \begin{pmatrix}2n\\n\end{pmatrix}-\begin{pmatrix}2n\\n-1\end{pmatrix}，正好等于上面的卡特兰数通项公式 2。

那么卡特兰数还可以干什么呢？只要是有两种操作且需要两种操作次数相同，任何时候操作 1 的次数不能大于操作 2 的次数，那么就可以使用卡特兰数求解。

Part 2. 折线法

Part 2.1 一条线的限制

那么以上的问题也属于折线法中一条线的限制类问题。当 n\neq m 时，是否还有如上的答案呢？

答案是肯定的，只是对称点发生了变化。当终点为 (n,m)，它关于直线 y=x+1 的对称点即为 (m-1,n+1)，答案即为 \begin{pmatrix}n+m\\n\end{pmatrix}-\begin{pmatrix}n+m\\n+1\end{pmatrix}。

那么来看这道题 P1641。

不难发现 0 操作等同于向上，1 操作等同于向右，那么就是求 (0,0) 走到 (m,n) 且不经过直线 y=x+1 的总方案数。

发现这就是把 m,n 反过来而已，所以答案是 \begin{pmatrix}n+m\\n\end{pmatrix}-\begin{pmatrix}n+m\\n-1\end{pmatrix}。

Part 2.2 两条线的限制

设有两条直线 A,B，那么每当路径碰到其中一直线我们就把这个直线的名称写下来，如此便得到了一个 AB 串。

那么答案就是所有路径数分别减去以 A,B 开头的串方案数总数。

考虑容斥，对于以 A 开头的串，我们将答案减去 A 串的方案数，加上 AB 串的方案数，再减去 ABA 串的方案数。如此循环往复直到无法再翻折，对于 B 开头同理。

那么现在问题是，对于直线 y=x+k，点 A(n,m) 沿该直线翻折后落在哪个点上。手推得到会落在 (m-k,n+k) 这个点上。

然后...就直接循环暴力做就行了，计算次数不超过 m+n 次。

发现每一行是在 m+1 个数中选择 m 个数递增填上去，于是设 f_{i,j} 表示第 i 行没有出现的数是 j，由限制条件 x_{i,j}<x_{i,j+1},x_{i,j}<x_{i-1,j+1} 可得 f_{i,j}=\sum\limits_{k=0}^{j+1} f_{i-1,k}=f_{i,j-1}+f_{i-1,j+1}

然后把下标化为二维坐标画在坐标系上就长这个样子：

斜着不太好看，于是我们对于第 i 行向右平移 i 个单位，再将左侧的转移改为先向右再向下转移，得到下图：

继续变换使其变为上一类问题，得：

这样问题就变成了从点 (0,0) 走到点 (n+m+1,n) 且不经过直线 y=x+1 和 y=x-(m+2) 的方案数，直接使用上面提到的做法即可。