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

——从一道组合问题说起

(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分,目前已被哈尔滨工业大学数学系本硕博连读专业录取(强基计划),高中阶段在《数学通讯》上发表文章一篇

(0)

相关推荐