关于Catalan数的组合恒等式（2024年CTST第二轮第1题）
正文文字 500 字公式 42 处1 图
题目：
对自然数n，记
是卡塔兰数．求证：对任意自然数m，均有
前置知识：
卡塔兰（Catalan）数有非常丰富的性质，在组合计数问题中频繁出现。这里我们只需要知道它的如下性质：
通项公式：
C_(n)=(1)/(n+1)Cn2n=((2n)!)/(n!(n+1)!) 递推公式：
C_(n)=∑_(k=0)^(n−1)C_(k)C_(n−k−1) 母函数：
f(x)=(1−√(1−4x))/(2x)=2∑_(k=0)^(∞)(((1)/(2))/(k+1))(−4x)^(k) 组合意义：从原点(0,0)出发，每次向x轴或y轴正方向移动1个单位，到达点(n,n)，在移动过程中不越过第一象限平分线的移动方法总数．
参考资料：https://oeis.org/A000108、《命题人讲座——集合与对应》第八讲公式：\quad卡塔兰数
事实上，除了题中已给的通项公式外，使用另外三个性质都能比较快速地证明本题．
但使用母函数需要一定的基础，适合受过母函数训练的同学；使用组合意义则需要一定的灵感，我短时间内没有想到，数之谜上有一个很漂亮的使用组合意义的做法。
这里我们用递推公式进行证明：
展开解答收起解答
证明：
首先化简左边式子，考虑到C_(i+j)C_(j+k)C_(k+i)形式比较复杂，先作换元：
求和下标的条件变为x+y+z=2(i+j+k)=2m，而
奇偶性相同，故i,j,k∈Z⟺x,y,z∈Z．
但i,j,k≥0，于是应有x,y,z≤m．因此
若没有x,y,z≤m这一条件，∑_(x+y+z=2m)C_(x)C_(y)C_(z)比较好计算，可以固定z，将y改为(2m−z)−x，这样对C_(x)C_((2m−z)−x)的求和可以利用Catalan数的递推公式进行化简，如下：
接下来减去不满足x,y,z≤m条件的即可，考虑z≥m+1的情况，依然固定z：
注意到C_(z)C_(2m+1−z)是对称的，上式补上最后一项C_(2m+1)C_(0)，再乘2，即可将求和索引改为z从0到2m+1． 于是
再分别考虑x,y≥m+1的情况，并注意到它们不可能同时发生，于是
只需证明：
这由通项公式是显然的，于是我们完成了本题的证明．
一年一度全球数学爱好者的盛会，就差你了！
留言
正常留言提交后可直接显示，无需人工审核；仍会经过防刷与垃圾内容过滤。请不要留下手机号等私人信息。解法、疑问都可以说；公式用 LaTeX：行内
$…$，整行$$…$$。