卡特兰数

卡特兰数 一、卡特兰的历史以及卡特兰定理 Catalan，Eugene，Charles，卡特兰（1814～1894）比利时数学家，生于布鲁日（Brugge），早年在巴黎综合工科学校就读。1856年任列日（Liege）大学数学教授，并被选为比利时布鲁塞尔科学院院士。卡特兰一生共发表200多种数学各领域的论著。在微分几何中，他了下述所谓的卡特兰定理：当一个直纹曲线是平面和一般的螺旋面时，他只能是实的极小曲面。他还和雅可比（Jacobi，C·G·J）同时解决了多重积分的变量替换问，建立了有关的公式。 1842年，他提出了一种猜想：方程xz－yt＝1没有大于1的正整数解，除非平凡情形32－23＝1。这一问题至今尚未解决。（mathoe注：即除了8、9这两个连续正整数都是正整数的方幂外，没有其他。1962年我国数学家柯召以极其精湛的方法证明了不存在三个连续正整数，它们都是正整数的方幂，以及方程x2－yn＝1，n＞1，xy≠0无正整数解。并且还证明了如果卡特兰猜想不成立，其最小的反例也得大于1016。）此外，卡特兰还在函数论、伯努利数和其他领域也做出了一定的贡献。 二、卡特兰数 卡特兰通过解决凸n边形的剖分得到了数列 。 凸n＋2边形用其n－1条对角线把此凸n＋2边形分割为互不重叠的三角形，这种分法的总数为Cn。 为纪念卡特兰，人们使用“卡特兰数”来命名这一数列。 原理： 　　令h(1)＝1,h(0)=1，catalan数满足递归式： 　　h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2) 　　另类递归式： 　　h(n)=((4*n-2)/(n+1))*h(n-1); 　　该递推关系的解为： 　　h(n)=C(2n,n)/(n+1) (n=1,2,3,...) 据说有几十种看上去毫不相干的组合计数问题的最终表达式都是卡特兰数的形式。 前几个卡特兰数：规定C0＝1，而 C1＝1，C2＝2，C3＝5，C4＝14，C5＝42， C6＝132，C7＝429，C8＝1430，C9＝4862，C10＝16796， C11＝58786，C12＝208012，C13＝742900，C14＝2674440，C15＝9694845。 递推公式 三、卡特兰数的应用 实质上都是递归等式的应用 1.括号化问题 　　矩阵链乘： ，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的？( 种) 2.出栈次序问题 　　一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列? 　　分析：　　对于每一个数来说，必须进栈一次、出栈一次。我们把进栈设为状态‘1’，出栈设为状态‘0’。n个数的所有状态对应n个1和n个0组成的2n位二进制数。由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。 　　在2n位二进制数中填入n个1的方案数为 ,不填1的其余n位自动填0。从中减去不符合要求（由左而右扫描，0的累计数大于1的累计数）的方案数即为所求。 　　不符合要求的数的特征是由左而右扫描时，必然在某一奇数位2m+1位上首先出现m+1个0的累计数和m个1的累计数，此后的2(n-m)-1位上有n-m个 1和n-m-1个0。如若把后面这2(n-m)-1位上的0和1互换，使之成为n-m个0和n-m-1个1，结果得1个由n+1个0和n-1个1组成的2n位数，即一个不合要求的数对应于一个由n+1个0和n-1个1组成的排列。 　　反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于0的个数多2个，2n为偶数，故必在某一个奇数位上出现0的累计数超过1的累计数。同样在后面部分0和1互换，使之成为由n个0和n个1组成的2n位数，即n+1个0和n-1个1组成的2n位数必对应一个不符合要求的数。 　　因而不合要求的2n位数与n＋1个0，n－1个1组成的排列一一对应。 　　显然，不符合要求的方案数为 。由此得出 输出序列的总数目= 。 　　3.剧院买票入场问题 　　有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈) 4.凸多边形的三角剖分问题 　　求将一个凸多边形区域分成三角形区域的方法数。 　　类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ 　　类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 5.用给定节点组成二叉树的问题 　　给定N个节点，能构成多少种不同的二叉树？ （能构成 个） 四、卡特兰数是整数 卡特兰数 ，求证：卡特兰数Cn是整数。 证明：分五部分证明 ①取整函数不等式：对任意实数x，y有[x＋y]≥[x]＋[y]。这里[x]表示不大于实数x的最大整数。 解：由定义x≥[x]……（1）                  y≥[y]……（2）以上两式相加，得：x＋y≥[x]＋[y]，        把上式再取整，得：[x＋y]≥[[x]＋[y]]＝[x]＋[y]，即[x＋y]≥[x]＋[y]。 ②1000！的末尾0的个数249个。（现在有的小学奥数书上出现了100！末尾有几个零的题目：24个） 解：1000÷5＝200，         200÷5＝40，         40÷5＝8，         8÷5＝1……3        以上各商相加，即得1000！末尾0的个数＝200＋40＋8＋1＝249个。 ③n！的质因数分解式中质因子p的幂次数： …………（1） k！的质因数分解式中质因子p的幂次数 …………（2） (n－k)!的质因数分解式中质因子p的幂次数 …………（3） 这里写成西格马求和式时使用了无穷的形式，但是从某一确定项之后的每项都是0，为了统一，都写成了“∞”形式。 ④组合数是整数 解： ⑤卡特兰数是整数 ⑥卡特兰数是整数的另外一个证明 ④组合数是整数 ⑤卡特兰数是整数 ⑥卡特兰数是整数的另一个证明 五、练习题： 1．2003年浙江省小学数学夏令营竞赛考了这个题：圆周上10个点可以连成既不相交，也没有公共端点的5条线段，不同的连法共有_____种。 答：方法的种数是卡特兰数C5＝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，即卡特兰数C5＝42。 又由于每个小朋友是不相同的，所以共有42×5！×5！＝42×120×120＝604800种情况。 若把此题的10个人，拿1元的有5人，拿2元的有5人改为共有2n个人，拿1元的n人，拿2元的n人，则符合要求的排队方法数为： 3、甲乙两人比赛乒乓球，最后结果为20∶20，问比赛过程中甲始终领先乙的计分情形的种数。 解：即甲在得到1分到19分的过程中始终领先乙，其种数是卡特兰数 4、饭后，姐姐洗碗，妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。一共有n个不同的碗，洗前也是摞 成一摞的，也许因为小妹贪玩而使碗拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起的碗有多少种可能的方式？ 答：得数是第n个卡特兰数Cn。 5、一个汽车队在狭窄的路面上行驶，不得超车，但可以进入一个死胡同去加油，然后再插队行驶，共有n辆汽车，问共有多少种不同的方式使得车队开出城去？ 答：得数是第n个卡特兰数Cn。 注：1、凸六边形剖分成三角形的14种方法，是卡特兰数C4 2、从左下角（0，0）走到右上角（4，4），只允许向上、向右走，但不允许穿过对角线的方法数是14种，是卡特兰数C4 关于卡特兰数的国际竞赛题， 1、1936第40届匈牙利奥林匹克数学竞赛 第1题考了Catalan恒等式的证明。 2、1979第21届国际数学奥林匹克 第1题考了一个卡特兰恒等式的应用的题目 3、 此题由1989年第1届匈牙利-以色列数学竞赛题改编。 1936第40届匈牙利奥林匹克数学竞赛 第1题考了Catalan恒等式的证明。 _1353496018.unknown _1353496132.unknown _1353496211.unknown _1353496324.unknown _1353496164.unknown _1353496070.unknown _1353485819.unknown