【重、难点解析】教学设计.doc

上传人:创****公 文档编号:1473937 上传时间:2019-03-01 格式:DOC 页数:12 大小:310KB
下载 相关 举报
【重、难点解析】教学设计.doc_第1页
第1页 / 共12页
【重、难点解析】教学设计.doc_第2页
第2页 / 共12页
【重、难点解析】教学设计.doc_第3页
第3页 / 共12页
【重、难点解析】教学设计.doc_第4页
第4页 / 共12页
【重、难点解析】教学设计.doc_第5页
第5页 / 共12页
点击查看更多>>
资源描述

1、【重、难点解析】(一)排 列1无重复元素的排列(线排列)从 n 个元素的集合 S 中选出 r 个元素的排列,称为 r-排列。其个数为:)!()1()2(1),( nnrP从 n 个元素的集合 S 中选出 n 个元素的排列,称为全排列。其个数为:!),(p2无重复元素的圆排列(环排列)从 n 个元素的集合 S 中选出 r 个元素排列成圆环,称为 r-圆排列。其个数为:)!(),(rnP公式解释 n 个元素的 r-排列有 个,而其中的任何一个排列 的顺, ra,21序移动: 共 r 个。因此 n 个元素的 r-圆排11214312 ,;,;, rr aaa列数为:)!(),(rnrP当 n=r 时

2、,n 个元素的集合 S 的全圆排列数为: )!1(),3重复排列设 ,则 S 所有元素的不同的 n-重复排列数为:,21kbnbnS!)(21kn 设 ,则 S 的 r-可重复全排列数为 nr。,21nbbS(二)组 合1无重复元素的组合数从 n 个元素的集合 S 中选出 r 个元素组成一组,称为 r-组合。其个数为: )!(!)1()2(1!),( nrnnrPCk 2 n个元素的集合 S的 r-可重复组合数从 n 个元素的集合 S 中选出 r 个元素的 r-可重复组合数,记作 F(n,r):1),(nnCF公式解释 设有 n 个元素 ,与自然数 1,2,n,建立一一对应关系。,21nbS所

3、考虑的任何 r-组合可以看作是一个 r 个数的数组(b 1, b2, bn) 。由于是数组,不妨认为 bi 按大小顺序排列,相同的 bi(可以重复)连续地排在一起,如按 b1b 2b rn排列。令 di= bi+i-1(i=1,2,r),于是,1,21 rddr由于 最大可取 n,那么 最大可取 。有i in)1(,2121 rnrr从而将问题转化为求集合(1,2,,n+r-1 )的 r-组合问题,易见,有一种b 1, b2, br的取法,就有一种d 1, d2, dr的取法。它们一一对应。这样,允许重复地从 n 个不同元素中取 r 个元素的组合数和不允许重复地从 n+r-1 元素中取 r 个

4、元素的组合数是相同的。故有公式1),(nrrnCf3组合恒等式(1) 1rnrnC(2) nknnn C0210 2(3) nkknnnnC0210 )1()1((4) rkknr0)((5) nknC112(6) 12nmnn C(7) ki knmikni0(三)筛法原理筛法原理也称为容斥原理,又称包含排列原理。筛法原理是用以解决集合的元素计数个数、概率中一般和事件的概率计算公式。在计数问题中,常采用间接计算一个集合的元素个数,比直接计算容易些。如,某单位集会,共有 187 人到会。由于某种需要,想知道男来宾的人数。但是,女来宾人数易计算出来。二者之差即为男来宾数。在集合计数中: | |

5、| | 3213231321 212121 AAASA 推而广之: jijimiiS| 12kji rkjiA)1(| |)1(|222mmii iir r设 S 是有 N 个元素的集合,A 1 是 S 的具有性质 P(1)的子集,其元素个数| A1|记作N1;A 2 是 S 的具有性质 P(2 )的子集,其元素个数|A 2|记作 N2; 是 S 的同时具21ii有性质 P(i 1)和 P(i 2)的子集,其元素个数| |记作 ;21iiA21,i是 S 的同时具有性质 P(i 1)P(i 2) P(i r)的子集,其元素个数|riii21|记作 ; 的不具有 P(i ) (i=1,2,m)r

6、iii A21 riiN,21 Sm是2任何性质的子集,其元素个数| |记作 N(0) 。于是上面式改写成:A miiir iijiimiNkk ,21, ,1)()(02121 3212121 这正是本章第 3 节的公式(4-3-1) 。(四)递推公式与分部1初等几何问题平面上 n 条一般直线(任何两直线不平行,任何三条直线不共点) ,将平面分成几个部分(区域)?用 Pn 表示 n 条直线所分平面的部分数(区域数) ,有:当 n=0 时,没有直线,平面是一个整体,即;10P当 n=1 时,一条直线,将平面分成 2 个部分,即 ;001nP当 n=2 时,2 条直线,将平面分成 4 个部分,即

7、;2112nPP当 n=3 时,3 条直线,将平面分成 7 个部分,即如图(4-7);3223n=0 n=1 n=2 n=3图 4-7 直线分割平面示意图依此类推,一般地,有公式 Pn1且 nPn1 12)()1(2(321)(2 nn2递推公式与斐波那契( Fibonacci)数列例 有一个人把一对(雌雄各一)的大兔子放在自家的院子里饲养,他想知道一年后能生出多少对兔子,假定这对大兔子每月可生雌雄各一的一对小兔子,而新生的一对小兔子经过一个月可以长成大兔子,以后也是每月产雌雄各一的一对小兔子。问:一年后(也就是到第 13 个月开始)能生出多少对兔子?解 由题设知,第一个月有一对兔子,第二个月

8、开始时有两对兔子(大、小兔子各一对) ,第三个月开始,新出生的小兔子刚长成大兔子还不能产仔,只有原来的一对大兔子产仔一对,共有 2+1=3 对兔子,它是第一、第二两个月兔子对数的总和。第四个月开始时,除第三个月出生的一对兔子不产仔外,其余的两对兔子都能产仔,共产小兔子 2 对,与第二个月兔子的对数相同,因此共有 2+3=5 对,它等于第二、第三两个月兔子对数的总和。一般地,可这样考虑:我们用 f(n)表示第 n 个月初兔子的对数。因为第 n 个月开始时,除第 n-1 个月新生的兔子不能产仔外,其余的兔子,即在第 n-2 个月时已有的兔子都能产仔,而第 n-2 个月共有兔子数为 f(n-2)对,

9、故第 n 个月新生的小兔子共有 f(n-2)。又因为第 n 个月的兔子是由两部分组成,一部分是在第 n-1 个月时已有的兔子,共f(n-1)对;另一部分是第 n 个月新生的小兔子,有 f(n-2)对。因此,第 n 个月共有:f(n)= f(n-1)+ f(n-2) 公式给出了连续多年兔子数之间的关系,我们称公式为递推公式。我们已经知道:f(1)=1 ,f(2)=2,当 n3 时,利用公式可以计算出 f(n)的值如下:f(3)=1+2=3 f(4)=3+2=5f(5)=5+3=8 f(6)=8+5=13f(7)=13+8=21 f(8)=21+13=34f(9)=34+21=55 f(10)=5

10、5+34=89f(11)=89+55=144 f(12)=144+89=233f(13)=233+144=377解得:一年后(即第 13 个月)有兔子 377 对。若规定 f(0)=1,f(1) =1,由递推公式可得到数列1,1,2,3,5,8,13,21,34,55,89,144,233,377,数学界把这个数列叫做斐波那契数列,以纪念最先得到这个数列的数学家斐波那契(Leon ardo Fibonacci),(约 11701250),是意大利数学家 。由于这个数列在数学、物理、化学领域经常出现,又具有很奇特的性质,所以美国数学会每三个就出版一本专门对这种数列进行研究的季刊,称为斐波那契季刊

11、 。递推公式的另一解释为:设 n-样本 集合,若 只能取 0 或 1,求不),(21na i允许连续出现两个 0 的样本个数,用 f(n)表示。记 f(0)=1,当 n=1 时,即 1-样本 取 0 或 1,有 2 个样本:(0) , (1) ;故 f(1)=2;1)(a当 n=2 时,即 2-样本 。有样本(11) , (01) , (10) ,故 f(2)=3;2当 n=3 时,即 3-样本( ) 。有样本(111) , (101) , (110) , (011) , (010) 。即,31a1=1 时,样本个数为 f(n-1)=f(2)=3;a1=0 时,a 2 只能取 1,样本个数为

12、f(n-2)=f(1)=2故 f(3)=5=f(2)+f(1)=f(n-1)+f(n-2)当 n=4 时,即 4-样本(a 1a2a3a4) 。有样本(1111), (1011) , (1010) , (1101) ,(1110) , (0111) , (0110) , (0101) 。故 f(4)=8=f(3)+f(2)=f(n-1)+f(n-2)以此类推,同样能得到递推公式f(n)=f(n-1)+f(n-2)3扰乱排列设 S=1,2,,n, (a 1,a2,,a n)和(b 1,b2,bn)是 S 的两个排列,对于一切i,i=1,2,n,有 ,则称(b 1,b2,bn)是(a 1,a2,,

13、 an)的一个扰乱排列,或称错位ii排列、移位排列。即每个数码都不在原来位置上的排列。如(4321)和(3412)都是(1234)的扰乱排列。而(1324)和(1432)都不是(1234)和扰乱排列,因为不是每个数码都不在原位置。用 D(n)表示 n 个元素的扰乱排列的个数。设 A 是 S 的所有排列的集合: !|nA令 为第 i 个元素定位在 i 的 S 的所有排列。 表示第 i 个元素定位在 i 的的排列i |i数,i=1,2,n。|)(1inAD因为元素 i 定位在 i 的所有排列数为(n-1)! ,即 =(n-1)!(i=1,2,,n)|iS 的两个元素的定位排列数为 )!2(|nji

14、S 的 k 个元素的定位排列数为 |1kAik由筛法原理: |)(| 1211 injininin ACCA!0)!()!( 1n所以 )(432)D !1!1! nn容易证明: )2()()(Dn4定位排列设 S 是一个排列(a 1,a2,,a n) ,如果有 r 个 ai=i 排列,则称为 S 的 r 定位排列。如 S 的一个排列(1234) ,则(1243)和(1432)是 S 的一个 2 定位排列,而(1342)不是 S 的 2 定位排列,只是 1 定位排列。S 是 r 定位排列数用 N(r )表示。因为有 r 定位排列,剩余 n-r 是扰乱排列,有 D(n-r ).而 n 个元素选

15、r 个的方式有个。rnC于是 n 个元素的集合 S 的 r 定位排列数为:)!(1)!4132!1()() rnrnDr 5从 n个数码的集合中取出 k个数码,不出现两个连续数码的个数设 S 是 n 个数码1,2,n的集合,从 S 中取出 k 个数码,不出现有 2 个连续数码的个数是knCf1),(当 n,1 视为连续数时,从 S 中取出 k 个数码,不出现有 2 个连续数码的个数为:kng),(6数 Un的计算niin aCIJper21)(其中 J 是元素全为 1 的 n 阶方阵,I 是 n 阶恒等矩阵(单位矩阵) ,C 是上次对角线为1,即 ,其余元素为 0 的 n 阶方阵: 表示矩阵)

