离散数学组合分析初步.ppt

1 组合分析 2 第10章组合分析初步 10 1加法法则与乘法法则10 2基本排列组合的计数方法10 3递推方程的求解与应用 3 10 1加法法则和乘法法则 加法法则与乘法法则应用实例 4 加法法则 使用条件 事件A与B产生方式不重叠适用问题 分类选取 方式分别计数 再相加 推广 事件A1有n1种产生方式 事件A2有n2种产生方式 事件Ak有nk种产生的方式 则 事件A1或A2或 Ak 有n1 n2 nk种产生的方式 事件A有m种产生方式 事件B有n种产生方式 则 事件A或B 有m n种产生方式 5 乘法法则 使用条件 事件A与B产生方式相互独立适用问题 分步选取 方式是连续的步骤 各步相互独立 分别计数 然后相乘 推广 事件A1有n1种产生方式 事件A2有n2种产生方式 事件Ak有nk种产生的方式 则 事件A1与A2与 Ak 有n1n2 nk种产生的方式 事件A有m种产生方式 事件B有n种产生方式 则 事件A与B 有mn种产生方式 6 应用实例 解1400 23527正因子为 2i5j7k 其中0 i 3 0 j 2 0 k 1N 3 1 2 1 1 1 24 例1设A B C是3个城市 从A到B有3条道路 从B到C有2条道路 从A直接到C有4条道路 问从A到C有多少种不同的方式 解N 3 2 4 10 例2求1400的不同的正因子个数 7 10 2基本排列组合的计数方法 排列组合的分类集合的排列集合的组合多重集的排列多重集的组合 8 排列组合的分类 选取问题 设n元集合S 从S中选取r个元素 根据是否有序 是否允许重复可将该问题分为四个子类型 9 集合的排列 从n元集S中有序 不重复选取的r个元素称为S的一个r排列 S的所有r排列的数目记作S的r 环排列数 10 集合的组合 从n元集S中无序 不重复选取的r个元素称为S的一个r组合 S的所有r组合的数目记作证明方法 公式代入组合证明 一一对应 11 基本计数公式的应用 解令A 1 4 298 B 2 5 299 C 3 6 300 将方法分类 分别取自A B C 各A B C各取1个 例1从1 300中任取3个数使得其和能被3整除有多少种方法 12 基本计数公式的应用 续 解1000 1000 999 998 2 1将上面的每个因子分解 若分解式中共有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 的末尾有多少个0 13 多重集S n1 a1 n2 a2 nk ak 0 ni 1 全排列r n n1 n2 nk n证明 分步选取 先放a1 有种方法 再放a2 有种方法 放ak有种方法 2 若r ni时 每个位置都有k种选法 得kr 多重集的排列 14 多重集的组合 当r ni 多重集S n1 a1 n2 a2 nk ak 的组合数为证明一个r组合为 x1 a1 x2 a2 xk ak 其中x1 x2 xk r xi为非负整数 这个不定方程的非负整数解对应于下述排列1 101 101 10 01 1x1个x2个x3个xk个r个1 k 1个0的全排列数为 15 实例 解 设盒子的球数依次记为x1 x2 xn 则满足下述方程 x1 x2 xn r x1 x2 xn为非负整数该方程的解的个数为 例3r个相同的球放到n个不同的盒子里 每个盒子球数不限 求放球方法数 16 实例 解 固定a和b中间选7个字母 有种方法将它看作大字母与其余17个全排列有18 种 例4排列26个字母 使得a与b之间恰有7个字母 求方法数 17 实例 续 解 1 2 例5 1 10个男孩 5个女孩站成一排 若没女孩相邻 有多少种方法 2 如果站成一个圆圈 有多少种方法 18 实例 续 解 相当于2n不同的球放到n个相同的盒子 每个盒子2个 放法为 例6把2n个人分成n组 每组2人 有多少分法 19 实例 续 例79本不同的书 其中4本红皮 5本白皮 1 9本书的排列方式数有多少 2 若白皮书