组合数学1幻灯片.ppt

ACM暑期集训之组合数学 刘昆 2009年8月 主要研究内容 依据一定的规则来安排某些事物的有关数学问题，这些问题包括4个方面： 这种安排是否存在，即存在性问题； 如果符合要求的安排是存在的，那么这样的安排又有多少，即计数问题（包括枚举的验证与效率）； 怎样构造这种安排，即算法构造问题； 如果给出了最优化标准，又怎样得到最优安排，即最优化问题。 组合问题的基本解题方法 从组合学基本概念、基本原理出发的所谓常规方法 通常与问题所涉及的组合数学概念无关的非常规方法 数学归纳法 一一对应技术（8个“车”问题） 殊途同归方法（C(n,0)+…C(n,n)=2^n） 数论方法（n位客人握手） 回溯法 内容提要 排列组合 鸽巢原理 递推关系与生成函数 二分图的最大匹配 Polya计数原理的相关数学基础 排列组合 两个基本原则 1、加法原则 如果完成一件事情有两种方案，而第一个方案有m种方法，第二个方案有n中方法，则完成该事情共有m+n种方法。 2、乘法原则 如果完成一件事情需要两个步骤，第一步有m中方法，第二步又有n种方法，则完成该事情共有m*n种方法 排列组合的几个基本结论 相异元素不允许重复的排列数和组合数： 不尽相异元素的全排列 排列组合的几个基本结论 相异元素不允许重复的圆排列 相异元素允许重复的组合数 圆排列 6位女士和6位先生围着一张圆桌聚餐，要求安排女士和先生交替就座。问：有多少可能的安排方案。 解. 由于要求安排女士和先生交替就座，因此可以先安排六位女士坐下，两位之间留出一个空位，然后再安排先生就座。安排六位女士坐下（圆排列）的方案数是 （种） 圆排列（续） 由于已经有女士在位，安排先生在六个空位上就座时，就不再是圆排列了，因为原先被看成相同圆排列的六位先生的就座方式所产生的全体人员的圆排列是不同的。故安排先生在六个空位上就座的方案数是 6！＝720 于是我们得到满足要求安排方案共计有 电子锁 某机要部门安装了电子锁。M工作人员每人发一张磁卡，卡上有开锁的密码特征，为了确保安全，规定至少有N人同时使用各自的磁卡才能将锁打开。 现在需要计算一下，电子锁上至少要有多少种特征，每个人的磁卡上至少要有多少特征 电子锁（续） 先做一个简单的假设：M=7，N=4。 电子锁（续） 电子锁（续） 电子锁（续） 电子锁（续） zju1976 Path On a Grid Path On a Grid（续） 排列组合数的一般计算方法 代码 全排列生成算法 如果将整数n从『1，2。。。，n』的一个排列中删除，那么结果则是『1，2。。。，n-1』的一个排列。 给定一个『1，2。。。，n-1』的排列，只要将n插入到其中的n个间隔（含头尾） 算法描述： 从『1』开始，将2插入排列中得『1，2』的排列，以此类推，直至得到『1，2。。。，n』的排列 『1，2，3』全排列生成算法示例 1 2 2 1 ＝＝＝＝＝＝＝＝＝ 1 2 3 1 3 2 3 1 2 －－－－－－－－－－ 2 1 3 2 3 1 3 2 1 STL中生成排列数的函数 #include algorithm int A[] = {2, 3, 4, 5, 6, 1}; prev_permutation(A, A+6); 结果：2　3　4　5　1　6 int A[] = {2, 3, 4, 5, 6, 1}; next_permutation(A, A+6); 结果：2　3　4　6　1　5 组合的生成算法 组合的生成算法（续） Code: 组合的生成算法（续） 相关练习 NKOJ 1038 NKOJ 1108 鸽巢原理 递归关系和生成函数 母函数 称重问题 假设你现有质量分别为1克、2克和3克的砝码各一枚，问只用这些砝码各一次你能称出哪几种质量？而对每种质量确定的物体又有多少种不同的称量方案？ 命题1 若有质量为1，2，3，…，n克的砝码各1枚，则称重情况的数学模型为： (1+x)(1+x^2)…(1+x^n)，能表示方案总数，但是不能表示具体的称量方案 (1+x1)(1+x2^2)…(1+xn^n)，既能表示称量方案总数，又能表示具体的称量方案。 命题2 若有质量为k1，k2，k3，…，kn克的砝码各1枚，则称重情况的数学模型为： (1+x^k1)(1+x^k2)…(1+x^kn)，能表示方案总数，但是不能表示具体的称量方案 (1+x1^k1)(1+x2^k2)…(1+xn^kn)，既能表示称量方案