卡特兰数通项公式的发现历程

——从一道组合问题说起

（2021 年 1 月 THUSSAT 理科数学第 14 题）现将大小和形状相同的 4 个黑球和 4 个红球排成一排，从左边第一个球开始数，不管数几个，黑球不少于红球的排法有______种.

一、原问题的解决与新问题的提出

但是这只是黑球与红球各有 4 个的情况，那么我们能否尝试推出一般规律呢？

变式：现将大小和形状相同的 n 个黑球和 n 个红球排成一排，从左边第一个球开始数，不管数几个，黑球不少于红球的排法有______种.

将上图扩展到 n 阶，进行简化后，我们可以得到一个类似于杨辉三角形的组合三角形：

通过观察，我们可以得到组合三角形的如下性质：（1）组合三角形每一行比上一行多一个数；（2）每一个数等于其上方的数加左边的数（最左边一列、顶部数字除外）；（3）从第 1 行开始，每一行最后两个数相等（认为第一个 1 为第 0 行）. 而我们则需要寻找每一行最后一个数的规律.

二、组合三角形的组合数表示

对于排列组合中与数有关的找规律问题，我们常常联想到杨辉三角形，它包含了所有组合数，把待求数组用组合数表示有利于我们观察数的隐藏规律，例如数列 1，7，21，35...可能难

至此，我们已经找到组合三角形前 2 列数的规律。但是，真正考验我们观察力、推理力的挑战也就此开始。其实，我们在这里应用的是数学中十分基础且重要的解题思路：观察—猜想—归纳—证明，或者说是“由特殊到一般”。说个题外话，现在许多同学都了解“由特殊到一般”的数学分析思路，事实上，这是不够完整的，因为数学分析的根本目的是解决实际问题而非发现规律，因此“到一般”绝不是终点，而应是“由特殊到一般再到特殊”，缺少了最后一个环节，就有了舍本逐末之感了。

言归正传。第 3 列，组合三角形的规律并不明显，因此我们可以借助杨辉三角形这个“组合数集”去发现规律. 由于第 1 列对应杨辉三角形中的第 1 斜列，第 2 列对应杨辉三角形中的第 2 斜列；因此，我们可以推测第 3 列对应杨辉三角形的第 3 斜列，只不过这次它有点“不老实”，给我们变了个身，经过简单观察，此处有表：

下面是第 4 列，也是我们发现规律最为关键的一列。同上文之理，我们应该从杨辉三角形的第 4 斜列发现规律。但是相较于第 3 列，该列更加难以观察，但是我们有了它变形的基本方法——作差。因此，稍作观察，又得一表：

三、归纳所得规律

四、规律的证明

我们要证明一个组合三角形，这句话听起来有点怪怪的。很明显，这个组合三角形是没有边界的，那么我们如何来完成证明呢？其实，证明这个组合三角形就是证明这个数阵的规律（或者说性质），但是老实说，这个数阵的规律很多，那么我们需要逐一证明吗？很明显不是。在这里，我们受数学归纳法的启发，可以尝试一种类似多米诺骨牌的证法：

思路与实效性：每一列的第一个数即是某一行的最后一个数，我们用结论 2 得到它，每一列有了第一个数以后，再用结论 1 即可得到每一列剩下的数...以此类推，我们便可以证明这个组合三角形。

证明结论 1：

五、原题通项公式与总结

卡特兰数的研究限繁复杂，但得出的通项公式确是简洁如斯，令人赞叹，这正体现了简洁的数学魅力，使一批又一批数学爱好者为之倾倒。当然，卡特兰数的研究方法有很多种，本文方法体现出数学中观察力的重要性。特此笔录，与君共勉。

作者简介：

殷鹏飞，2018-1021就读于河南省实验中学（高中），2021年参加河南省普通高招总分669分，数学单科145分，目前已被哈尔滨工业大学数学系本硕博连读专业录取（强基计划），高中阶段在《数学通讯》上发表文章一篇