2024年9月3日
最近在查阅部分和相关问题时，发现一种证明卡塔兰数列通项公式的新方法！
需要用到的关键引理是Raney’s Lemma，该引理也是极端原理的训练好题，这里给出我的分析思路，最后计算卡塔兰数。
【Raney’s Lemma】圆周上顺次放了一些和为1的整数.
证明：圆周上存在唯一位置，以其为起点，顺时针任意连续若干项的和恒正.
引理证明
考察简单情形
当时，两数为，必选起始；
当时，三数为，选出发
或，选出发。
我们总能发现，选法会包含连续和最大的部分作为起点。
猜测关键元素
设这个数为，考虑这些数组成的所有连续和（模意义下），其中最大的那一个为
我们希望说明就是唯一起始点。
先检查基本的情况：
在S内部时 考虑时的连续和
若,则，与的最大性矛盾；
若,则，与当前预设并不矛盾，需要优化。
注意到在S后添加-1，1，不改变最大性，也不改变最前面的起始，于是我们优化预设为【最大的且长度最短的连续和】，在此预设下情形会产生更短的最大连续和，产生矛盾！
在S外部时，考虑时的连续和
为保证,则,也就是说希望这些连续和也不能太“负数”，即绝对值不能超过，这可以办到吗？
可以！这里就要用到条件中的
我们考虑这些连续和中最小的一个为，则剩下的一段和为,这是一一对应的，即说明最大的连续和S选出后，最小的连续和就是剩余部分，即为.
故我们也说明了在S外部的情形。
唯一性的证明
此时，我们还需说明的唯一性，用反证法：
若不唯一，则有两段最大最短连续和,不妨设
最短长度为
情形一:若，即有覆盖这两段连续和的连续和
有，与S最大性矛盾.
情形二:若
有，
由条件知，的长度大于,显然也不超过，故我们考虑减去一圈：
（i）若，则又找到更大的连续和，与S的最大性矛盾；
（ii）若,因为则的长度<S的长度，与S的最短性矛盾.
综上所述，我们证明了Raney’s Lemma.
运用Raney’s Lemma 计算卡塔兰数
转化命题
【卡塔兰数原命题】有个，个排成一排，使得
则满足要求的排列有。【转化命题】为和Raney’s Lemma产生联系，我们添加，于是就转化为有个，个排成一排，使得
则满足要求的排列有。建立对应
原命题的个数前面加上1，均可得到一种符合转化命题的数组，有;
转化命题的个数划去最开始的1，均可得到一种符合原命题的数组，有；
于是.
运用Raney’s Lemma
【Raney’s Lemma】圆周上顺次放了一些和为1的整数.
证明：圆周上存在唯一位置，以其为起点，顺时针任意连续若干项的和恒正.
由Raney’s Lemma，我们只需考察个，个的圆排列种数（旋转重合的为一种）。
说明这些圆排列的“自旋最小正周期”d=2n+1
记“自旋最小正周期”为d，因为旋转必重合，则有;
下考虑个1的下标，每个都变大了后又与原先重合，说明在模下，下标没有变化，则有
综上.
计算圆排列数
由，结合算两次知
综上，我们运用Raney’s Lemma完成了对卡塔兰数通项新求法！
思考题
【思考题】圆周上顺次放置了和为0的n个数,每个均为或,其中是两个互素的正整数. 证明：圆周上存在一段个数少于的连续的数和为
【思考题推论】时,圆周上存在唯一位置,以其为起点,顺时针任意连续若干项的和恒正.
如果觉得文章有价值，恳请您点个赞和在看！
欢迎后台交流！
往期精彩文章：
一、高联问题深度探究
简单又深刻！为什么立方数通常模7或9分析？——21高联B卷P4
观察大趋势，琢磨小细节——例谈离散不等式解题模式(23东南赛高一P7)
时刻观察特点，寻找思维捷径——丝滑分析2023中国女奥P6代数
二、强基自招
三、难题研究
组合零点定理（2）解北大“怀新一题”20230509期“数学家聚会”问题
////// END //////
