卡特兰数

一、背景与定义

1.背景

Catalan，Eugene，Charles，卡特兰（1814～1894）比利时数学家，生于布鲁日（Brugge），早年在巴黎综合工科学校就读。1856年任列日（Liege）大学数学教授，并被选为比利时布鲁塞尔科学院院士。

卡特兰一生共发表200多种数学各领域的论著。在微分几何中，他证明了下述所谓的卡特兰定理：当一个直纹曲线是平面和一般的螺旋面时，他只能是实的极小曲面。他还和雅可比（Jacobi，C·G·J）同时解决了多重积分的变量替换问题，建立了有关的公式。

1842年，他提出了一种猜想：方程x^z－y^t＝1没有大于1的正整数解，除非平凡情形3²－2³＝1。这一问题至今尚未解决。

（mathoe注：即除了8、9这两个连续正整数都是正整数的方幂外，没有其他。1962年我国数学家柯召以极其精湛的方法证明了不存在三个连续正整数，它们都是正整数的方幂，以及方程x²－yⁿ＝1，n＞1，xy≠0无正整数解。并且还证明了如果卡特兰猜想不成立，其最小的反例也得大于10¹⁶。）

此外，卡特兰还在函数论、伯努利数和其他领域也做出了一定的贡献。

2.定义

卡特兰通过解决凸n边形的剖分得到了数列C_n。

凸n＋2边形用其n－1条对角线把此凸n＋2边形分割为互不重叠的三角形，这种分法的总数为C_n。

为纪念卡特兰，人们使用“卡特兰数”来命名这一数列。

据说有几十种看上去毫不相干的组合计数问题的最终表达式都是卡特兰数的形式。卡特兰数在数学竞赛、信息学竞赛、组合数学、计算机编程等都会有其不同侧面的介绍。

3.递推公式

前几个卡特兰数：规定C₀＝1，而

C₁＝1，C₂＝2，C₃＝5，C₄＝14，C₅＝42，

C₆＝132，C₇＝429，C₈＝1430，C₉＝4862，C₁₀＝16796，

C₁₁＝58786，C₁₂＝208012，C₁₃＝742900，C₁₄＝2674440，C₁₅＝9694845。

递推公式

圆周上有标号为1，2，3，4，……，2n的共计2n个点，这2n个点配对可连成n条弦，且这些弦两两不相交的方式数为卡特兰数C_n。

4.例题

例1：2003年浙江省小学数学夏令营竞赛考了这个题：圆周上10个点可以连成既不相交，也没有公共端点的5条线段，不同的连法共有_____种。

答：方法的种数是卡特兰数C₅＝42，此题被收录进单墫主编的知识出版社出版的《华数奥赛强化训练》小学六年级册的“计数问题”专题。

共六种类型，第1类有5种连法，第2类有2种连法，第3类有10种连法，第4类有10种连法，第5类有10种连法，第6类有5种连法。共有42种连法。

例2：1994年《小学数学》有奖征答竞赛：游乐园门票1元一张，每人限购一张。现在有10个小朋友排队购票，其中5个小朋友每人只有1元的钞票一张，另5个小朋友每人只有2元的钞票一张，售票员没有准备零钱。问：有多少种排队方法，使售票员总能找的开零钱？（此题也被许多奥数资料收录为例题或习题，《华罗庚学校数学课本》小学六年级册的思维训练也收有此题）

答：现把拿1元的5个小朋友看成是相同的，把拿2元的5个小朋友也看成是相同的，使用我们常用的“逐点累加法”：

图中每条小横段表示拿1元的小朋友，每条小竖段表示拿2元的小朋友，要求从A走到B的过程中网格中任何点均有横段数不小于竖段数：拿1元的要先，且人数不能少于拿2元的，即不能越过对角线AB：每个点所标的数即为从A走到此点的方法数。求从A到B的走法的方法数。逐点累加可求出为42，即卡特兰数C₅＝42。

又由于每个小朋友是不相同的，所以共有42×5！×5！＝42×120×120＝604800种情况。