组合数学
萌到你眼炸
721次浏览
2021年01月26日 13:55
最佳经验
本文由作者推荐
听课评语-
组合数学中的基本原理及其应用
卡特兰数
Catal an
，
Eugene
，
Charles
，卡特兰（
1814
～
1894
）比利时数学家，生于布鲁日（
Brugge
）
，早年在
巴黎综合工科学校就读。
1856
年任列日（
Liege
） 大学数学教授，并被选为比利时布鲁塞尔科学院院
士。
卡特兰一生共发表
2 00
多种数学各领域的论著。在微分几何中，他证明了下述所谓的卡特兰定理：当
一个直纹曲线 是平面和一般的螺旋面时，他只能是实的极小曲面。他还和雅可比（
Jacobi
，
C
·
G
·
J
）
同时解决了多重积分的变量替换问题，建立了有 关的公式。
1842
年，他提出了一种猜想：方程
x
z
－
y
t
＝
1
没有大于
1
的正整数解，除非平凡情形< br>3
2
－
2
3
＝
1
。这一问
题至今尚 未解决。
（
mathoe
注：即除了
8
、
9这两个连续正整数都是正整数的方幂外，没有其他。
1962
年我国数学家柯
召以 极其精湛的方法证明了不存在三个连续正整数，它们都是正整数的方幂，以及方程
x
2
－
y
n
＝
1
，
n
＞
1
，
xy
≠
0
无正整数解。并且还证明了如果卡特兰猜想不成立，其最小的反例也得大于< br>10
16
。
）
此外，卡特兰还在函数论、伯努利数和其他领域也做出了一定的贡献。
卡特兰通过解决凸
n
边形的剖分得到了数列
C
n
。
凸
n
＋
2
边形用其
n
－
1条对角线把此凸
n
＋
2
边形分割为互不重叠的三角形，这种分法的总数为
C
n
。
为纪念卡特兰，人们使用
“
卡特兰数
”
来命名这一数列。
据说有几十种看上去毫不相干的组合计数问题的最终表达式都是卡特兰数的形式。
卡特兰数在数学竞赛、信息学竞赛、组合数学、计算机编程等都会有其不同侧面的介绍。
前几个卡特兰数：规定
C
0
＝
1
，而
C
1
＝
1
，
C
2
＝
2
，
C
3
＝
5
，
C
4
＝
14
，
C
5
＝
42
，
C
6
＝
132
，
C
7
＝
429
，
C
8
＝
1430
，
C
9
＝
4862
，
C
10
＝
16796
，
C
11
＝
58< br>786
，
C
1
2
＝
208012
，
C
1
3
＝
742900
，
C
14
＝
2674440
，
C
1
5
＝
9694845
。< br>
递推公式
圆周上有标号为
1，
2
，
3
，
4
，
……
，
2n
的共计
2n
个点，这
2n
个点配对可连成
n
条弦， 且这些弦两
两不相交的方式数为卡特兰数
C
n
。
2003
年浙江省小学数学夏令营竞赛考了这个题：圆周上
10
个点可以连成既不相交，也没有 公共端点
的
5
条线段，不同的连法共有
_____
种。
< br>答：方法的种数是卡特兰数
C
5
＝
42
，此题被收录进单墫主 编的知识出版社出版的《华数奥赛强化训
练》小学六年级册的
“
计数问题
”< br>专题。
- 1 -
共六种类型 ，第
1
类有
5
种连法，第
2
类有
2
种连法 ，第
3
类有
10
种连法，第
4
类有
10
种 连法，第
5
类有
10
种连法，第
6
类有
5
种连法。共有
42
种连法。
1994年《小学数学》有奖征答竞赛：游乐园门票
1
元一张，每人限购一张。现在有
10
个小朋友排队购
票，其中
5
个小朋友每人只有
1
元的钞票一 张，另
5
个小朋友每人只有
2
元的钞票一张，售票员没有准备
零钱。 问：有多少种排队方法，使售票员总能找的开零钱？
（此题也被许多奥数资料收录为例题或习 题，
《华罗庚学校数学课本》小学六年级册的思维训练也收
有此题）
答：< br>现把拿
1
元的
5
个小朋友看成是相同的，
把拿
2元的
5
个小朋友也看成是相同的，
使用我们常用的
“
逐
点累加法
”
：
图中每条小横段表示拿
1
元的小朋友，每条 小竖段表示拿
2
元的小朋友，要求从
A
走到
B
的过程中网< br>格中任何点均有横段数不小于竖段数：拿
1
元的要先，且人数不能少于拿
2元的，即不能越过对角线
AB
：每个点所标的数即为从
A
走到此点的方法 数。求从
A
到
B
的走法的方法数。逐点累加可求出为
42
， 即卡特兰数
C
5
＝
42
。
- 2 -
又由于每个小朋友是不相同的，所以共有
42×
5
！
×
5
！＝
42
×
120
×
120
＝
604800
种情况。
若把此题的
10
个人，拿
1
元的有
5
人，拿
2
元的有
5
人改为共有
2n
个人，拿
1
元的
n
人，拿
2
元的
n
人，
则符合要求的排队方法数为：
再一个卡特兰数的例子：
甲乙两人比赛 乒乓球，最后结果为
20
∶
20
，问比赛过程中甲始终领先乙的计分情形的种 数。
即甲在得到
1
分到
19
分的过程中始终领先乙，其种 数是卡特兰数
再一个卡特兰数的例子
饭后，姐姐洗碗，妹妹把姐姐洗过的碗一个一个放进碗橱摞成 一摞。
一共有
n
个不同的碗，洗前也是
摞成一摞的，也许因为小妹贪玩而使碗 拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起
的碗有多少种可能的方式？
答：得数是第
n
个卡特兰数
C
n
。
再一个卡特兰数的例子
一个汽车队在狭窄的路面上行驶，不得超车，
但可以 进入一个死胡同去加油，然后再插队行驶，
共有
n
辆汽车，问共有多少种不同的方式使 得车队开出城去？
答：得数是第
n
个卡特兰数
C
n
。
- 3 -
卡特兰数
求证：卡特兰数
C
n
是整数。
证明：
①
取整函数不等式：对任意实数
x
，
y
有
[x
＋< br>y]
≥
[x]
＋
[y]
。这里
[x]
表示不 大于实数
x
的最大整数。
解：由定义
x
≥
[x]
……
（
1
）
y
≥
[y]
……
（
2
）以上 两式相加，得：
x
＋
y
≥
[x]
＋
[y]
，
把上式再取 整，得：
[x
＋
y]
≥
[[x]
＋
[y]]
＝
[x]
＋
[y]
，即
[x
＋
y]
≥< br>[x]
＋
[y]
。
②
1000
！的末尾< br>0
的个数
249
个。
（现在有的小学奥数书上出现了
100< br>！末尾有几个零的题目：
24
个）
解：
1000
÷
5
＝
200
，
200
÷
5
＝
40
，
40
÷
5
＝
8
，
8
÷
5
＝
1
……
3
以上各商相加，即得
1000
！末尾
0
的个数＝
200
＋
40
＋
8
＋< br>1
＝
249
个。
③
n
！的质因数分解式中质因子
p
的幂次数：
…………
（
1
）
k
！的质因数分解式中质因子
p
的幂次数
…………
（
2
）
(n
－
k)!
的质因数分解式中质因子
p
的幂次数
…………
（
3
）
这里写成西格马求和式时使用 了无穷的形式，但是从某一确定项之后的每项都是
0
，为了统一，都写
成了
“ ∞”
形式。
④
组合数是整数
解：
⑤
卡特兰数是整数
⑥
卡特兰数是整数的另外一个证明
④
组合数是整数
- 4 -
⑤
卡特兰数是整数
⑥
卡特兰数是整数的另一个证明
- 5 -
凸六边形剖分成三角形的
14
种方法，是卡特兰数
C
4
从左下角
（0
，
0
）走到右上角
（
4
，
4
），只允许向上、向右走，但不允许穿过对角线的方法数是
14
种，
是卡特兰数C
4
- 6 -
1936
第
40
届匈牙利奥林匹克数学竞赛
第
1
题考了
Catalan
恒等式的证明。
1979
第
21
届国际数学奥林匹克
第
1
题考了一个卡特兰恒等式的应用的题目
- 7 -
- 8 -