Catalan数和它的有关问题

# Catalan数和它的有关问题 ## 0.Catalan数的引入： 为了方便对其他问题的求解我们推出如下数列：  为了方便说明，我们将$C(n)$定义为在$n*n$的网格内只能沿水平或竖直方向上移动一个单位长度且不越过红线从左下角移动至右上角的路径数。（仅为在本文中的定义） 然后我们使用递推的方法可以简单的求得其路径数：  于是我们就得到了数列的前8项（从第0项开始）：1，1，2，5，14，42，132。 我们可以通过容斥的方式来求得通项公式： - 合法路径数量=总路径数量-非法路径数量。 - 总路径数量等于有$2n$次决策，选择$n$次沿水平方向移动的方案数，为$\dbinom{2n}{n}$ - 对于非法路径数量，我们可以发现每一条非法路径必然经过在红线向上平移一个单位长度所在线的点，所以我们将其为对称轴，求出终点的对称点，则每一条非法路径对应了原始图上到对称点的路径，为$\dbinom{2n}{n-1}$ - 所以合法路径数量为$\dbinom{2n}{n}-\dbinom{2n}{n-1}$。 所以在不知道递推关系的情况下我们得出了通项公式。 ## 1.入门的转化： ### 转化一：合法的n对括号匹配方案数 我们发现括号匹配合法当且仅当任意时刻左括号数不严格大于右括号数，且在最终时刻左括号数等于右括号数。我们将左括号看作在水平方向移动，将右括号看作在竖直方向移动，转化一与引出问题为等价问题。 ### 转化二：n个元素入栈并且出栈的方案数： 我们将一个元素入栈当作左括号，出栈当作右括号，显然入栈数不严格大于出栈数，且在最终时刻入栈数等于出栈数。转化二与转化一为等价问题。 ### 转化三：n个节点的二叉搜索数的个数： 我们考虑如下方案，在进入一个节点是写入左括号，然后递归左子树的节点，写入右括号，然后递归右子树的节点，我们发现每一个不同形态的二叉树唯一对应着一种合法的括号匹配，转化三与转化一为等价问题。 我们不难给出另一种证明的方案，考虑笛卡尔树的构建方式，我们通过用栈来实现，所以任意一种栈的出入方案对应了一颗笛卡尔树，至于如何把笛卡尔树对应到栈上，留给读者自行思考，转化三与转化二为等价问题。 ### 问题1：圆上$2n$个点的不相交弦的方案数 ### 推广： 我们可以通过证明一个问题与原有问题的等价性（需要证明充分性和必要性，简单的来说就是能一一转化过来，也能一一转化过去），来证明其满足原有问题的性质，这是充分但不必要的。 ## 2.进阶的转化： 凸n+2边形的三角划分:以五边形为例  我们如何把它也转化成我们可以解决的问题呢？ 大家可以思考一下。 changle_cyx %%% 给出的做法如下： - 把每个三角形看成二叉树的一个结点。 - 首先固定任意的一条边（怎么选开心就好，但是注意是固定）。 - 然后以这条边所在的三角形为根。 - 向下有公共边的就是儿子，具体来说就是对于已知的三角形，对于原有的一条边（开始固定的或者上次个三角形推过来的），顺时针相邻的边，连接右儿子，逆时针相邻的边连接左儿子。 - 这样，任意一种划分方式，对应了一种二叉树的形态，转化完毕。 然后也有如下的还原方式： - 把每个三角形看成二叉树的一个结点。 - 首先固定任意的一条边（怎么选开心就好，但是注意是固定）。 - 我们可以得出左右子树的大小，然后按照大小我们可以从多边形上找到一个点，向固定边连线，满足逆时针侧部分为左子树大小，顺时针侧的部分为右子树大小。 - 递归进行。 - 这样，任意一种二叉树的形态，对应了一种划分方式，转化完毕。 ## 3.本源的探究： 显然假如这些问题都满足同一个计算方式，其本身也必然满足某一个性质。 首先是括号序列： - 已知A，B为合法的括号序列。 - A(B)也是一个合法的括号序列。（显然成立） 对此我们就找到了他的递推公式： $$ C_{n+1}=\sum\limits_{i=0}^nC_iC_{n-i} $$ 然后根据事实我们可以得到：$C_0=1,C_1=1$。（0对括号的匹配方式就是 ~~前边一个空，只有聪明的人才能看见~~，显然是一个啊）。 同理我们可以对n个元素入栈并且出栈的方案数，得出同样的结论，本文不再说明。 再看下一个问题：n个节点的二叉搜索数的个数 等于固定根节点后，左右子树大小之和为n-1的方案数。 $$ C_{n}=\sum\limits_{i=0}^{n-1}C_iC_{n-i-1} $$ 凸多边形的三角划分，与之同理，本文不再说明。 ### 推广： 假如一个问题可以满足给定递推公式，且已知项相同，则可能存在与已知问题进行转化的方案，但这不是充分也不是必要条件，只能说是启发。 ### 问题2： 我们发现一个问题，那就是：引出问题与转化一，二形式类似，转化三与进阶的转化形似类似，他们直接可以进行较为容易的转化，但是转化一与转化三之间却需要复杂的转化。 下面提出一个问题留给读者思考： 我们发现最好表示的括号序列，仍然需要$2^{2n}$来表示，但是显然卡特兰数并没有那么大，如何建立起一种映射关系呢？ 我们把这个问题换成一个OI的形式，这是一道通信题：给定一个长度为n的序列，需要用值域为$[1,C_n]$的整数去表示，还原后可以回答区间内最大值的所在位置。 ## 4.OI的应用： ### 例题一： 从$[1,2n]$中，选出n个数将其按照大小排序称其为序列A，剩下的n个数也将其大小排序称其为序列B，然后一一比较大小，求n次比较B的数始终比A的数的方案数。 当然这个题可以用~~杨氏矩阵和[钩子公式](https://en.wikipedia.org/wiki/Hook_length_formula)去直接解释~~: $$ \lambda=(n,n),C_n=f^{\lambda} $$ 我们也可根据上文的转化，给出另一种方法： 我们将序列A的数看作左括号，B的数看作右括号，排序之后，需要满足合法匹配，至此问题解决。 ### 例题二：BZOJ 3907 求网格图，到$(n,m)$且不越过$x=y$的路径数量。 我们可以根据引出问题的方式，做出其对称点$(m-1,n+1)$，然后答案就是$\dbinom{n+m}{n}-\dbinom{n+m}{n+1}$。 ### 例题三：[P3200 [HNOI2009]有趣的数列](https://www.luogu.com.cn/problem/P3200) 我们不难发现，将奇数项和偶数项看作A和B序列，两个问题等价。 ### 例题四：[P2532 [AHOI2012]树屋阶梯](https://www.luogu.com.cn/problem/P2532) 我们可以将最左上的一个点看作根节点，然后向右拓展的点看作右子树，向下拓展的点看作左子树，这里做出一个比较感性的解释，可以结合样例理解，（我无法证明它的正确性）。   我们换一种理性的方式： 我们设一个有(n-1)个L形的拐角的子图形的方案数为$f(n)$，对于$f(n+1)$所对应的图形，我们枚举一个向外突出的拐角与原点所组成的矩形，这样我们就可以得出$f(n+1)=\sum\limits_{i=0}^{n}f(i)f(n)$，确认其前几项之后，我们可以不完美的证明f数列就是C。 ## 5.高中数学的应用： 这大概是一道出烂了的题。 用$n$个格子，进行黑白涂色，要求在任意前缀中，白色始终不小于黑色的方案数。 我们回归引出问题的方法，我们可以再做一条$x+y=n$的直线，直线所在格点，合法路径的方案数。 然后我们可以根据例题二求出每个格点的方案数。 $$ (\sum\limits_{i=\lceil\frac{n}{2}\rceil}^{n}\dbinom{n}{i}-\dbinom{n}{i+1})=\dbinom{n}{\lceil\frac{n}{2}\rceil} $$ 其实在高中的数学题中$n=6$，啊这，好简单啊。 ## *6.关于杨氏矩阵与钩子公式： 根据例题二，我们对到$(n,m)$且不越过$x=y$的路径数量，得出了公式$\dbinom{n+m}{n}-\dbinom{n+m}{n+1}$。 但是这个问题转化到括号匹配上就是不合法的括号匹配，在栈上就是不出栈的方案数。 在例题一中，我们已经提到过了杨氏矩阵与钩子公式，大家可以自行学习杨氏矩阵与钩子公式，并且思考一个入门问题，可以用杨氏矩阵与钩子公式解释上述问题吗？ 拓展阅读：2019国家集训队论文%%%。 ## 7.关于其他递推公式： Catalan数还存在其他的通项公式： $$ \frac{1}{n+1}\dbinom{2n}{n} $$ 我们可以推导出上式： $$ \begin{aligned}\dbinom{2n}{n}-\dbinom{2n}{n-1}&=\frac{(2n)!}{n!*n!}-\frac{(2n)!}{(n+1)!(n-1)!}\\&=\frac{(2n)!}{n!*n!}-\frac{(2n)!}{n!*n!*\frac{n+1}{n}}\\&=\frac{(2n)!}{n!*n!}*(1-\frac{n}{n+1})\\&=\frac{1}{n+1}\dbinom{2n}{n}\end{aligned} $$ Catalan数还存在其他的递推公式： $$ C_{n+1}=\frac{4n+2}{n+2}C_n $$ 我们可以对推导出上式： $$ \begin{aligned}\dfrac{C_{n+1}}{C_{n}}&=\dfrac{\dfrac{1}{(n+1)+1}\dbinom{2n+2}{n+1}}{\dfrac{1}{n+1}\dbinom{2n}{n}}\\&=\dfrac{n+1\dfrac{(2n)!*(2n+1)(2n+2)}{n!*n!*(n+1)(n+1)}}{n+2\dfrac{(2n!)}{n!*n!}}\\&=\frac{4n+2}{n+2}\end{aligned} $$ 但是只是在数学意义上证明了正确性，暂时没有找到与这个公式吻合的实际意义。（是我太弱了）。 ~~问题2.5：提出一个满足上式实际意义的题目~~ ## 8.其他题目： ### 问题3： ~~~ 恶梦是一个登山爱好者，今天他来到了黄山。 俗话说的好，不走回头路。所以在黄山，你只能往前走，或者往上走d。并且很显然的是，当你走到山脊的时候，你不能够往上走，你只能往前走一步再往上走。 抽象一点而言就是，你可以把黄山视为一个N * N格点图，恶梦从(0,0)开始出发，要走到(N,N)。当他走到位置(x,y)的时候，它可以往(x + 1,y),或(x,y+1)走。 并且当他走到(x,x)的时候，由于他已经处在了山脊上，所以他不能够往(x,x+1)方向上走。 当恶梦兴致勃勃准备开始爬山的时候，他的同伴告诉他，黄山由于年久失修，有一些位置出现了大坑，不能走。恶梦觉得更刺激了，但他想先知道他能有多少种方式走到黄山顶。 由于这个数字很大，所以你只需要将答案对10^9 + 7取模输出即可。 N≤100000,C≤1000 ~~~ ### 问题4： ~~~ ztxz16旅游归来后十分疲倦，很快就进入了梦中。 在梦中ztxz16结婚生子了，他不得不照顾小宝宝。但这实在太无聊了，于是ztxz16会在散步。梦中ztxz16住在一个类似数轴的街上，数轴上的每个整点是一个街区，每个单位时间内ztxz16可以选择向左走一个街区或者向右走一个街区，但如果他离开家超过m个单位时间小宝宝会有危险，因此ztxz16必须在距离上次在家中不超过m个单位时间内回到家中。 n个单位时间后ztxz16会醒来，他希望此时正好在家中。 ztxz16想知道散步过程可能有多少种不同的散步过程。两个散步过程被认为不同，当且仅当存在至少一个单位时刻ztxz16选择的走向不同。 2≤n≤1e9，2≤m≤100 ~~~ ## 9.结束： 以上是我的一点拙见，如有不足请大家谅解，欢迎大家指出文中出现的问题。