16、(23naa niia21J-I-C 的所有不同行不同列的 n 个元素乘积之和。其中 i1 不能取 1,2; i2 不能取 2,3;i n 不能取 n,1。显然 的值要么是 1,要么是 0。nii21或用下公式计算:)!2(,)!(!12ngCUnn0,13,g其中 (见教材本章定理 4.7) 。knk),(7分 部分部就是将正整数表成若干个正整数之和。分 出 的 正 整 数 不 能 重 复不 可 重 复 现分 出 的 正 整 数 可 重 复 出可 重 复无 序 部 分 分 出 的 正 整 数 不 能 重 复不 可 重 复 现分 出 的 正 整 数 可 重 复 出可 重 复有 序 分 部分 部

17、 现以正整数 4 的分部为例,说明各个概念,见下表。表 4-1 4 的分部表有 序 分 部 无 序 分 部 备 注不允许重复 4=4,4=1+3,4=3+1 4=4,4=3+1允许重复 4=44=1+3, 4=3+14=2+2, 4=2+1+14=1+2+1,4=1+1+24=1+1+1+14=44=1+34=2+2, 4=2+1+14=1+1+1+1在一个分部中数字重复出现设 n 是正整数,则不定方程),21,0(21 kixxik 的正整数解就称为 n 的分部。如表 4-1 中,正整数 4 的有序不重复分部有 3 个;无序不重复分部有 2 个;有序重复分部有 8 个,无序重复分部有 5 个

18、。我们着重讨论允许重复的分部。(1)n 的可重复的 k 个有序正整数解的个数不定方程 的 k 个可重复的有序正整数解的),21,0(21ixxik 个数,记作 Pk(n),有:1)(knkCP举例验证。如 n=7:k=1,即 7 表成 1 个正整数之和,显然 x1=7.则06)(knCPk=2,即 7 表成 2 个正整数之和: ,有 2+5,5+2,4+3,3+4,6+1,1+6 共7216 个,则 162)7(knk=3,即 7 表成 3 个正整数之和: ,有7321x1+1+5, 1+5+1,5+1+1,2+1+4,2+4+1,1+2+4,1+4+2,4+1+2,4+2+1 ,3+3+1,

19、3+1+3,1+3+3 ,2+2+3,2+3+2,3+2+2共 15 个,则126315)7(knCPk=4,即 7 表成 4 个正整数之和: ,有:7432xx1+1+1+4,1+1+4+1,1+4+1+1,4+1+1+1,1+1+2+3,1+1+3+2,1+2+3+1 ,1+3+2+1,2+3+1+1, 3+2+1+1,1+2+1+3,1+3+1+2,2+1+3+1,3+1+2+1,2+1+1+3 ,3+1+1+2,1+2+2+2,2+1+2+2,2+2+1+2,2+2+2+1共 20 个。则 136420)7(knCPk=5,即 7 表成 5 个正整数之和: ,有:754321xx1+1

20、+1+1+3,1+1+1+3+1,1+1+3+1+1,1+3+1+1+1,3+1+1+1+1,1+1+2+1+2,1+2+1+1+2,2+1+1+1+2,2+1+1+2+1 ,2+1+2+1+1 ,2+2+1+1+1,1+2+2+1+1,1+1+2+2+1,1+1+1+2+2,2+1+1+1+2,共 15 个,则14651)7(knCPk=6,即 7 表成 6 个正整数之和: ,有:7654321 xx1+1+1+1+1+2,1+1+1+1+2+1, 1+1+1+2+1+1, 1+1+2+1+1+1, 1+2+1+1+1+1, 2+1+1+1+1共 6 个,则 1566)(knCPk=7,即

21、7 表成 7 个正整数之和: ,只有7654321 xxx1+1+1+1+1+1+1共 1 个。 1567)(knCP(2)n 的可重复的 k 个无序正整数解的个数不定方程 个可重复的无序正整数解的个kixxik 的),21,0(21 数,仍记作 ,有)(PkkiknP1)()(易知, 。0,)(,nk时当举例验证。如:当 n=1 时,k=1,即 1=1,所以 P1(1)=1。当 n=2 时,k=1,即 2=2,所以 P1(2)=1;k=2,即 2=1+1,所以 P2(2)=1。当 n=3 时,k=1,即 3=3,所以 P1(3)= P 1(2)=1 ; k=2,即 3=1+2,所以 P2(3

22、)= P 1(1)+ P 2(1)=1 ;k=3,即 3=1+1+1,所以 P3(3)=1。 当 n=4 时,k=1,即 4=4,所以 P1(4)= P 1(3)=1 k=2,即 4=2+2 或 1+3,所以 P2(4)= P 1(2)+ P2(2)=1+1=2k=3,即 4=3+1,所以 P3(4)= P 1(1)+ P 2(1)+ P3(1)=1+0+0+1 k=4,即 4=1+1+1+1,所以 P4(4)=1。当 n=5 时,k=1,即 5=5,所以 P1(5)= P 1(4)=1 k=2,即 5=1+4 或 2+3,所以P2(5)= P1(3)+ P 2(3)=1+1=2k=3,即 5

23、=2+2+1,3+1+1,所以P3(5)= P1(2)+ P 2(2)=1+1=2k=4,即 5=1+1+1+2,所以P4(5)= P1(1)+ P 2(1)=1+0=1k=5,即 5=1+1+1+1+1,所以 P5(5)=18用母函数计算组合问题母函数又叫生成函数。它是解决计数问题的一个有力工具,我们先看两个例子。例 1 袋内有 4 个红球,3 个白球,2 个黑球。从袋中任取 4 个球,问有多少种不同的取法。解 考虑如下表达式: )1)(1)() 232432 xxxxf961在第 1 个括号中 xk 的指数 k 可认为代表 k 个红球,第 2 个括号中 xk 的指数 k 可认为代表 k 个

