离散数学第8章.ppt_第1页
离散数学第8章.ppt_第2页
离散数学第8章.ppt_第3页
离散数学第8章.ppt_第4页
离散数学第8章.ppt_第5页
已阅读5页,还剩44页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、1,第8章 组合计数基础,2,第8章 组合计数基础,引言 组合问题的处理技巧 8.1 基本计数规则 8.2 排列与组合 8.3 二项式定理与组合恒等式 8.4 多项式定理,3,组合问题的处理技巧,一一对应 数学归纳法 上下界逼近,4,一一对应与上下界逼近,例1 在允许移动被切割的物体的情况下,最少用多少次切割可以将 333 的立方体切成 27个单位边长的立方体?,中间的小立方体的6个面都是切割产生的面,每次切割至多产生一个面,至少需要6次切割。存在一种切割方法恰好用 6 次切割。,例2 100个选手淘汰赛,为产生冠军至少需要多少轮比赛? 方法1:50+25+12+6+3+2+1=99 方法2:

2、比赛次数与淘汰人数之间存在一一对应,总计淘汰99人,因此至少需要99场比赛.,5,8.1 基本计数规则,8.1.1 加法法则 8.1.2 乘法法则 8.1.3 分类处理与分步处理,6,加法法则,加法法则:事件A 有 m 种产生方式,事件 B 有n 种产生方式,则 “事件A或B” 有 m+n 种产生方式. 使用条件:事件 A 与 B 产生方式不重叠 适用问题:分类选取 推广:事件 A1有 p1种产生方式,事件 A2有 p2 种产生方式,, 事件 Ak 有 pk 种产生的方式,则 “事件A1或 A2或 Ak” 有 p1+p2+pk 种产生的方式.,7,乘法法则,乘法法则:事件A 有 m 种产生方式

3、,事件 B 有n 种产生方式,则 “事件A与B” 有 m n 种产生方式. 使用条件:事件 A 与 B 产生方式彼此独立 适用问题:分步选取 推广:事件 A1有 p1种产生方式,事件 A2有 p2 种产生方式,, 事件 Ak 有 pk 种产生的方式,则 “事件A1与 A2与 Ak” 有 p1 p2 pk 种产生的方式.,8,分类处理与分步处理,分类处理:对产生方式的集合进行划分,分别计数,然 后使用加法法则 分步处理:一种产生方式分解为若干独立步骤,对每步 分别进行计数,然后使用乘法法则 分类与分步结合使用: 先分类,每类内部分步 先分步,每步又分类,9,应用实例,例3 设A, B, C 是3

4、个城市,从A 到 B 有3条道路,从B 到 C 有2条道路,从A 直接到 C 有4条道路,问从 A 到 C 有多少种不同的方式? 解: N=32+4 = 10 例4 求1400的不同的正因子个数 1400=23 52 7 解:正因子为:2i 5j 7k,其中 0i3, 0j2, 0k1 N=(3+1)(2+1)(1+1)=24,10,8.2 排列与组合,引言 选取问题 8.2.1 集合的排列与组合 8.2.2 多重集的排列与组合,11,选取问题 -组合计数模型1,设 n 元集合 S,从 S 中选取 r 个元素. 根据是否有序,是否允许重复可以将该问题分为四个子类型,12,集合的排列,定义 从

5、n 元集 S 中有序、不重复选取的 r 个元素称为 S 的一个 r 排列,S 的所有 r 排列的数目记作 P(n,r) 定理8.1 证明 使用乘法法则 推论 S 的环排列数 =,13,集合的组合,定义 从 n 元集 S 中无序、不重复选取的 r 个元素称为 S 的一个 r 组合,S 的所有 r 组合的数目记作 C(n,r) 定理8.2,推论 设n, r为正整数,则 (1) C(n, r)= (2) C(n, r) = C(n, nr) (3) C(n, r)=C(n1,r1)+C(n1,r),14,证明方法,方法1:公式代入并化简 方法2:组合证明 实例:证明 C(n, r) = C(n, n

6、r) 证 设 S =1, 2, , n是n元集合,对于S 的任意 r-组合 A=a1, a2, , ar,都存在一个S 的 nr 组合SA与之对应. 显然不同的 r 组合对应了不同的 nr 组合,反之也对,因 此 S 的 r 组合数恰好与 S 的(nr)组合数相等. C(n, r)=C(n1,r1)+C(n1,r) 称为 Pascal公式,也对应了杨 辉三角形, 两种证明方法都适用.,15,杨辉三角,16,基本计数公式的应用,解 分类选取 A = 1, 4, ,298 B = 2, 5, ,299 C = 3, 6, , 300 分别取自 A, B, C: 各 C(100,3) A, B, C

