1、ACM暑期集训之组合数学刘昆2009年 8月主要研究内容n 依据一定的规则来安排某些事物的有关数学问题，这些问题包括 4个方面：n 这种安排是否存在，即存在性问题；n 如果符合要求的安排是存在的，那么这样的安排又有多少，即计数问题（包括枚举的验证与效率）；n 怎样构造这种安排，即算法构造问题；n 如果给出了最优化标准，又怎样得到最优安排，即最优化问题。组合问题的基本解题方法n 从组合学基本概念、基本原理出发的所谓常规方法n 通常与问题所涉及的组合数学概念无关的非常规方法n 数学归纳法n 一一对应技术（ 8个 “车 ”问题）n 殊途同归方法（ C(n,0)+ C(n,n)=2n）n 数论方法（
2、n位客人握手）n 回溯法内容提要n 排列组合n 鸽巢原理n 递推关系与生成函数n 二分图的最大匹配n Polya计数原理的相关数学基础排列组合两个基本原则1、加法原则如果完成一件事情有两种方案，而第一个方案有 m种方法，第二个方案有 n中方法，则完成该事情共有 m+n种方法。2、乘法原则如果完成一件事情需要两个步骤，第一步有 m中方法，第二步又有 n种方法，则完成该事情共有 m*n种方法排列组合的几个基本结论n 相异元素不允许重复的排列数和组合数 ：n 不尽相异元素的全排列n!(n-r)!P(n,r)= C(n,r)=n!(n-r)!r! RP(n,n) = n!n1!n2!.nt!排列组合的
3、几个基本结论n 相异元素不允许重复的圆排列n 相异元素允许重复的组合数CP(n,n)=P(n,n)n集合描述：设 S=e1, e2, en,，从 S中允许重复地取出 r个元素，称为 r可重组合RC(,r)=C(n+r-1,r) = (n+r-1)!r!(n-1)! 圆排列n 6位女士和 6位先生围着一张圆桌聚餐，要求安排女士和先生交替就座。问：有多少可能的安排方案。n 解 . 由于要求安排女士和先生交替就座，因此可以先安排六位女士坐下，两位之间留出一个空位，然后再安排先生就座。安排六位女士坐下（圆排列）的方案数是n （种）圆排列（续）n 由于已经有女士在位，安排先生在六个空位上就座时，就不再是圆排列了，因为原先被看成相同圆排列的六位先生的就座方式所产生的全体人员的圆排列是不同的。故安排先生在六个空位上就座的方案数是n 6！ 720n 于是我们得到满足要求安排方案共计有
