《第四组合数学》PPT课件.ppt

组合数学 河北工业大学计算机学院 李建伟 n组合数学是一门研究离散对象的科学，是计算机 的核心课程之一，在众多的计算机系统软件和信 息安全软件中都要用到本课程的内容。它是近代 密码学和算法的理论基础，在计算机科学的理论 体系中占有极其重要的位置。对计算机专业本科 的学生进行组合数学教学和训练，为进一步学习 计算机算法（组合算法）打下坚实基础。 n组合数学是为学习”算法与复杂性分析”作理论的 准备。 本课程的学习目的 n通过本课程的学习，理解组合理论的基 本概念，掌握组合理论的基本方法和技 巧，了解一些简单算法，为深入研究、 应用组合数学打好基础。 前言 组合数学是一个古老而又年 轻的数学分支。 据传说，大禹在4000多年前 就观察到神龟背上的幻方. 前言 幻方可以 看作是一个3 阶方阵，其 元素是1到9 的正整数， 每行、每列 以及两条对 角线的和都 是15。 5 1 9 37 24 86 前言 贾宪 北宋数学家（约11世纪） 著有 黄帝九章细草、算法斅古集斅 音“笑 （“古算法导引”）都已失传。杨辉著详解 九章算法（1261年）中曾引贾宪的“开方 作法本源”图（即指数为正整数的二项式展开 系数表，现称“杨辉三角形”）和“增乘开方法 ”（求高次幂的正根法）。前者比帕斯卡三角 形早600年，后者比霍纳（William Geoge Horner，17861837）的方法（1819年 ）早770年。 前言 1666年莱布尼兹所著组合 学论文一书问世，这是组合数学 的第一部专著。书中首次使用了组 合论（Combinatorics）一词。 前言 组合数学的蓬勃发展则是在计 算机问世和普遍应用之后。由于组 合数学涉及面广，内容庞杂，并且 仍在很快地发展着，因而还没有一 个统一而有效的理论体系。这与数 学分析形成了对照。 前言 n本学期主要讲组合分析（计数和枚举） 以及组合优化的一部分（线性规划的单 纯形解法）。 n组合分析是组合算法的基础。 前言 组合数学经常使用的方法并不高 深复杂。最主要的方法是计数时的合 理分类和组合模型的转换。 但是，要学好组合数学并非易事 ，既需要一定的数学修养，也要进行 相当的训练。 第一章排列组合 1.1 加法法则与乘法法则 加法法则 设事件A有m种产生方式， 事件B有n种产生方式，则事件A或B之一 有m+n种产生方式。 集合论语言： 若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。 1.1 加法法则与乘法法则 例 某班选修企业管理的有 18 人，不选 的有 10 人，则该班共有 18 + 10 = 28 人。 例 北京每天直达上海的客车有 5 次， 客机有 3 次， 则每天由北京直达上海的旅 行方式有 5 + 3 = 8 种。 1.1 加法法则与乘法法则 乘法法则 设事件A有m种产生式，事 件B有n种产生方式，则事件A与B有 m n 种产生方式。 集合论语言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。 1.1 加法法则与乘法法则 例 某种字符串由两个字符组成，第一个 字符可选自a，b，c，d，e，第二个字符 可选自1，2，3，则这种字符串共有5 3 = 15 个。 例 从A到B有三条道路，从B到C有两条 道路，则从A经B到C有32=6 条道路。 1.1 加法法则与乘法法则 n例 某种样式的运动服的着色由底色和 装饰条纹的颜色配成。底色可选红、蓝 、橙、黄，条纹色可选黑、白，则共有 42 = 8种着色方案。 n若此例改成底色和条纹都用红、蓝、橙 、黄四种颜色的话，则，方案数就不是 4 4 = 16， 而只有 4 3 = 12 种。 n在乘法法则中要注意事件 A 和 事件 B 的相互独立性。 1.1 加法法则与乘法法则 例 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数 1)小于10000的不含1的正整数可看做4位数, 但0000除外。 故有999916560个. 含1的有：99996560=3439个 另: 全部4位数有10 个,不含1的四位数有9 个, 含1的4位数为两个的差: 10 9 = 3439个 4 4 4 4 2)“含0”和“含1”不可直接套用。0019 含1但不含0。 在组合的习题中有许多类似的隐含的 规定，要特别留神。 不含0的1位数有9个，2位数有9 个， 3位数有9 个，4位数有9 个 不含0小于10000的正整数有 9+9 +9 +9 =(9 1)/(91)=7380个 含0小于10000的正整数有 99997380=2619个 2 34 2345 排列 定义 从n个不同的元素中，取r个不重 复的元素，按次序排列，称为从n个中取 r个的无重排列。排列的全体组成的集合 用 P(n,r)表示。排列的个数用P(n,r)表 示。当r=n时称为全排列。一般不说可重 即无重。可重排列的相应记号为 - P(n,r),P(n,r)。 排列 n排列研究事物的有序安排或有序选择数。 n例如：125和251虽然都由1，2，5三个数 字构成，但这是两个不同的排列。 n分为： n线排列（简单排列，我们高中所学的排列） n圆排列（排列的首尾元素相连） n重排列（排列中的元素可以重复） 组合 定义从n个不同元素中取r个不重复的元素 组成一个子集，而不考虑其元素的顺序， 称为从n个中取r个的无重组合。 组合的全体组成的集合用C(n,r)表示，组 合的个数用C(n,r)表示，对应于可重组合 - 有记号C(n,r),C(n,r)。 组合 n组合研究事物的无序安排或无序选择数 。 n例如：125和251都由1，2，5三个数 字构成，被看成是同一个组合。 1.1排列与组合 从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) 排列计数定理 nP(n,r)=n(n- 1)(n-r+1) = n! (n-r)! 1.1排列与组合 若球不同，盒子相同，则是从n个中取r个 的组合的模型。若放入盒子后再将盒子标 号区别，则又回到排列模型。每一个组合 可有r!个标号方案。 故有 C(n,r)r!=P(n,r), C(n,r)=P(n,r)/r!=nr/r!=( )= 易见 P(n,r)=n n r r n! r!(n-r)! 排列与组合 例 有5本不同的日文书，7本不同 的英文书，10本不同的中文书。 1)取2本不同文字的书； 2)取2本相同文字的书； 3)任取两本书 排列与组合 5+7+10 2 解 1) 57+510+710=155; 2) C(5,2)+C(7,2)+C(10,2) =10+21+45=76; 3) 155+76=231=( ) 排列与组合 n从n个中取r个的圆排列的排列数为 P(n,r)/r , 2rn n以4个元素为例 1 2 4 3 1234 1 2 4 3 2341 1 2 4 3 3412 1 2 4 3 4123 排列与组合 n从n个中取r个的项链排列的排列数为 P(n,r)/2r, 3rn n项链排列就是说排列的方法和项链一样,在圆 排列的基础上，正面向上和反面向上两种方 式放置各个数是同一个排列。 n例 下面两种方式实际上表示的都是3个元素 的同一种排列。 1 1 2 3 3 2 排列与组合 例 从1,300中取3个不同的数，使这 3个数的和能被3整除，有多少种方案？ 解 将1,300分成3类： A=i|i1(mod 3)=1,4,7,298, B=i|i2(mod 3)=2,5,8,299, C=i|i3(mod 3)=3,6,9,300. 要满足条件，有四种解法： 1)3个数同属于A; 2)3个数同属于B 3)3个数同属于C; 4)A,B,C各取一数。 故共有3C(100,3)+1003=485100+1000000=1485100 1.2一一对应 n“一一对应”概念是一个在计数中极为基本的 概念。一一对应既是单射又是满射。 n如我们说A集合有n个元素 |A|=n，无非是 建立了将A中元与1,n元一一对应的关系。 n在组合计数时往往借助于一一对应实现模型 转换。 n比如要对A集合计数，但直接计数有困难， 于是可设法构造一易于计数的B，使得A与B 一一对应。 1.2模型转换 n例 简单格路问题 |(0,0)(m,n)|=( ) 从 (0,0)点出发沿x轴或y轴的正方向每步 走一个单位，最终走到(m,n)点，有多少 条路径？ m+n m y (m,n) . . . 0 . . . x 1.2 模型转换 n无论怎样走法，在x方向上总共走m步， 在y方向上总共走n步。若用一个x表示x 方向上的一步，一个字母y表示y方向上 的一步。 n则(0,0)(m,n)的每一条路径可表示为 m 个x与n个y的一个有重排列。将每一 个有重排列的x与y分别编号，可得m!n! 个m+n元的无重全排列。 有重排列的计算方法 n求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! nP(n；r1,r2,rt)= =( ) n! r1!r2!rt! n r1 r2 rt 1.4模型转换 n设所求方案数为p(m+n；m，n) n则P(m+n；m，n)m!n!=(m+n)! n故P(m+n;m,n)= = ( ) =( ) =C(m+n,m) n设ca,db,则由(a,b)到(c,d)的简单格路数 为|(a,b)(c,d)|=( ) (m+n)! m+n m+n m!n! m n (c-a)+(d-b) c-a (c,d) (a,b) 1.2模型转换 n例 在上例的基础上若设m2 2 41 1 在后缀7521中找出比4大的数7 5找出其中比4大的最小数 5 5 4 、5 对换 8396 7 215 4 后缀变为7421 将此后缀翻转 12 4 7 接上前缀83965得到839651247 即839647521的下一个。 例 在后边找出比4大的最小的数和4交换。 即5和4交换，然后把1，2，4，7按递增排序。 从右边开始查找，找出比右边数字小的第一个数4 1.6.2字典序法 把前面的例子一般化后为，设P是1,n的一个全排列： P=P1P2Pn=P1P2Pi-1PiPi+1Pj-1PjPj+1Pn (a)i=maxj|Pj-11,有C(n-1,r)种方案 n共有C(n-1,r)+C(n-1,r-1)中方案，故 C(n,r)=C(n-1,r)+C(n-1,r-1) 举例 n例如1，2，3，4，5取3各组合得： 123，124，125，134，135，145，234， 235，245，345 （即C(5,3)=10个） 其中： 123，124，125，134，135，145可 以看成是由2，3，4，5取两个组合然后加上1 得到的（即C(4,2)=6个） ，而234，235， 245，345 可以看成是由2，3，4，5四个元 素中取三个元素得到的。（即C(4,3)=4个） nC(5,3)= C(4,2)+C(4,3) 1.9若干等式及其组合意义 nC(m+n,m)=C(m+n-1,m)+C(m+n-1,m- 1) n(0,0)(m,n) =(0,0)(m,n-1)(0,0)(m- 1,n) 组合意义：从（0,0）点到（m,n）的路 径数=（0,0）点到（m,n-1）的路径数 + （0,0）点到（m-1,n）的路径数 1.9若干等式及其组合意义 （4） ( )+( )+( )+( )=( ) 证明方法1 从1,n+r+1取a1a2ar-1ar， 设a1a2ar 可按是否含有ai的分类： ai=1,2,3,r. 不含a1,则a2ar取自2,n+r+1 有( )种取 法 n n+1 n+2 n+r n+r+1 0 1 2 r r n+r r 也可看做按含1不含1，含2不含2, 含r不含r的不断分类，也可以得到式（4） 含有a1，但不包含 a2 ，相当于从除去元素a1， a2 后的n+r-1个元素3,n+r+1中取r-1个元素 的组合，然后再加上元素a1而成。即( ) 有a1, a2 ar-1无ar, 第r个取自r+1,n+r+1 有( )种取法 n+1 1 由 a1, a2ar组成，有( )=1种取法 n 0 n+r-1 r-1 1.9若干等式及其组合意义 n方法2从(0,0)到(n+1,r)的路径数,任何一条路径 过且仅过一条带箭头的边,而过这些边的路径有( 从下到上) ( ),( ),( ) n有.( )+( )+( )+( )=( ) n n+1 n+r 0 1 r n n+1 n+2 n+r n+r+1 0 1 2 r r r (n+1,r) . . . (0,0) n n+1 1.9若干等式及其组合意义 方法3 可重组合（可重组合定理） 1,n+2的C(n+2,r)模型 ( ) 不含1,含1个1,含2个1,含r-1个1,含r个1 ( ), ( ), ( ), ( ) n+r+1 r n+r n+r-1 n+r-2 n r r-1 r-2 0 举例 n从1，2，3中取4个做允许重复的组合 令a1=1,则有 不出现1的有：2222，2223，2233，2333，3333 出现1个1的有：1222，1223，1233，1333 出现2个1的有：1122，1123，1133， 出现3个1的有：1112，1113 出现4个1的有：1111 等式（4）的另一种表达形式 n ( )+( )+( )+( )=( ) n n+1 n+2 n+r n+r+1 n n n n n 作业：仿照等式（4）的证明，分三种 方法证明该等式或说明该等式意义。 1.9若干等式及其组合意义 (5) ( )( )=( )( ) 选政治局,再选常委,n个中央委员选出L 名政治局委员,再从其中选出r名常委。 选常委,再选非常委的政治局委员。 两种选法都无遗漏,无重复地给出可能的 方案，即n个中央委员中有几种政治局 委员和政治局常委的组合，应该相等。 n L n n-r L r r L-r 1.9若干等式及其组合意义 nC(m+n,2)-C(m,2)-C(n,2)=mn m个男生和n个女生，一男一女的组合为 mn中方案 等式左端为从m+n个人中取2个组合， 减去两个男生的组合和两个女生的组合 ，余下的为一男一女的组合。 1.9若干等式及其组合意义 n(7) ( )+( )+( )=2 , m0 n证1(x+y) =( )x y ,令x=y=1,得(6) n组合证1 1,m的所有状态.每一元素都可取 k1,m或不取k.这样有2 个方案.左端说明所 有状态可分解为m个元素中分别取0个，1个， ，m个组合的总和。 n组合证2 从(0,0)走m步，有2 种走法,每步两种走法，都 落在直线x+y=m上,而到(m,0),(m-1,1),(m- 2,2),(2,m-2),(1,m-1),(0,m)各点的 走法各有( ),( ),( ),( ),( ),( )种 m m m m 0 1 m m k m-k m m k k=0 m m m m m m m m 0 1 2 m-2 m-1 m 1.9若干等式及其组合意义 n(8) ( )-( )+( )-( )=0 n证1 在(x+y)=( )x y 中令x=1,y=-1即得 . n n n n 0 1 2 n n n-k k n k n k=0 1.9若干等式及其组合意义 n证2 在1,n的所有组合中, n含a的组合不含a的组合，有11对 应关系。在任一含a组合及与之对应的 不含a组合中，必有一奇数个元的组合 与一偶数个元的组合。将含奇数个元的 组合做成集，将含偶数个元的组合做成 另一集。此二集的元数相等。 举例 n以4个元素为例，设4个元素为a,b,c,d。 nr为奇数的组合个数为： a、 b、 c、 d、 a,b,c、 a,b,d、 a,c,d、 b,c,d r为偶数的组合个数为： 、 a,b、 a,c、 a,d、 b,c 、 b,d、 c,d、 a,b,c,d 1.9若干等式及其组合意义 n(9) ( )=( )( )+( )( )+( )( ) n即Vandermonde恒等式 n证1 从m个互异红球和n个互异蓝球中取r个 球,按r个球中红球的个数分类. n组合证法: (0,0)到(m+n-r,r)点的路径. (0,0)(m-l,l)(m+n-r,r) 路径数( ) ( ) n( )=( )( ) m+n m n m n m n r 0 r 1 r-1 r 0 m 路径数 n l r-l m+n m n r l r-l P(m-r,r) (m+n-r,r) (m-l,l) l=0,1,2,r Q(m,0) r l=0 1.9若干等式及其组合意义 n(10) 在(9)中令r=mn,再将 ( )等价换成( ) n得( )=( )( )+( )( )+( )( ) m m k m-k m+n m n m n m n m 0 0 1 1 m m 等式的组合意义 n参见课本的P45组合意义 n只说明一一对应关系。 nP46的例1.29 1.10应用举例 n例 某保密装置须同时使用若干把不同 的钥匙才能打开。现有人，每人持若 干钥匙。须人到场，所备钥匙才能开 锁。问至少有多少把不同的钥匙？ 每人至少持几把钥匙？ n解 每人至少缺把钥匙，且每 人所缺钥匙不同。故至少共有( )=35 把不同的钥匙。 7 3 1.10应用举例 n任一人对于其他人中的每人，都至 少有把钥匙与之相配才能开锁。故每 人至少持( )20把不同的钥匙。 n为加深理解，举一个较简单的例子： 人中人到场，所求如上。共需要有 ( )=6把不同的钥匙。每人有( )=3把 钥匙。（见下页图） 1.10应用举例 钥 匙 A 人 B C D 1.10应用举例 n例 有4个相同质点,总能量为4E0,E0是常数。 每个质点所具能量为kE0,k=0,1,2,3,4. nA)若能级为kE0的质点可有k +1种状态，而且 服从Bose-Einstein分布，即同能级的质点可 以处于相同的状态，问系统有几种不同的状 态？（或图像）(可重排列) n B)若能级为kE0的质点可有2(k +1)种状态， 而且服从Fermi-Dirac分布，即不允许同能级 的两个质点有相同状态，问系统有几种不同 状态？（或图像） (不可重排列) 2 2 1.10应用举例 n解