《离散数学》课程PPT教学课件（讲稿）第10章 组合分析初步

组合分析

1 组合分析

组合分析部分 ■第10章组合分析初步

2 组合分析部分 ◼ 第10章 组合分析初步

第10章组合分析初步 10.1加法法则和乘法法则 □加法法则与乘法法则 口应用实例 ■10.2基本排列组合的计数方法 口排列组合问题的分类 口集合的排列与组合 口多重集的排列与组合

3 第10章组合分析初步 ◼ 10.1 加法法则和乘法法则 加法法则与乘法法则 应用实例 ◼ 10.2 基本排列组合的计数方法 排列组合问题的分类 集合的排列与组合 多重集的排列与组合

加法法则 事件A有m种产生方式,事件B有n种产生方 式,则“事件A或B”有m+n种产生方式 使用条件:事件A与B产生方式不重叠 适用问题:分类选取方式分别计数,再相加 推广:事件A1有m1种产生方式,事件A2有m2 种产生方式,…事件A有nk种产生的方式, 则“事件A1或A2或…Ak”有m1+n2+…,+mk种产 生的方式

4 加法法则 使用条件：事件 A与 B 产生方式不重叠 适用问题：分类选取. 方式分别计数，再相加. 推广：事件 A1 有 n1 种产生方式，事件 A2有 n2 种产生方式，…, 事件 Ak 有 nk 种产生的方式， 则“事件A1 或 A2或…Ak” 有 n1+n2+…+nk 种产 生的方式. 事件 A有 m 种产生方式，事件 B 有 n 种产生方 式，则“事件 A 或 B”有 m+n 种产生方式

乘法法则 事件A有m种产生方式,事件B有n种产生方 式,则“事件A与B有m种产生方式 使用条件:事件A与B产生方式相互独立 适用问题:分步选取方式是连续的步骤,各步 相互独立,分别计数,然后相乘 推广:事件A1有n1种产生方式,事件A2有n2 种产生方式,…事件A1有mk种产生的方式, 则“事件A1与A2与,,4”有n1n2…,nk种产生 的方式

5 乘法法则 使用条件：事件A与B产生方式相互独立 适用问题：分步选取. 方式是连续的步骤，各步 相互独立，分别计数，然后相乘. 推广：事件 A1 有 n1 种产生方式，事件 A2有 n2 种产生方式，…, 事件 Ak 有 nk 种产生的方式， 则“事件A1 与 A2与 …Ak” 有 n1n2…nk 种产生 的方式. 事件 A有 m 种产生方式，事件 B 有 n 种产生方 式，则“事件 A 与 B”有 mn 种产生方式

应用实例 例1设A,B,C是3个城市,从A到B有3条道路, 从B到C有2条道路,从A直接到C有4条道路, 问从A到C有多少种不同的方式? 解N=3×2+4=10 例2求1400的不同的正因子个数 解1400=23527 正因子为:257k,其中0≤3,0≤2,0≤ks1 N=(3+1)(2+1)(1+1)=24

6 应用实例 解 1400 = 23 5 2 7 正因子为：2 i 5 j 7 k，其中 0 i3, 0j2, 0k1 N = (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 的不同的正因子个数

排列组合的分类 选取问题:设n元集合S,从S中选取r个元素 根据是否有序,是否允许重复可将该问题分为四 个子类型 不重复 重复 有序集合排列P(,r)多重集排列 无序集合组合C(u,n)多重集组合

7 排列组合的分类 选取问题：设 n 元集合 S，从 S 中选取 r 个元素. 根据是否有序，是否允许重复可将该问题分为四 个子类型 不重复 重复 有序 集合排列 P(n,r) 多重集排列 无序 集合组合 C(n,r) 多重集组合

集合的排列 从n元集S中有序、不重复选取的r个元素称为 S的一个r排列,S的所有r排列的数目记作Pr n n≥r n-1 n 0 n<I S的r环排列数 rln

8 集合的排列 从 n 元集 S 中有序、不重复选取的 r 个元素称为 S 的一个r 排列，S 的所有 r 排列的数目记作 S 的 r- 环排列 数 =        − = = − n r n r n r n n r n P r n 0 ( )! ! ( )! ! ( )! ! r n r n r P r n − = r Pn

集合的组合 从n元集S中无序、不重复选取的r个元素称为 S的一个r组合,S的所有r组合的数目记作Cn n≥r !r!(n-r)! n<r 证明方法: 公式代入 组合证明(一一对应)

9 集合的组合 从 n 元集 S 中无序、不重复选取的 r 个元素称为 S 的一个r 组合，S 的所有 r 组合的数目记作 证明方法： 公式代入 组合证明（一一对应）        − = = n r n r r n r n r P C r n r n 0 !( )! ! ! r Cn

基本计数公式的应用 例1从1300中任取3个数使得其和能被3整除有 多少种方法? 解令A={1,4,…,298},B={2,5,…,299} C=3,6,…,300} 将方法分类: 分别取自A,B,C:各Cio A,B,C各取1个:C100 N=3C100+0100)=1485100 10

10 基本计数公式的应用 解 令 A={1, 4, …, 298}，B={2, 5, …, 299} C={3, 6, …, 300} 将方法分类： 分别取自 A, B, C: 各 A, B, C各取1个： 1 C100 3 C100 3 ( ) 1485100 1 3 100 3 N = C100 + C = 例1 从1—300中任取3个数使得其和能被3整除有 多少种方法？