24、白球,第 3 个括号中的 xk 的指数 k 可认为代表 k 个黑球。如果用 ,那么kii个 括 号 里 的表 示 第)(4)3(2)1(x就是一种(取法)方案,它表示取 1 个红球,2 个白球,1 个黑球的一种取法;而40)3(4)(xx也是一种方案,它表示取红球 4 个,白球、黑球都不取的一种取法。每次取 4 个球,所有不同的取法个数就是 f(x)的展开式中 x 的系数 11。例 2 若有 1g,2g,3g,4g 的砝码各一枚,问能称出哪几种重量?有几种可能的方案? 1)(1)(432xx 10987652xx这里第 1 个括号中 x 的指数 1 可认为代表 1g 的砝码 1 枚,第 2 个

25、括号中 x 的指数 2 可认为代表 2g 的砝码 1 枚,余类推。在展开式中:如 2x5 的指数 5 表示可称 5g 重物,系数 2 则表示称 5g 重物有 2 种方案(因为 ,即用 2g 与 3g 砝码各一枚,可称出 5g 的重量;用 1g 和 4g 的4352砝码各一枚,也能称出 5g 的重量) 。从展开式知道,用 1g,2g,3g 和 4g 的砝码各一枚,能称出 1g 和 10g 的重量。展开式中各项的系数,便是方案数。下面考虑多重集。设 ,21nakakA它表示集合 A 有 。n个个个 ,21设想有标号分别为 1,2,n 的盒子在第 i 个盒子里放有 个球 。ik),21(nia所谓多

26、重集 A 的一个 r-组合,就是指由 A 中的可重复的 r 个元素构成的一个组合,那么多重集 A 的一个如下的 5-组合: 321a则对应于从第 1 个盒子里取出 2 个球,第 2 个盒子里取出 2 个球,第 3 个盒子里取出 1 个球的一种取法;同样,多重集 A 的一个 7-组合:431对应于从第 1 个盒子里取 3 个球,第 3 个盒子里取 2 个球,第 4 个盒子里取 2 个球的一种取法。反之,从第 1 个盒子里取 1 个球,第 2 个盒子里取 3 个球,第 4 个盒子里取 1 个球,则对应于多重集 A 的一个 5-组合。421a所以,多重集 A 的 r-组合数就等于从 n 个盒子里一共取出 r 个球的不同取法数。如果 x 代表球, 代表从第 1 个盒子里取出 i1 个球, 代表从第 2 个盒子里取出 i2 个球,并且1ix 2ix满足条件riin21 ),1,(njkij 那么项

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育教学资料库 > 课件讲义

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。