组合数学概念简介.pptx

1 combinatorics 马昱春 第一章 排列组合 说说数数这件事 2 无重复，无遗漏无重复，无遗漏 3 第一章排列组合 1.1 加法法则与乘法法则 分类计数和分步计数 从甲地到乙地，可以乘火车，也可以乘汽车 ，一天中，火车有3班，汽车有2班那么一 天中，乘坐这些交通工具从甲地到乙地共有 多少种不同的走法？ 解答： 325 种不同的走法 从甲地到乙地，要从甲地选乘火车到丙地，再 于次日从丙地乘汽车到乙地一天中，火车有 3班，汽车有2班那么两天中，从甲地到乙地 共有多少种不同的走法？ 解答：共有 326 种不同的走法 4 1.1 加法法则与乘法法则 加法法则 The Sum Rule设事件A有m种产生方 式，事件B有n种产生方式，则事件A或B之一 有m+n种产生方式。 集合论语言： 若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。 例 某班选修企业管理的有 18 人，不选 的有 10 人，则该班共有 18 + 10 = 28 人。 5 1.1 加法法则与乘法法则 乘法法则 The Product Rule 设事件A有m种 产生方式，事件B有n种产生方式，则事件A与 B有 m n种产生方式。 集合论语言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。 例 某种字符串由两个字符组成，第一个字符 可选自a，b，c，d，e，第二个字符可选自1 ，2，3，则这种字符串共有5 3 = 15 个。 6 1.1 加法法则与乘法法则 例 某种样式的运动服的着色由底色和装饰 条纹的颜色配成。底色可选红、蓝、橙、黄 ，条纹色可选黑、白，则共有42 = 8种着 色方案。 若此例改成底色和条纹都用红、蓝、橙、黄 四种颜色的话，则，方案数就不是4 4 = 16， 而只有 4 3 = 12 种。 在乘法法则中要注意事件 A 和 事件 B 的相 互独立性。 7 1.1 加法法则与乘法法则 例 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数 1)小于10000的不含1的正整数可看做4位数, 但0000除外. 故有999916560个. 含1的有：99996560=3439个 另: 全部4位数有104 个,不含1的四位数有94 个, 含1的4位数为两个的差: 104 94 = 3439个 8 2)求小于10000的含0的正整数的个数 “含0”和“含1”是否可以直接套用？ 0019含1但不含0。 在组合的习题中有许多类似的隐含的 规定，要特别留神。 不含0的1位数有9个，2位数有92个，3位 数有93个，4位数有94个 不含0小于10000的正整数有 9 + 92 + 93 + 94 =(951)/(91)=7380个 含0小于10000的正整数有 99997380=2619个 9 1.2排列与组合 定义 排列 Permutation从n个不同的元素中， 取r个不重复的元素，按次序排列，称为从n个 中取r个的无重排列。排列的个数用P(n,r)表示 ，或者 。当r=n时称为全排列。一般不说可 重即无重。 定义 组合 Combination从n个不同元素中取r 个不重复的元素组成一个子集，而不考虑其元 素的顺序，称为从n个中取r个的无重组合。 组合的个数用C(n,r)表示或者 10 1.2排列与组合 从n个中取r个的排列的典型例子是从n个不 同的球中,取出r个,放入r个不同的盒子里,每 盒1个。 第1个盒子有n种选择，第2个有n-1种 选择，第r个有n-r+1种选择。 故有 P(n,r)=n(n-1)(n-r+1) = 有时也用nr记n(n-1)(n-r+1) 全排列：P(n,n) = n! 11 1.2排列与组合 若球不同，盒子相同，则是从n个中取r个的组 合的模型。 若放入盒子后再将盒子标号区别，则又回到排 列模型。每一个组合可有r!个标号方案。 故有 C(n,r)r!=P(n,r)= C(n,r)=P(n,r)/r!=nr/r!= = 12 排列组合问题的来源 排列组合问题，最早见于我国的易经一书 所谓“四象”就是每次取两个爻(yo )的排列，“八卦”是每次取三个 爻的排列 在汉代数学家徐岳的数术记遗（公元2世纪）中，也曾 记载有与占卜有关的“八卦算”，即把卦按不同的方法在八 个方位中排列起来 它与“八个人围一张圆桌而坐，问有多少种不同坐法”这一典型的排 列问题类似11世纪时，邵雍还进一步研究了六十四卦的排列问题 唐朝僧人一行曾经研究过围棋布局的总数问题古代的棋 盘共有17路，289个点，后来发展到19路361个点一行曾 计算过一切可能摆出的棋局总数 17世纪，北宋时期沈括在梦溪笔谈中，进一步讨论了 围棋布局总数问题他利用一些排列、组合的办法对一行 的计算作了分析沈括指出，当361个棋子全用上时，棋局 总数达到1000052 的数量级 13 1.2排列与组合 例 有5本不同的日文书，7本不同的英 文书，10本不同的中文书。 1)取2本不同文字的书； 57+510+710=155; 2)取2本相同文字的书； C(5,2)+C(7,2)+C(10,2) =10+21+45=76; 3)任取两本书 155+76=231= C(5+7+10,2) 14 1.2排列与组合 多重全排列： 2个a, 3个b，4个c，其多重全排列记为 加上下标以区别 a1a2b1b2b3c1c2c3c4 a下标排列有2!，b下标排列有3!，c下标排 列有4！ 15 1.2排列与组合 求r1个1，r2个2，rt个t的排列数，设 r1+r2+rt=n,设此排列数为P(n;r1,r2,rt) 对1，2，t分别加下标，得到 P(n;r1,r2,rt)r1!r2!rt! = n! P(n;r1,r2,rt) = 多项式展开 = 16 1.2排列与组合 圆排列：从n个中取r个的圆排列的排列数为 P(n,r)/r , 2rn 以4个元素为例 1