妙用卡特兰数公式解题

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《妙用卡特兰数公式解题》，欢迎阅读！

龙源期刊网 http://www.qikan.com.cn

妙用卡特兰数公式解题

作者：尼志福 赵广华

来源：《文理导航》2017年第11期

摘要： 卡特兰数又称卡塔兰数，是组合数学中一个常出现在各种计数问题中出现的数列，是以比利时数学家欧仁.查理. 卡塔兰命名。许多高中数学问题可以用它来解决。 关键词 卡特兰数 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条线段不相交的方法数。。

本文来源：https://www.wddqxz.cn/4b61c7274bfe04a1b0717fd5360cba1aa8118ca8.html