卡特兰数学习笔记

万航之舰 · 2022-09-27 20:52:38 · 个人记录

简介

总之就是一个很神奇的数列：1,1,2,5,14,42,132…… 可以由多种递推式、通项公式得出 运用相关思想，能够解决很多奇奇怪怪的计数问题

<br>

<br>

经典应用

长度为2n的括号序列个数

就类似()()()这种序列，每一个前括号，在它后面都有唯一一个后括号都能对应

考虑第一个左括号与第i个右括号匹配，那么这对括号之间是一串长度为2(i-1)的括号序列，这对括号右边是一串长度为2(n-i)的括号序列，两者相互独立，根据乘法原理，就有：

最后f(n)即为卡特兰数第n项，这也是卡特兰数的递推式之一

在网格图中，在正方形右下方从（0,0）走到（n,n）的方案数

将问题描述得更加具体一点： 在网格图中，只允许向上或向右走，且不允许越过正方形连接(0,0),(n,n)的对角线，求总方案数

显然：往右走的步数等于往上走的步数，且路径不越过对角线，说明对于任意时刻，向上走的次数都不超过向下走的次数。换言之假设最后方案为一个向右向上的操作序列（如右上右右上上），对于序列中任意向右走的操作，在它右边都有唯一一个向上走的操作，这与括号序列的定义一致

所以该问题的答案为：

<br> <br>

组合数优化

虽然我们求出了递推式，但是该递推式的复杂度为 O(n^2) ，并不优秀。我们可以尝试优化一下。

考虑第二个例子

为了方便讨论，我们将在网格上的操作转换为在数轴上的操作。即将向右操作变为 +1（或者说向右移动），向上操作变为 -1 （或者说向左移动）。那么“任意时刻，向上走的次数都不超过向下走的次数”就可以转换成“对于操作任意时刻，-1的个数不大于1的个数”，也即“对于任意时刻，路径不越过数轴原点”的方案个数

这乍一看感觉不是很好统计。那我们不妨统计所有可能序列和所有不合法的序列，然后相减得出答案

统计所有可能序列非常简单，一共有 2n 个空，选择其中 n 个填上 1，剩下只能填 -1，结果显然为 \binom{n}{2n}

那么怎么统计不合法操作呢？接下来就是计算卡特兰数及相关问题最重点的部分：

我们考虑将路径到达点 -1 后的操作全部取反：比如原来操作为: +1,-1,-1,+1,+1,-1 取反后就是

我们将此操作在数轴上的路径称作取反路径（我自己瞎编的名字） 不难发现以下性质：

取反路径终点落在 -1

由于我们在 -1 点将所有操作取反，假设此时向右走了 i 步，剩下 n-i 步能走，向左走了 i+1 步，剩下 n-i-1 步能走。 也就是说，取反后，我们会继续向右走 n-i-1 步，总共向右走了 n-1 步，同理向左走了 n+1 步。最终落点即为 -1

取反路径与原非法路径一一对应

每一个非法路径都必然会经过 -1，也就必然会诞生对应的取反路径。而对于每一个取反路径，我们将他第一次碰到 -1 的时候取反，也会反推出唯一的原路径

所以综上所述，

综上所述：原问题答案为：

这也是卡特兰数的公式

应用

对于这种对于操作a和操作b各有n次，要求满足任意时刻操作b的次数不能超过操作a，，求方案数的题目，都可以直接套卡特兰数的公式\binom{n}{2n}-\binom{n-1}{2n}。非常的简单

比如：我没有零钱，现在有n个拿50元的顾客和拿100元的顾客，每一个拿100元的顾客都需要找零50，求排队方案数。很显然，就是说任意时刻拿100元的顾客数量都不超过拿50元的，答案直接就是\binom{n}{2n}-\binom{n-1}{2n} <br> <br>

拓展

非常显然，并不是所有（事实上是几乎没有）题目会完全就是最基础的卡特兰数，大都会写一些奇奇怪怪（非常恶心）的题面。

先考虑最基础的拓展：有n个操作a和m个操作b，要求在任一时刻操作a与操作b数量之差不低于m。

我们还是按照原来的思路，把a当做 +1，b当做 -1 所有可能方案数为\binom{n}{n+m}

而计算所有非法方案数：、当每个方案到达数轴 -k 处时取反所有操作。假设此时向右走了 i 步，向右剩下 n-i 步能走，向左剩下 m-i-k 步能走。 此时我们会继续向右走 m-i-k 步，总共向右走了 i+(m-i-k)=m-k 步，同理向左走了 (n-i)+(i+k)=n+k 步。最终落点即为 m-k-(n+k)=m-n-2k

所以非法序列答案即为 \binom{m-k}{n+m}

最终答案即为：

个人感觉这是做题时最常用的式子，剩下的都是在这个基础上根据题目各种推式子

（本来计划加一些题目什么的，但貌似没有时间了，就先到这里吧）