7、 各取 1 个(分步处理): C(100,1)3 N= 3C(100,3) + 1003 = 1485100,例8.5 从1300中任取3个数使得其和能被3整除有多少种方法?,17,基本计数公式的应用(续),解: 1000!=1000 999 998 21 将上面的每个因子分解,若分解式中共有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+

8、40+8+1 = 249. min(i, j)=249.,例2 求1000!的末尾有多少个0?,18,基本计数公式的应用(续),例3 设A为 n 元集,问 (1) A上的自反关系有多少个? (2) A上的反自反关系有多少个? (3) A上的对称关系有多少个? (4) A上的反对称关系有多少个? (5) A上既不对称也不是反对称 的关系有多少个?,19,多重集的排列,定理8.3 多重集S=n1a1, n2a2, , nkak,0 ni + (1) 全排列 r = n, n1 + n2 + + nk = n 证明:分步选取. 先放a1, 有C(n,n1) 种方法;再放a2, 有 C(n n1,n2

9、)种方法, . , 放ak,有C(nn1n2 nk1,nk) 种方法 (2) 若r ni 时,每个位置都有 k 种选法,得 kr.,20,多重集的组合,定理8.4 多重集 S=n1a1, n2a2, , nkak,0ni + 当 r ni , S的r 组合数为 N = C(k+r1,r), 证明 一个 r 组合为 x1a1, x2a2, , xkak, 其中 x1 + x2 + + xk = r , xi 为非负整数. 这个不定方程的非负整数解对应于下述排列 11 0 11 0 11 0 0 11 x1个 x2个 x3个 xk个 r 个1,k1个 0 的全排列数为,21,实例,例5 排列26个

10、字母,使得 a 与 b 之间恰有7个字母,求方法数.,解: 设盒子的球数依次记为 x1, x2, , xn, 则满足 x1 + x2 + + xn = r, x1, x2, , xn 为非负整数 N = C(n+r1, r),例4 r 个相同的球放到 n 个不同的盒子里,每个盒子球数不限,求放球方法数.,解: 固定a 和 b, 中间选7个字母,有2 P(24,7)种方法, 将它看作大字母与其余17个字母全排列有18!种,共 N = 2 P(24,7) 18!,22,实例(续),例6 (1) 10个男孩,5个女孩站成一排,若没有女孩相邻, 有多少种方法? (2) 如果站成一个圆圈,有多少种方法?

11、,解: (1) P(10,10) P(11,5) (2) P(10,10) P(10,5)/10,解:相当于2n 不同的球放到 n 个相同的盒子,每个盒子2个,放法为,例7 把 2n 个人分成 n 组,每组2人,有多少分法?,23,实例(续),解 使用一一对应的思想求解这个问题. a1, a2, , ak :k个不相邻的数, 属于集合1, 2, , n b1, b2, , bk:k个允许相邻的数, 属于集合1, , n(k1) 对应规则是 bi = ai(i1). i =1, 2, , k 因此 N = C(nk+1,k),例8 从S=1, 2, , n中选择 k 个不相邻的数,有多少种方法?

12、,24,8.3二项式定理与组合恒等式,8.3.1 二项式定理 8.3.2 组合恒等式 8.3.3 非降路径问题,25,二项式定理,定理8.5 设 n 是正整数,对一切 x 和 y 证明方法: 数学归纳法、组合分析法. 证 当乘积被展开时其中的项都是下述形式:xi yni, i = 0, 1, 2, , n. 而构成形如 xiyni 的项,必须从n 个 和 (x+y) 中选 i 个提供 x,其它的 ni 个提供 y. 因此, xiyni 的系数是 ,定理得证.,26,二项式定理的应用,例1 求在(2x3y)25的展开式中x12y13的系数. 解 由二项式定理 令i =13 得到展开式中x12y1

