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 基本计数公式的应用