第二十一章基本的计数公式 21加法法则与乘法法则 212排列组合 213二项式定理与组合恒等式 214多项式定理
1 第二十一章 基本的计数公式 21.1 加法法则与乘法法则 21.2 排列组合 21.3 二项式定理与组合恒等式 21.4 多项式定理
21加法法则与乘法法则 加法法则 ˉ乘法法则 应用实例
2 21.1 加法法则与乘法法则 加法法则 乘法法则 应用实例
加法法则 加法法则:事件A有m种产生方式,事件B有n种产生 方式,则“事件A或B有m+n种产生方式 使用条件:事件A与B产生方式不重叠 适用问题:分类选取 推广:事件A1有m1种产生方式,事件A2有m2种产生方 式,…,事件A有nk种产生的方式,则“事件A1或 A2或…Ax有m+n2+…+nk种产生的方式
3 加法法则 加法法则：事件 A 有 m 种产生方式，事件 B 有 n 种产生 方式，则“事件 A 或 B”有 m+n 种产生方式. 使用条件：事件 A 与 B 产生方式不重叠 适用问题：分类选取 推广：事件 A1 有 n1种产生方式，事件 A2有 n2种产生方 式，…, 事件 Ak 有 nk种产生的方式，则“事件 A1或 A2 或…Ak”有 n1+n2+…+nk 种产生的方式
乘法法则 乘法法则:事件A有m种产生方式,事件B有n种产生 方式,则“事件A与B有m种产生方式 使用条件:事件A与B的产生方式相互独立 适用问题:分步选取 推广:事件A1有m1种产生方式,事件A2有m2种产生方 式,…,事件Ak有mk种产生的方式,则“事件A1 与A2与.A4”有m12n种产生的方式
4 乘法法则：事件 A 有 m 种产生方式，事件 B 有 n 种产生 方式，则“事件 A 与 B”有 mn 种产生方式. 使用条件：事件 A 与 B 的产生方式相互独立 适用问题：分步选取 推广：事件 A1 有 n1 种产生方式，事件 A2 有 n2 种产生方 式，…, 事件 Ak 有 nk 种产生的方式，则“事件 A1 与 A2与…Ak” 有 n1n2…nk 种产生的方式. 乘法法则
应用实例 例1设A,B,C是3个城市,从A到B有3条道路,从B 到C有2条道路,从A直接到C有4条道路,问从 A到C有多少种不同的方式? N=3x2+4=10 例2求1400的不同的正因子个数 1400=23527 正因子为:257,其中0x3,0g2,0≤k1 N=3+)(2+1)(1+)=24
5 例 1 设 A,B,C 是 3 个城市，从 A 到 B 有 3 条道路，从 B 到 C 有 2 条道路，从 A 直接到 C 有 4 条道路，问从 A 到 C 有多少种不同的方式？ N=3×2+4 = 10 例 2 求 1400 的不同的正因子个数 1400=23 52 7 正因子为：2i 5j 7k，其中 0≤i≤3, 0≤j≤2, 0≤k≤1 N=(3+1)(2+1)(1+1)=24 应用实例
212排列组合 ■选取问题 集合的排列与组合 基本计数公式的应用 ■多重集排列与组合
6 21.2 排列组合 选取问题 集合的排列与组合 基本计数公式的应用 多重集排列与组合
选取问题-组合计数模型1 设n元集合S,从S中选取r个元素. 根据是否有序,是否允许重复可以将该问题分为四个子类型 不重复 重复 有序集合排列P(nr 多重集排列 无序集合组合Cu)多重集组合
7 选取问题 --组合计数模型1 设 n 元集合 S，从 S 中选取 r 个元素. 根据是否有序，是否允许重复可以将该问题分为四个子类型 不重复 重复 有序 集合排列 P(n,r) 多重集排列 无序 集合组合 C(n,r) 多重集组合
集合的排列 1.从n元集S中有序、不重复选取的r个元素称为S 的一个r排列,S的所有r排列的数目记作P(r) n n≥ P(n,r)=(u-r) 0 n<r 2.环排列 S的环排列数=P(nP
8 1．从 n 元集 S 中有序、不重复选取的 r 个元素称为 S 的一个 r 排列，S 的所有 r 排列的数目记作 P(n,r) ⎪⎩ ⎪⎨⎧ < ≥ = − n r n r n r n P n r 0 ( )! ! ( , ) 2．环排列 S 的环排列数 = r P(n,r) 集合的排列
集合的组合 3.从n元集S中无序、不重复选取的r个元素称为S的 一个r组合,S的所有r组合的数目记作C(n,r P(n, C(n,)={r ≥r 0 n<r 4.C(1,r)=C(ln-) 证明方法: 公式代入 组合证明(一一对应)
9 3．从 n 元集 S 中无序、不重复选取的 r 个元素称为 S 的 一个 r 组合，S 的所有 r 组合的数目记作 C(n,r) ⎪⎩ ⎪⎨⎧ < ≥ = n r n r r P n r C n r 0 ! ( , ) ( , ) 4．C(n,r) = C(n,n−r) 证明方法： 公式代入 组合证明（一一对应） 集合的组合
基本计数公式的应用 例1从1-300中任取3个数使得其和能被3整除有 多少种方法? A={1,4,…,298} B={2,5,,29 C=3,6,…,300} 分类: 分别取自A,B,C:各C1003) A,B,C各取1个:C10,13 N=3C1003)1+1005=1485100
10 例 1 从 1—300 中任取 3 个数使得其和能被 3 整除有 多少种方法？ A={1, 4, …,298} B={2, 5, …,299} C={3, 6, …, 300} 分类： 分别取自 A, B, C: 各 C(100,3) A, B, C 各取 1 个： C(100,1)3 N= 3C(100,3) + 1003 = 1485100 基本计数公式的应用