Chap1-1排列组合.ppt

组合数学 序1 1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。 序2 序3 组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。 一个技巧是从小规模的问题出发，找到规律，再推广到一般。 第一章 排列组合 1.1 加法法则与乘法法则 1.1 加法法则与乘法法则 1.1 加法法则与乘法法则 1.1 加法法则与乘法法则 例5 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有4?2 = 8种着色方案。 1.1 加法法则与乘法法则 例6 (1)求小于10000的含1的正整数的个数; (2)求小于10000的含0的正整数的个数. 1.1 加法法则与乘法法则 1.1 加法法则与乘法法则 1.2 一一对应 “一一对应”概念是一个在计数中极为基本的概 念。一一对应既是单射又是满射。 1.2 一一对应 例1 在64名选手之间进行淘汰赛(即一场的比 赛结果，失败者退出比赛),最后产生一名冠军， 问要举行几场比赛？ 1.2 一一对应 例2 设凸n边形的任意三条对角线不共点， 求对角线在多边形内交点的个数。 1.3 排列 定义 从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的个数用P(n,r)表示。当r = n 时称为全排列。 1.3 排列 例1 由5种颜色的星状物，20种不同的花排列成如下图案：两边是星状物，中间是3朵花，问共有多少种这样的图案？ 1.3 排列 两边是星状物，从五种颜色的星状物中取两个的排列的排列数是 P(5,2)=20 1.3排列—举例 例2 A单位有7名代表，B单位有3位代表，排成 一列合影要求B单位的3人排在一起，问有多少种 不同的排列方案。 1.3排列—举例 于是我们只需要计算Si即可。 1.3排列—举例 S2=3(1+3+5+7)10+3(1+3+5+7)= 480+48=528 1.4 组合 定义 从 n 个不同元素中取 r 个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。 1.4 组合 1.4组合—举例 例1 有5本不同的日文书，7本不同的英文书， 10本不同的中文书。 1)取2本不同文字的书； 2)取2本相同文字的书； 3)任取两本书 1.4组合—举例 C(4,2)×C(7,3) C(4,2)×C(7,3)+C(4,3)×C(7,2)+C(4,4)×C(7,1) 3）C(10,5)+C(9,4)，或C(11,5)-C(9,3)， 1.5组合—举例 1.5组合—举例 1.5组合—举例 例4 假定有a1,a2,a3,a4,a5, a6, a7,a8这8位成员，两两配对分成4组，试问有多少种方案？ 1.5组合—举例 1.5组合—举例 例5 某广场有6个入口，每个入口每次只能通过一辆汽车，现有9辆车要开进广场，有多少种入场方案？ 1.5组合—举例 解1 标号可产生5!个14个元的全排列。 故若设x为所求方案，则 x ·5!=14! ∴x=14!/5!=726485760 1.5组合—举例 例6 一个凸n边形，它的任何3条对角线都不交于同一点，问它的所有对角线在凸n边形内部有多少个交点。 1.5圆周排列 1.5圆周排列 从n个中取r个的圆周排列的排列数为 1.5圆周排列--例子 例1 5颗红珠子，3颗蓝珠子装在圆板的四周，试问有多少种方案？若要求蓝色珠子不相邻，又有多少种排列方案？蓝色珠子在一起呢？ 1.5圆周排列--例子 解2：分成4组，第一组取法为C(8,2)，余下6人，第二组取法为C(6,2)，第三组取法为C(4,2)，剩下为第四组。但4组的顺序是重复的，因此答案为 C(8,2)×C(6,2)×C(4,2)/P(4,4)=105 解3：8人全排列有P(8,8)。分成4组，每组中2人交换是重复的，重复数为2×2×2×2，另外4组的顺序也是重复的，重复数为P(4,4)，因此答案为 P(8,8)/(2×2×2×2×P(4,4))=105 一个进站方案可以表示成：00011001010100 其中“0”表示车，“1”表示间隔，其中“0”是 不同元，“1”是相同元。给“1”这6个入口只用5 个间隔。任意进站方案可表示成上面14个 元素的一个排列。 解2 在14个元的排列中先确定“1”的位置，有C(14,5)种选择，再确定人的位置，有9！种