1-1 排列与组合40837.ppt

组合数学 钱江jqian104 北邮理学院 组合数学就是按照一定的规则来安排一些离散个体的有关问题 其内容包括 1 计数与枚举 2 容斥原理和鸽巢原理 3 组合设计 4 组合算法和组合优化 5 图论 排列 组合 母函数 递推关系 容斥原理 Burnside引理 Polya定理 第一章排列与组合 1 1排列与组合1 2排列组合的生成算法1 3组合意义的解释与应用举例 1 1排列与组合 加法法则和乘法法则一一对应排列 组合圆周排列可重排列可重组合不相邻的组合 1 加法法则与乘法法则 加法法则 设具有性质A的事件有m个 具有性质B的事件有n个 则具有性质A或B的事件有m n个 若 A m B n A B 则 A B m n 集合论语言 基本假设 性质A和性质B是无关的两类 例1某班选修企业管理的有18人 不选的有10人 则该班共有18 10 28人 例2假设要从北京坐飞机或者火车或者客车到上海 北京每天到达上海的飞机有5个航班 火车有7趟 客车有10趟 则每天由北京到达上海的旅行方式有5 7 10 22种 乘法法则 设具有性质A的事件有m个 具有性质B的事件有n个 则具有性质A和B的事件有mn个 若 A m B n A B a b a A b B 则 A B mn 集合论语言 例3从A到B有三条道路 从B到C有两条道路 则从A经B到C有3 2 6条道路 加法法则 得到事件通过两种不同的方法 乘法法则 得到事件通过两个步骤 例4某种样式的运动服的着色由底色和装饰条纹的颜色配成 底色可选红 蓝 橙 黄 条纹色可选黑 白 则共有4 2 8种着色方案 若此例改成底色和条纹都用红 蓝 橙 黄四种颜色的话 则方案数就不是4 4 16 而只有4 3 12种 例5 1 求小于10000的含1的正整数的个数 2 求小于10000的含0的正整数的个数 1 小于10000的不含1的正整数可看做4位数 但0000除外 故有9 9 9 9 1 6560个 含1的有 9999 6560 3439个 另 全部4位数有104个 不含1的四位数有94个 含1的4位数为两个的差 104 94 3439个 9999 7380 2619 2 含0 和 含1 不可直接套用 0019含1但不含0 不含0的1位数有9个 2位数有92个 3位数有93个 4位数有94个 不含0小于10000的正整数有 含0小于10000的正整数有 1 4 3 5 60 2 6 3 18 个位数有5种取法 千位数有8种取法 百位 十位各有8 7种取法 5 8 8 7 2240 例6 1 n 73 112 134 求除尽n的数的个数 2 n 73 142 求除尽n的数的个数 例7在1000和9999之间有多少每位上的数字均不同的奇数 例8由a b c d e这5个字符 从中取6个构成字符串 要求 1 第1 6个字符必为子音字符b c d 2 每个字符串必有两个母音字符a或e 且两个母音字符不相邻 3 相邻的两个子音字符必不相同 求满足这样的条件的字符串的个数 由条件 1 两个母音字符的位置不能在1 6 又由条件 2 位置只能是 2 4 2 5 和 3 5 之一 对每种格式 母音2 2 相邻子音3 2 其他两个子音3 3 因此答案为3 2 2 3 2 3 3 648 如我们说A集合有n个元素 A n 无非是建立了将A中元与 1 n 元一一对应的关系 在组合计数时往往借助于一一对应实现模型转换 比如要对A集合计数 但直接计数有困难 于是可设法构造一易于计数的B 使得A与B一一对应 2 一一对应 一一对应 概念是一个在计数中极为基本的概念 一一对应既是单射又是满射 一种常见的思路是按轮计场 费事 另一种思路是淘汰的选手与比赛 按场计 集一一对应 63场比赛 例9在64名选手之间进行淘汰赛 即一场的比赛结果 失败者退出比赛 最后产生一名冠军 问要举行几场比赛 可以先计算对角线的个数 然后计算交点 但是存在在多边形内无交点的情形 比较复杂 可以考虑对应关系 多边形内交点to多边形四个顶点 可以证明这是一一映射 映射 单且满 例10设凸n边形的任意三条对角线不共点 求对角线在多边形内交点的个数 排列的典型例子是取球模型 从n个不同的球中 取出r个 放入r个不同的盒子里 每盒1个 第1个盒子有n种选择 第2个有n 1种选择 第r个有n r 1种选择 故由乘法法则有 3 排列 组合 定义 从n个不同的元素中 取r个不重复的元素 按次序排列 称为从n个中取r个的无重排列 排列的个数用P n r 表示 当r n时称为全排列 P n r n n 1 n r 1 n n r P n n n 例11由5种颜色的星状物 20种不同的花排列成如下图案 两边是星状物 中间是3朵花 问共有多少种这样的图案 两边是星状物 从五种颜色的星状物中取两个的排列的排列数是P 5 2 20 20种不同的花取3种排列的排列数是 根据乘法法则得图案数为 P 20 3 20 19 18 6840 20 6840 136800 接上例 若A单位的2人排在队伍两端 B单位的3人不能相邻 问有多少种不同的排列方案 B单位3人按一个元素参加排列 P 8 8 P 3 3 A单位的人排法固定后A A A A A A A B单位第一人有6种选择 第二人有5种 第三人有4种 因此答案为P 7 7 6 5 4 例12A单位有7名代表 B单位有3位代表 排成一列合影要求B单位的3人排在一起 问有多少种不同的排列方案 例13试求由 1 3 5 7 组成的所有不重复出现的整数的总和 这样的整数可以是1位数 2位数 3位数 4位数 若设 是i位数的总和 则 S S1 S2 S3 S4 S1 1 3 5 7 16 于是我们只需要计算Si即可 S4 6 1 3 5 7 1000 6 1 3 5 7 100 6 1 3 5 7 10 6 1 3 5 7 96000 9600 960 96 106656 S 16 528 10656 106656 117856 S2 3 1 3 5 7 10 3 1 3 5 7 480 48 528 S3 6 1 3 5 7 100 6 1 3 5 7 10 6 1 3 5 7 9600 960 96 10656 组合的个数用C n r 表示 或者用表示 定义 从n个不同元素中取r个不重复的元素组成一个子集 而不考虑其元素的顺序 称为从n个中取r个的无重组合 C n r 0 若n r 故有 C n r r P n r C n r P n r r 从n个不同的球中 取出r个 放入r个相同的盒子里 每盒1个 这是从n个中取r个的组合的模型 若放入盒子后再将盒子标号区别 则又回到排列模型 每一个组合可有r 个标号方案 2 C 5 2 C 7 2 C 10 2 10 21 45 76 1 5 7 5 10 7 10 155 3 155 76 231 C 5 7 10 2 例14有5本不同的日文书 7本不同的英文书 10本不同的中文书 1 取2本不同文字的书 2 取2本相同文字的书 3 任取两本书 例15甲和乙两单位共11个成员 其中甲单位7人 乙单位4人 拟从中组成一个5人小组 1 要求包含乙单位恰好2人 2 要求至少包含乙单位2人 3 要求乙单位某一人与甲单位特定一人不能同时在这个小组 试求各有多少种方案 1 C 4 2 C 7 3 2 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 300 分成3类 A i i 1 mod3 1 4 7 298 B i i 2 mod3 2 5 8 299 C i i 3 mod3 3 6 9 300 例16从 1 300 中取3个不同的数 使这3个数的和能被3整除 有多少种方案 要满足条件 有四种情形 1 3个数同属于A 2 3个数同属于B 3 3个数同属于C 4 A B C各取一数 故共有 3C 100 3 1003 485100 1000000 1485100 解1 a1选择其同伴有7种可能 选定后 余下6人中某一人选择其同伴只有5种可能 余下4人 其中某1人有3种选择可能 在余下的2人只好配成一对 无法选择 故共有 N 7 5 3 105 例17假定有a1 a2 a3 a4 a5 a6 a7 a8这8位成员 两两配对分成4组 试问有多少种方案 解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个元素的一个排列 例18某广场有6个入口 每个入口每次只能通过一辆汽车 现有9辆车要开进广场 有多少种入场方案 解2 在14个元的排列中先确定 1 的位置 有C 14 5 种选择 再确定车的位置 有9 种选择 故C 14 5 9 即为所求 解3 实际上相当于14个位置中选取9辆汽车的排列 即为P 14 9 解1 标号可产生5 个14个元的全排列 若设x为所求方案 则x 5 14 故x 14 5 726485760 注意到 每个交点只有两个对角线通过 对应了4个顶点所组成的一个组合 不同的交点对应的组合也不相同 故共有C n 4 个交点 例19一个凸n边形 它的任何3条对角线都不交于同一点 问它的所有对角线在凸n边形内部有多少个交点 定义 从n个不同的数中不重复的取出取出r个沿一圆周排列 称为一个圆周排列 所有的r 圆周排列数记为Q n r 注意圆周排列与排列的不同之处在于圆周排列首尾相邻 如a b c d的4种不同排列abcd dabc cdab bcda 在圆周排列中都是一个排列 4 圆周排列 以4个元素为例 Q n r P n r r 2 r nQ n n n 1 从n个中取r个的圆周排列的排列数为 若无要求 则为Q 8 8 若要求蓝色珠子一起 则为Q 6 6 P 3 3 若要求蓝色珠子不相邻 则为Q 5 5 5 4 3 例205颗红珠子 3颗蓝珠子装在圆板的四周 试问有多少种方案 若要求蓝色珠子不相邻 又有多少种排列方案 蓝色珠子在一起呢 例215对夫妇出席一个宴会 围一圆桌坐下 试问有几种不同的坐法 要求每对夫妇相邻又如何 若无限制 则为Q 10 10 若要求相邻 则为Q 5 5 2 2 2 2 2 5 可重排列 定义 多重集是指元素可以多次出现的集合 即元素可以重复 我们把某个元素ai出现的次数ni ni 0 1 2 叫做该元素的重复数 通常把含有k种不同元素的多重集S记作 定理 设多重集则S的r 可重 排列数是kr 推论 设多重集且对一切的i 1 2 k 有ni r 则S的r 可重 排列数是kr 所求的标志数是多重集 2红旗 3黄旗 的排列数 故N 5 2 3 10 例23用两面红旗 三面黄旗依次悬挂在一根旗杆上 问可以组成多少种不同的标志 例22求不多于4位数的二进制数的个数 设 则S的r 排列数N满足 1 若r n 则N 0 2 若r n 则N 3 若r n 且对所有的i 则 4 若r n 且存在i ni r 则对N没有一般的求解公式 具体解法以后再说 定理 从中取r个作可重的组合 其个数为C k r 1 r 6 可重组合 r个相同的球 0 010 01 10 0 k 1个相同的盒壁 而后一问题又可转换为r个相同的球与k 1个相同的盒壁的排列的问题 则所求计数为C k r 1 r 这个计数问题相当于r个相同的球放入k个不同的盒子里 个数没有限制的计数 另证 不妨假设k个不同元素为1 2 k 设某一个r可重组合为b1 b2 br 由于允许重复 可以假设 这相当于从1到k r 1中取r个不允许重复的组合 很容易验证 这是一个一一对应 从而定理成立 第二个证明可说一种 拉伸压缩 技巧 不可谓不巧妙 但仍不如第一证明来的明快 由此可见组合证明的功效 任取一个所求的r组合 从中拿走每个元素一个就得到S的一个r k组合 反之 对于S的一个r k组合 加入元素a1 a2 ak就得到所求组合 所以其组合数即为S的r k可重组合数 设则S的r 组合数N满足 4 若r n 且存在i ni r 则对N没有一般的求解公式 具体解法以后再说 1 若r n 则N 0 2 若r n 则N 1 3 若r n 且