1、组合数学钱 江计算数学与应用软件教研室Email: 北京邮电大学理学院序 11666年莱布尼兹所著 组合学论文 一书问世，这是组合数学的第一部专著。书中首次使用了 组合论 （ Combinatorics） 一词 。序 2组合数学就是按照一定的规则来安排一些离散个体的有关问题。其内容包括：1、计数与枚举2、容斥原理和鸽巢原理3、组合设计4、组合算法和组合优化5、图论序 3组合数学经常使用的方法并不高深复杂。最主要的方法是 计数时的合理分类 和 组合模型的转换。一个技巧是 从小规模的问题出发，找到规律，再推广到一般 。第一章 排列组合1.1 加法法则与乘法法则1.2 一一对应1.3 排列1.4 圆
2、周排列1.5 组合1.6 排列的生成算法1.7 组合的生成算法1.8 允许重复的组合与不相邻的组合1.9 组合意义的解释1.10 应用举例1.1 加法法则与乘法法则加法法则 设事件 A有 m种产生方式，事件件 B有 n种产生方式，则事件 A或 B之一有m+n种产生方式。若 |A| = m , |B| = n , AB = , 则|A B| = m + n 。集合论语言 ：基本假设：事件 A和事件 B是 无关 的两类。1.1 加法法则与乘法法则例 1 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18 + 10 = 28 人。例 2 北京每天直达上海的客车有 5 次，飞机有 3
3、 次，火车有 5 次， 则每天由北京直达上海的旅行方式有 5 + 3 + 5 = 13 种。乘法法则 设事件 A有 m种产生方式，事件 B有 n种产生方式则事件 A与 B有 m n种产生方式。若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则|A B| = m n 。1.1 加法法则与乘法法则集合论语言：1.1 加法法则与乘法法则例 3 某种字符串由两个字符组成，第一个字符可选自 a， b， c， d， e， 第二个字符可选自 1， 2， 3，则这种字符串共有 53 = 15 个。例 4 从 A到 B有三条道路，从 B到 C有两条道路，则从 A经 B到 C有 32=6 条道路。加法：得到事件通过 两种不同的方法 。乘法：得到事件通过 两个步骤 。1.1 加法法则与乘法法则例 5 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有 42 = 8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是 4 4 = 16， 而只有 4 3 = 12 种。
