信息科学与技术正在对人类社会的发展产生难以估量的深远影响，并将成为新世纪的一个标志。作为人类总体智慧的结晶，电脑已经成为一种新的现代文化。“计算机的普及要从娃娃做起”已经成为“科教兴国”的一项重要内容。

一个国家、一个民族要想不落伍，要想跻身于世界先进民族之林，关键在于拥有高素质的人才；综合国力的竞争，说到底也是人才的竞争。电子计算机是现代科学与技术的基础和核心，它的飞速发展，把社会生产力水平提到前所未有的高度，人类进入了信息时代。电脑对人类社会的发展所起的巨大作用，特别是对人类智能的发展所起的促进作用，已为人们普遍认识到。计算跟语言一样是人类社会每时每刻都不可缺少的。现在，人类已经拥有了帮助自己进行复杂计算与思维的工具，电子计算机起到了人脑延伸的作用。以往历史上的技术革命，只能起到创造和改进工具，用机器代替人的体力的作用；而计算机则是把人从重复性的或有固定程式的脑力劳动中解放出来，使自己的智能获得空前的发展。作为“人类通用智力工具”的计算机在开发人类智能方面所起的无与伦比的作用不容忽视。这也就是计算机与基础教育相结合，能够成为当今世界的大趋势的一个原因。从信息社会要求人才具备的科学素养看，数学、物理学、化学、生命科学和信息科学是五大支柱，这正是联合国教科文组织倡导举行五项国际学科奥林匹克竞赛的内容。

国际信息学奥林匹克(International Olympiad in Informatics,简称IOI)始于1989年，到2001年已成功地举办了13届。这是一种智力与应用计算机能力的大赛。从益智的角度看，是用电脑帮助开发人脑，重在提高思维能力，培养创新意识。在中国队的训练中强调德智体美全面发展；心态上自立、自尊、自信、自强，要怀着中华民族的自豪感和自信心去参赛；这种心态是学习、训练和取胜的重要条件。13届比赛，中国队每届都取得了名列前茅的好成绩，51人次参赛，夺得51块奖牌，其中金牌26块、银牌14块、铜牌11块。特别是IOI’95(荷兰)突破了前6届比赛女孩与金奖无缘的纪录，两名中国女选手荣登金牌领奖台。在IOI’96(匈牙利)上中国队又实现了全金的突破，四名选手，每人获得一块金牌。

从大局看，竞赛不是目的，是推动普及的手段，我们的目的只有一个：科教兴国。竞赛活动带有因材施教、因材施测的特点。普及是有层次的，与学科竞赛有关的普及活动，对青少年而言属于比较高的层次，当然就有相当的难度。我们编写的这套竞赛指导丛书，涉及程序设计语言、常用算法、组合数学、图论、人工智能搜索等的基本知识和基本方法。这些理论知识往往都是通过竞赛当中的一些实例来讲解的，重点放在解题思路上，书中有许多题目比较新颖，很难去套固定算法或固定模式，这中间有些招数是选手们想出来的。从中可以看出信息学奥林匹克要求创新，鼓励创新。当然，书中给出的解法，对青少年读者而言，我们希望仅仅起到抛砖引玉的作用，并且热切盼望引出更多的“玉”来。作为老师，我和王建德都这样想，“精心育桃李，热望青胜蓝”就是我们编写这套丛书的初衷。

国际信息学奥林匹克中国队总教练

清华大学计算机系教授博士生导师

吴文虎

2002年8月

第一章导论1

1.1组合数学的研究对象1

1.2组合问题的基本解题方法2

1.3回溯法的讨论6

习题一17

第二章从鸽笼原理到Ramsey理论20

2.1鸽笼原理20

2.2Ramsey问题和Ramsey数22

习题二25

第三章排列组合及其计数问题26

3.1两个基本计数原理26

3.2排列27

3.3组合31

3.4排列组合问题的一个实验程序38

习题三44

第四章容斥原理46

4.1容斥原理的两种形式46

4.2容斥原理的一般形式49

4.3容斥原理的应用52

习题四68

第五章母函数70

5.1母函数的引出70

5.2普通母函数71

5.3指数母函数79

习题五84

第六章递归关系86

6.1递归关系的定义和建立86

6.2Fibonacci数88

6.3Catalan数91

6.4第二类Stirling数98

习题六102

第七章Pólya原理105

7.1等价关系、群、置换群105

7.2Burnside引理112

7.3Pólya定理117

习题七125

第八章组合设计127

8.1问题的提出127

8.2魔方与魔和129

8.3拉丁方的构造131

8.4构造奇数阶正交拉丁方137

习题八142

第九章线性规划143

9.1线性规划及其数学模型143

9.2单纯形法148

9.3对偶问题157

9.4整数规划165

9.5指派问题174

习题九182

第十章动态规划184

10.1动态规划问题的数学描述184

10.2动态规划问题的最优化原理186

10.3动态规划应用举例189

习题十194