1、组合数学 陈宁宇书 名 :程序 设计 中的 组 合数学(ACM、 ICPC国 际 大学生程序 设计竞赛 ) 作者 :吴文虎 /孙贺 出版社 :清 华 大学出版社 一：排列组合基本概念和例题1.基本概念：略2.例题（重点是重排列和重组合问题）（ 1）在 10009999之间具有多少不同数字的奇数？（ 2） 1， 1， 1， 3， 8可以构造出多少个不同的五位数？（ 3） 10个人要围坐一圆桌，其中有两人不愿意彼此挨着就坐，共有多少循环座位排放方法？（ 4） 2a， 2b， 4c排列方法数？插入幻方介绍（ 5） 2 a， 2b ， 4c 的 3组合数？（ 6）平面上给定 25个点，问最多可以确定多
2、少条直线？多少个三角形？（任何三点不共线）（ 7）在单词 MISSISSIPPI中的字母排列数是多少？（ 8）在 88 的棋盘上对于 8个彼此不同的非攻击型的车有多少可能的放法？二： “方程的解 ”问题 方程的解问题实际上是多重集的组合问题？ 我们同样通过例题由浅入深来看 一家面包房生产 8种炸面包圈。如果一盒内装有一打炸面包圈，那么你能够买到多少种不同的盒装面包圈（要求每一盒必须包含每一种炸面包圈）？做完先看 3和 42. 一家面包房生产 8种炸面包圈。如果一盒内装有一打炸面包圈，那么你能够买到多少种不同的盒装面包圈？公式 （ r-1 k-1） （ r-1+k k-1） 令 S是具有四种元素
3、 a,b,c,d的多重集（ a,b,c,d都有无穷多个）。问 S的使得 4种元素都至少出现一次的 10组合的数目是多少？即方程 x1+x2+x3+x4=10的正整数解的个数？4. 令 S是具有四种元素 a,b,c,d的多重集（a,b,c,d都有无穷多个）。问 S的 10组合的数目是多少？即方程 x1+x2+x3+x4=10的非负整数解的个数？ 方程 x1+x2+x3+x4=20的整数解的个数？其中 x1 =3, x2 =1, x3 =0, x4=56. 一位秘书在距离家以东 9个街区，以北7个街区的一座大楼里工作。每天他都要步行 16个街区去上班，对他来说有多少不同的线路？（如下图）线路图表： 七桥问题18世纪在哥尼斯堡城 (今俄罗斯加里宁格勒)的普莱格尔河上有 7座桥，将河中的两个岛和河岸连结，如图所示。城中的居民经常沿河过桥散步，于是提出了一个问题：能否一次走遍 7座桥，而每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。
