组合数学第一讲课件.ppt

前言 1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。 组合数学研究的中心问题是按一定规则将一些事物安排成各式各样模式的问题。包括安排的存在问题、计数问题、构造问题以及给出了优化标准后如何求出最优安排问题。 前言 组合数学经常使用的方法并不高深复杂。 最主要的方法是计数时的合理分类和组合模型的转换。 但是，要学好组合数学并非易事，既需要 一定的数学修养，也要进行相当的训练。 第一章 排列与组合 1.1 加法法则与乘法法则. [ 加法法则 ] 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 1.2排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 定义：从n个不同元素中允许重复地取r个元素作排列，称为n元可重r-排列，其排列数为nr 例：由数字1，2，3可组成多少个两位数？并写出这些两位数。 解：这是三元可重2-排列问题。其排列数为32=9。这些两位数为11,12,13,21,22,23,31,32,33。 第一章 排列与组合 定义：从n 个不同元素中取r个元素围成一圈，称为从n个不同元中取r个元的圆排列，其排列数记为K(n,r)。我们有： 第一章 排列与组合 例：4个女生和4个男生围圆桌相间而坐，试问有多少种不同的入座方式？ 解：先让女生入座，这是一个4的圆排列问题。有K（4，4）=4！/4=3！。 例:由四种颜色的珠子各一颗，可以做成多少种不同的项链？ 解：注意项链可以翻转。 第一章 排列与组合 定义：从n个不同元中允许重复地取r个元的组合，称为n元可重r-组合，其组合数记为F(n,r)。 用集合描述为：重集{∞·a1, ∞·a2 ,…∞·an}的r-组合数为F(n,r)。 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 1.3模型转换 第一章 排列与组合 例 第一章 排列与组合 无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。 则(0,0)→(m,n)的每一条路径可表示为m 个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。 第一章 排列与组合 设所求方案数为P(m+n；m，n) 则P(m+n；m，n)·m!·n!=(m+n)! 故P(m+n;m,n)= ——— = ( ) =( )=C(m+n,m) 第一章 排列与组合 例：在上例的基础上若设mn，求(0,1)点到(m,n)点不接触对角线x=y的格路的数目(“接触”包括“穿过”) 从(0,1)点到(m,n)点的格路，有的接触x=y，有的不接触。 对每一条接触x=y的格路，做(0,1)点到第一个接触点部分关于x=y的对称格路，这样得到一条从(1,0)到(m,n)的格路。 第一章 排列与组合 容易看出从(0,1)到(m,n)接触x=y的格路与 (1,0)到(m,n)的格路(必穿过x=y)一一对应 第一章 排列与组合 若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得x－y=1，　(0,0)关于x－y=1的对称点为(1,-1). 第一章 排列与组合 例 CnH2n+2是碳氢化合物,随着n的不同有下列不同的枝链： 第一章 排列与组合 第一章 排列与组合 例 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？ 解 一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。 第一章 排列与组合 1.4全排列的生成算法 第一章 排列与组合 1.4.1全排列的生成--序数法 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 第一章 排列与组合 1.6若干等式及其组合意义 第一章 排列与组合 2. C(n,r)=C(n-1,r)+C(n-1,r-1) (1.6.2) ※从[1,n]取a1,a2,…,ar.设1≤a1＜a2＜…＜ar≤n,对取法分类： a1=1,有C(n-1,r-1)