《离散数学组合分析初步.ppt》由会员分享，可在线阅读，更多相关《离散数学组合分析初步.ppt（19页珍藏版）》请在金锄头文库上搜索。
1、 组合分析组合分析1第第10 章章 组合分析初步组合分析初步n10.1 加法法则与乘法法则加法法则与乘法法则n10.2 基本排列组合的计数方法基本排列组合的计数方法n10.3 递推方程的求解与应用递推方程的求解与应用210.1 加法法则和乘法法则加法法则和乘法法则n加法法则与乘法法则加法法则与乘法法则n应用实例应用实例3加法法则加法法则使用条件：事件使用条件：事件 A与与 B 产生方式不重叠产生方式不重叠适用问题：分类选取适用问题：分类选取. 方式分别计数，再相加方式分别计数，再相加. 推广：事件推广：事件 A1 有有 n1 种产生方式，事件种产生方式，事件 A2有有 n2种产生方式，种产生方
2、式，, 事件事件 Ak 有有 nk 种产生的方式，种产生的方式，则则“事件事件A1 或或 A2或或Ak” 有有 n1+n2+nk 种产种产生的方式生的方式. 事件事件 A有有 m 种产生方式，事件种产生方式，事件 B 有有 n 种产生方种产生方式，则式，则“事件事件 A 或或 B”有有 m+n 种产生方式种产生方式.4乘法法则乘法法则使用条件：事件使用条件：事件A与与B产生方式相互独立产生方式相互独立适用问题：分步选取适用问题：分步选取. 方式是连续的步骤，各步方式是连续的步骤，各步相互独立，分别计数，然后相乘相互独立，分别计数，然后相乘. 推广：事件推广：事件 A1 有有 n1 种产生方式，
3、事件种产生方式，事件 A2有有 n2种产生方式，种产生方式，, 事件事件 Ak 有有 nk 种产生的方式，种产生的方式，则则“事件事件A1 与与 A2与与 Ak” 有有 n1n2nk 种产生种产生的方式的方式. 事件事件 A有有 m 种产生方式，事件种产生方式，事件 B 有有 n 种产生方种产生方式，则式，则“事件事件 A 与与 B”有有 mn 种产生方式种产生方式.5应用实例应用实例解解 1400 = 23 52 7 正因子为：正因子为：2i 5j 7k，其中，其中 0 i 3, 0 j 2, 0 k 1 N = (3+1)(2+1)(1+1) = 24例例1 设设A, B, C是是3个城市
4、，从个城市，从 A 到到 B 有有3条道路，条道路，从从 B 到到C 有有2条道路，从条道路，从 A 直接到直接到 C 有有4条道路，条道路，问从问从 A 到到 C 有多少种不同的方式？有多少种不同的方式？解解 N = 3 2+4 = 10例例2 求求 1400 的不同的正因子个数的不同的正因子个数610.2 基本排列组合的计数方法基本排列组合的计数方法n排列组合的分类排列组合的分类n集合的排列集合的排列n集合的组合集合的组合n多重集的排列多重集的排列n多重集的组合多重集的组合7排列组合的分类排列组合的分类选取问题：设选取问题：设 n 元集合元集合 S，从，从 S 中选取中选取 r 个元素个元
5、素.根据是否有序，是否允许重复可将该问题分为四根据是否有序，是否允许重复可将该问题分为四个子类型个子类型不重复不重复重复重复有序有序集合排列集合排列 P(n,r)多重集排列多重集排列无序无序集合集合组合合 C(n,r)多重集多重集组合合8集合的排列集合的排列从从 n 元集元集 S 中有序、不重复选取的中有序、不重复选取的 r 个元素称为个元素称为 S 的一个的一个r 排列排列，S 的所有的所有 r 排列的数目记作排列的数目记作 S 的的 r- 环排列环排列 数数 = 9集合的组合集合的组合从从 n 元集元集 S 中无序、不重复选取的中无序、不重复选取的 r 个元素称为个元素称为 S 的一个的一
6、个r 组合组合，S 的所有的所有 r 组合的数目记作组合的数目记作证明方法：证明方法： 公式代入公式代入 组合证明（一一对应）组合证明（一一对应）10基本计数公式的应用基本计数公式的应用解解 令令 A=1, 4, , 298，B=2, 5, , 299 C=3, 6, , 300将方法分类：将方法分类： 分别取自分别取自 A, B, C: 各各 A, B, C各取各取1个：个： 例例1 从从1300中任取中任取3个数使得其和能被个数使得其和能被3整除有整除有多多少种方法？少种方法？11基本计数公式的应用（续）基本计数公式的应用（续）解解 1000! = 1000 999 998 2 1 将上面
7、的每个因子分解，若分解式中共有将上面的每个因子分解，若分解式中共有 i 个个5, j 个个2，那么，那么 min i, j 就是就是 0 的个数的个数. 1, , 1000 中有中有 500 个是个是 2 的倍数，的倍数，j 500; 200 个是个是 5 的倍数，的倍数， 40 个是个是 25 的倍数（多加的倍数（多加40个个5），）， 8 个是个是 125 的倍数（再多加的倍数（再多加8个个5），）， 1 个是个是 625 的倍数（再多加的倍数（再多加1个个5） i = 200 + 40 + 8 + 1 = 249. min i, j =249. 例例2 求求1000！的末尾有多少个！的末
8、尾有多少个0？12多重集多重集 S =n1 a1, n2 a2, , nk ak，0 ni + (1) 全排列全排列 r = n, n1 + n2 + + nk = n 证明：分步选取，先放证明：分步选取，先放 a1, 有有 种方法；再放种方法；再放 a2, 有有 种方法，种方法，. , 放放ak有有 种方法种方法 (2) 若若 r ni 时，每个位置都有时，每个位置都有 k 种选法，得种选法，得 kr.多重集的排列多重集的排列13多重集的组合多重集的组合当当r ni ， 多重集多重集 S = n1 a1, n2 a2, , nk ak 的组的组合数为合数为 证明证明 一个一个 r 组合为组合
9、为 x1 a1, x2 a2, , xk ak ，其，其中中 x1 + x2+ + xk = r , xi 为非负整数为非负整数. 这个不定方程这个不定方程的非负整数解对应于下述排列的非负整数解对应于下述排列 11 0 11 0 11 0 0 11 x1个个 x2个个 x3个个 xk个个r 个个1，k-1个个 0 的全排列数为的全排列数为14实例实例解：设盒子的球数依次记为解：设盒子的球数依次记为 x1, x2, , xn, 则满足则满足下下 述方程：述方程： x1 + x2 + + xn = r， x1,x2, , xn为非负整数为非负整数 该方程的解的个数为：该方程的解的个数为： 例例3
10、r 个相同的球放到个相同的球放到 n 个不同的盒子里，每个盒个不同的盒子里，每个盒 子球数不限，求放球方法数子球数不限，求放球方法数.15实例实例解：固定解：固定a 和和 b 中间选中间选7个字母，有个字母，有 种方法种方法 将它看作大字母与其余将它看作大字母与其余 17个全排列有个全排列有18！种，！种，例例4 排列排列 26个字母，使得个字母，使得a与与b之间恰有之间恰有7个字母，个字母，求方法数求方法数.16实例（续）实例（续）解解: (1) (2) 例例5 (1) 10个男孩，个男孩，5个女孩站成一排，若没女孩个女孩站成一排，若没女孩 相邻，有多少种方法？相邻，有多少种方法？ (2)
11、如果站成一个圆圈，有多少种方法？如果站成一个圆圈，有多少种方法？17实例（续）实例（续）解：相当于解：相当于 2n 不同的球放到不同的球放到 n 个相同的盒子，每个相同的盒子，每个盒子个盒子 2个，放法为个，放法为例例6 把把 2n 个人分成个人分成 n 组，每组组，每组2人，有多少分法？人，有多少分法？18实例（续）实例（续）例例7 9本不同的书，其中本不同的书，其中4本红皮，本红皮，5本白皮本白皮. (1) 9本书的排列方式数有多少？本书的排列方式数有多少？ (2) 若白皮书必须放在一起，那么有多少方法？若白皮书必须放在一起，那么有多少方法？ (3) 若白皮书必须放在一起，红皮书也必须放在若白皮书必须放在一起，红皮书也必须放在 一起，那么有多少方法？一起，那么有多少方法？ (4) 若把皮和红皮书必须相间，有多少方法？若把皮和红皮书必须相间，有多少方法？解：解： (1) 9! (2) 5！5！ (3) 5！4！2！ (4) 5！4！19
