递推法解排列、组合及概率问题

递推法解排列、组合及概率问题

ID:21189034

大小:191.00 KB

页数:4页

时间:2018-10-20

递推法解排列、组合及概率问题_第1页
递推法解排列、组合及概率问题_第2页
递推法解排列、组合及概率问题_第3页
递推法解排列、组合及概率问题_第4页
资源描述:

《递推法解排列、组合及概率问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、递推法解排列、组合及概率问题刘东林(广东省普宁市第二中学数学组515300)排列组合在高中数学旧教材中是相对独立的内容,而在高中数学新教材中排列组合是概率及统计的基础,因此,排列组合内容在高中数学新教材中的位置也变得相对重要起来了。而概率是新教材中新增加的内容,也是初等概率论中最基本的内容。在历年的高考中,排列组合知识多是选择题或填空题,概率一般是一个解答题,这些题的题型繁多,解法独特,因此得分率普遍较低。本文试图用递推法来解决几类常见的排列组合及概率问题。1走楼梯问题例1:欲登上第10级楼梯,如果规定每步只能跨上一级或两级,则不同的走法共有()(A)34种(B)55种(C)89种(D)

2、144种解法1:分类法:第一类:没有一步两级,则只有一种走法;第二类:恰有一步是一步两级,则走完10级要走9步,9步中选一步是一步两级的,有种可能走法;第三类:恰有两步是一步两级,则走完10级要走8步,8步中选两步是一步两级的,有种可能走法;依此类推,共有=89,故选(C)。解法2:递推法:设走级有种走法,这些走法可按第一步来分类,第一类:第一步是一步一级,则余下的级有种走法;第二类:第一步是一步两级,则余下的级有种走法,所以,又易得,由递推可得,故选(C)。显然,递推法的关键是按照某种标准找出递推关系式,并求出取第一个值(或前几个值)时的各项,然后代入递推关系式,求出题中要求的值。当然

3、,我们也可以由找出的递推关系,求出通项,但对于选择填空题,我们不必大动干戈的去求通项,因为这样太浪费时间与精力。2更列问题把个元素排成一列,所有元素各有一个不能占据的指定位置,且不同元素不能占据的指定位置也不同,我们把满足这种条件的一个排列叫做这些元素的一个更列。例2:五个人排成一列,重新站队时,各人都不站在原来的位置上,那么不同的站队方式共有()(A)60种(B)44种(C)36种(D)24种解:首先我们把人数推广到个人,即个人排成一列,重新站队时,各人都不站在原来的位置上。设满足这样的站队方式有种,现在我们来通过合理分步,恰当分类找出递推关系:第一步:第一个人不站在原来的第一个位置,

4、有种站法。4第二步:假设第一个人站在第2个位置,则第二个人的站法又可以分为两类:第一类,第二个人恰好站在第一个位置,则余下的个人有种站队方式;第二类,第二个人不站在第一个位置,则就是第二个人不站在第一个位置,第三个人不站在第三个位置,第四个人不站在第四个位置,……,第个人不站在第个位置,所以有种站队方式。由分步计数原理和分类计数原理,我们便得到了数列的递推关系式:,显然,,再由递推关系有,,故应选(B)我们再来看一道全国高考题:例3:同室4人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送出的贺年卡,则4张贺年卡不同的分配方式共有()(1993年全国高考试题)(A)6种(B)9种(C

5、)11种(D)23种此题就是更列问题,即为例2中的,故选(B)3染色问题例4:用4种不同颜色涂四边形的4个顶点,要求每点染一种颜色,相邻的顶点染不同的颜色,则不同的染色方法有()(A)84种(B)72种(C)48种(D)24种解:我们先把这个题目推广:用种不同颜色给边形的个顶点染色(其中,且为常数),每点染一种颜色,相邻的顶点染不同的颜色,不同的染色方法有多少种?设不同的染色方法有种,现在我们来通过合理分布,恰当分类找出递推关系:第一步:染,有种染法;第二步:染,有种染法;同理,染均有种染法,最后染,如果仅考虑与不同色,则仍有种染法,相乘得种染法,但要去掉与同色的染法数,此时可将与合并看

6、成一个点,得出需要排除的染法数为,所以有,显然,。又本题中,颜色数,所以递推关系为:,又,所以(种),故选(A)。用这种方法,不难求出下面两道2003年的高考题:例5:如图1,一个地区分为5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色,现有四种颜色可供选择,则不同的着色方法共有种。(以数字作答)(2003年全国高考试题)例6:某城市在中心广场建造一个花圃,花圃分成6个部分(如图2),现要栽种4种不同颜色的花,每部分栽种一种且相邻部分不能栽种同样颜色的花,不同的栽种方法共有种。(以数字作答)(2003年天津理科高考试题)1345图12123456图24我们来看例5,其中2、3、4

7、、5四个区域围成一个四边形,因此可以把它们看成是一个四边形的4个顶点,而区域1就是这个四边形对角线的交点。第一步,先涂区域1,有4种涂法,由于区域1跟其余四个区域都相邻,因此涂1的颜色不能用来涂其余的四个区域,因此第二步相当于用3种颜色来涂一个四边形的四个顶点,由例4不难得出,,所以,,由分步计数原理,得出共有种涂法。同理,不难得出例6的答案为120种。4传球问题例7:甲、乙、丙、丁四人相互传球,第一次甲传给乙、丙、丁中的任一人,第

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。