妙用卡特兰数公式解题

摘要： 卡特兰数又称卡塔兰数，是组合数学中一个常出现在各种计数问题中出现的数列，是以比利时数学家欧仁.查理. 卡塔兰命名。许多高中数学问题可以用它来解决。

关键词 卡特兰数 01数列

2016年高考数学全国丙卷有这样一道题目。定义“规范”01数列 如下： 共有2m项，其中m项为0，m项为，1，且对任意k 2m， 中0的个数不少于1的个数。若m=4，则不同的“规范”01数列共有（ ）

A18个 B16个 C14 个 D12个

此题答案为C，多数人采用列举的方法解决此题。思路如下：

因为m=4，所以 共有8项，4项是0，4项是1。又因为对任意k 2m， 中0的个数不少于1的个数，所以首项 ，末项 。其余6项3项为0，3项为1，共有 種，其中01110001，01101001， 01100101，01100011， 00111001， 01011001 6种情况不和题意，故“规范”01数列共有 个。笔者在讲这道题目时，有头脑灵活的学生提出这样一个人思路：此题看成在一个4 4正方形中，由正方形一个顶点去相对顶点，行走过程中只能向上或向右，向上走一步用1表示，向右走一步用0表示，行走过程中不能经过对角线以上的点，问有几种走法？

受学生问题启发，我查阅相关资料发现这个题可以利用卡特兰数公式来解决。卡特兰数又称卡塔兰数，是组合数学中一个常出现在各种计数问题中出现的数列，是以比利时数学家欧仁.查理. 卡塔兰命名。其通项公式

它能解决如下高中数学中常见问题。

1.n个+1和n个-1构成项数为2n的数列 ，其部分和满足 问满足条件的数列有多少个？

2.有2n个人排成一行进入剧场，入场费5元，其中n个人只有一张5元钞票，另外n个人只有一张10元钞票，问有多少种方法使得只要有10元的人买票，售票处就有5元的钞票找零？

3.在圆上选择2n个点，将这些点成对连接起来，使得所得到的n条线段不相交的方法数。。

这些问题的结果都为 。

有些题目看似不能用卡特兰数公式解，决但经过转化就可用。例如有这样一道题：8个高矮不同的人，排成两排，每排必须是从矮到高排列，而且第二排比对应的第一排的人高，问排列方式有多少种？

这个题可以看成把8个人排成一个数列，排在前排的为0，排在后拍的为1，这样就转化为这个数列4项为0，4项为1. 8个人从低到高对应数字1，2，3 8，每一个0 1数列都按照从小到大顺序排列，即对应数字1，2，3 8。如：00011011对应排列

第一排1 2 3 6 第二排4 5 7 8 01110001就对应排列 第一排1 5 6 7

第二排2 3 4 8 要满足第二排比对应的第一排的人高，必须对任意k 8， 中0的个数不少于1的个数这样此题就转化为和我们开始讲的2016年高考数学全国丙卷那道题为同一题目了。

在我们日常教学中，对学生进行适当的知识扩充，就会使许多问题简单化。当然这需要我们自身知识丰富，不断学习，才能把大学知识与高中适当衔接。

推荐访问： 卡特 解题 妙用 公式