13、3的系数,即,27,组合恒等式递推式,证明方法:公式代入、组合分析 应用: 1式用于化简 2式用于求和时消去变系数 3式用于求和时拆项(两项之和或者差),然后合并,28,组合恒等式变下项求和,证明公式4. 方法:二项式定理或者组合分析. 设S=1,2,n,下面计数S 的所有子集. 一种方法就是分类处理,n元集合的 k子集个数是,根据加法法则,子集总数是,另一种方法是分步处理,为构成 S 的子集A,每个元素有 2 种选择,根据乘法法则,子集总数是2n.,29,恒等式求和变系数和,证明方法: 二项式定理、级数求导 其他组合恒等式代入,30,证明公式6 (二项式定理+求导),31,证明公式7 (已知

14、恒等式代入),32,恒等式变上项求和,证明 组合分析. 令S=a1, a2, , an+1为n+1元集合. 等式右边是 S 的 k+1子集数. 考虑另一种分类计数的方 法. 将所有的k+1元子集分成如下n+1类: 第1类:含a1, 剩下 k个元素取自a2,an+1,第2类:不含a1,含a2, 剩下k个元素取自 a3, , an+1, 不含a1, a2, , an, 含an+1,剩下k个元素取自空集,由加法法则公式得证,33,恒等式乘积转换式,证明方法:组合分析. n 元集中选取 r 个元素,然后在这 r 个元素中再选 k个 元素. 不同的 r 元子集可能选出相同的 k子集,例如 a, b, c

15、, d, e a, b, c, d b, c, d b, c, d, e b, c, d 重复度为: 应用:将变下限 r 变成常数 k,求和时提到和号外面.,34,恒等式积之和,关系,证明思路:考虑集合A=a1,a2,am,B=b1,b2,bn. 等 式右边计数了从这两个集合中选出r个元素的方法. 将这 些选法按照含有A中元素的个数 k 进行分类,k=0,1,r. 然后使用加法法则.,35,组合恒等式解题方法小结,证明方法: 已知恒等式带入 二项式定理 幂级数的求导、积分 归纳法 组合分析 求和方法: Pascal公式 级数求和 观察和的结果,然后使用归纳法证明 利用已知的公式,36,非降路径

16、问题,基本计数模型 限制条件下的非降路径数 非降路径模型的应用 证明恒等式 单调函数计数 栈的输出,37,基本计数模型,(0,0) 到 (m,n) 的非降路径数:C(m+n, m) (a,b) 到 (m,n)的非降路径数: 等于 (0,0) 到 (ma,nb) 的非降路径数 (a,b) 经过 (c,d) 到 (m,n) 的非降路径数:乘法法则,38,限制条件的非降路径数,从(0,0)到(n,n)不接触对角线的非降路径数 N N1:从(0,0) 到 (n,n) 下不接触对角 线非降路径数 N2:从(1,0)到(n,n1) 下不接触对角 线非降路径数 N0: 从(1,0)到(n,n1) 的非降路径

17、数 N3: 从(1,0)到(n,n1) 接触对角线的 非降路径数 关系: N=2N1=2N2=2N0 N3,39,一一对应,N3: 从(1,0)到(n,n1) 接触对角线的 非降路径数 N4: 从(0,1)到(n,n1) 无限制条件的 非降路径数 关系: N3=N4,40,应用证明恒等式,例2 证明 证: 计数(0,0)到(m+nr,r) 的非降路径数 按照 k分类,再分步. (0,0)到(mk,k)路径数, (mk,k)到(m+nr,r)的路径数,41,应用单调函数计数,例3 A=1,2,m, B=1,2,n, N1:B上单调递增函数个 数是(1,1)到 (n+1,n) 的非降路径数 N:

18、B上单调函数个数 N=2N1 N2: A到B单调递增函数个 数是从(1,1)到 (m+1,n) 的非降路径数 N: A到B的单调函数个数,N =2N2 严格单调递增函数、递减函数个数都是C(n,m),42,函数计数小结,A = 1, 2, , m, B = 1, 2, , n f: AB,43,应用栈输出的计数,例4 将1,2,n按照顺序输入栈,有多少个不同的输出序列? 解:将进栈、出栈分别记作 x,y, 出栈序列是n个x,n个y的排列,排列中任何前缀的 x 个数不少于y 的个数. 等于从 (0,0) 到 (n,n) 的不穿过对角线的非降路径数. 实例:n=5 x, x, x ,y, y, x, y, y, x, y 进,进,进,出,出,进,出,出,进,出 3, 2, 4, 1, 5,44,应用栈输出的计数(续),N: 堆栈输出个数 N:(0,0)到(n,n)不 穿过对角线的 非降路径数 N0:(0,0)到(n,n)的 非降路径总数 N1:(0,0)到(n,n)的 穿过对角线的 非降路径数 N2:(1,1)到(n,n) 的非降路径数. 关系:N=N =N0N1, N1=

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论