排列组合题解法

时间:2023-12-25 点赞:41350 浏览:75825 作者原创标记本站原创

该文为贺年卡方面毕业论文的格式范文,与排列组合题解法相关硕士论文选题,可作为论文题目专业贺年卡论文写作研究的大学硕士与本科毕业论文开题报告范文和职称论文参考文献资料。免费下载教你怎么写贺年卡及中学数学及排列方面的优秀学术论文范文。

中图分类号:G4

排列组合应用题是现行中学数学教学大纲的一项重要内容.递推法是解排列组合应用题的一个重要方法,许多问题用这一方法来解显得精练简洁,并往往能得到解决同类问题的通用解法或得到一个应用较广的递推公式.

(1994年高考题)同室4人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送出的贺年卡,则4张贺年卡不同的拿法有

A.6种 B.9种 C.11种 D.23种

下面介绍包括“构造法”在内的5种解法.

1.构造法:构造法的关键是针对问题的实际意义,构造一个三棱锥,记这4个人为A,B,C,D,每人所写的贺年卡对应记为a,b,c,d(如图),设法把每个人和他写出的贺年卡同放在三棱锥的一个顶点上,则4个顶点刚好分配完.规定每条棱表示2种顺序拿法.例如棱AB表示A拿b或B拿a.根据题意全部拿法分为两类:第一类是4人中有2人交换着拿,例如A拿b,B拿a,这时另2人也只能交换着拿,这种拿法在三棱锥中表示为成异面直线关系的两条棱,而这样的棱在三棱锥有3对,所以这类拿法有3种.第二类是4人顺序循环拿,例如A拿b,B拿c,C拿d,D拿a(或反序循环:A拿d,D拿c,C拿b,B拿a),这在图中表示为4条首尾顺次相接的棱构成的空间四边形ABCD.而余下的2条棱也恰好为1对“异面直线棱”.由于三棱锥有3对这样的“异面直线棱”,所以图有3个不同的空间四边形,而每个四边形有2种循环序表示2种拿法.故第二类拿法共有3×2等于6种.因此,两类拿法共表示9种不同的分配方式.


2.列举法:当问题比较简单时可做具体分析.

设4人A,B,C,D,写的贺年卡分别记为a, b, c, d.

可从第一个人A考虑起,当A取b时,其他三人可

取的情况见右表.由表可知A取b 时有三种分配方

法.同样A取c, d 时也各有三种方法.这样由A的

取法可分三类,由加法原理,得 3+3+3等于9(种)

3.直接法:用乘法原理.即让四人依次拿一张贺年卡,分四步进行.

第一步:A先拿有3种方法;第二步:叫被A取走他写的贺年卡的人再拿,也有三种取法;第三步:剩下的两张贺年卡中至少有一张是还没拿的两个人中的某个人写的,让这个人拿只有一种拿法;第四步:一张贺年卡一个人只有一种拿法.

由乘法原理得:3×3×1×1等于9(种)

4.间接法:先不考虑要求,四个人拿四张不同的贺年卡,每人一张的方法数为P44等于24种,其中不合要求的情况有:

(1)四个人均拿到自己写的贺年卡的情况:这种情况有1种.

(2)有且只有两个人拿到自己写的贺年卡的情况:有2×1等于6种.

(3)有且只有一个人拿到自己写的贺年卡的情况:有1×2等于8种.

故共有:24-1-6-8等于9(种)

“构造法”运用巧妙,但这种解法比较难思考,有较大的局限性,也比较难进一步推广,假如把4个人改为5个人、6个人或更多的,用“构造法”恐怕很复杂.经深入研究和探讨,发现用递推的思想解这道题,可以找到一般的递推关系,并可以利用这种递推关系解决更为复杂的一些问题.

5.递推法

我们先把文中题目所涉及的问题换一种说法.即把1,2,3,4四个数字排成一排,使得I不能排在第I位,I等于1,2,3,4.求符合条件的排列数.

我们再把这问题推广为一般的模式.把1,2,3,等,n这n个数字排成一排,使得I不能排在第I 位,I等于1,2,3,等,n.求符合条件的排列数.

设n个数字的这种排列数为Dn,若能推出Dn的通项公式或递推公式,那么上面的问题就迎刃而解且能解决一些较为复杂的问题.利用递推的数学思想分析如下:

容易知道D1等于0,D2等于1,n≥3时,考虑1,2,3,等n这n个数字的所有符合条件的排列数(以下称为n个元素的错位排列数).我们根据在排列中的第一位的数字是2,3,等,n,而将这些排列分成n-1类,显然每一类的排列数相等.令dn表示第一位是2的排列数.那么有 Dn等于(n-1)dn (1)

考察在dn中的排列,它们都是2I2 I3等 In的形式,其中Ij≠j,j等于2,3,等,n.我们进一步把这些排列分成两类,称I2等于1的为第一子类,并把其中的排列个数记为dnˊ;称I2≠1的为第二子类,它的排列个数记为dn〞,那么有 dn等于 dnˊ+ dn〞 (2)

在第一子类中的排列具有21 I3I4等 In的形式,Ij≠j,j等于3,4,等,n.所以dnˊ就是3,4,等,n,这n-2个元素的错位排列数Dn-2.在第二子类中的排列具有2I2 I3等 In的形式,其中I2≠1,Ij≠j,j等于3,4,等,n.所以dn〞就是1,3,4,等,n,这n-1个元素的错位排列数Dn-1.因此得到 dn 等于 Dn-2 +Dn-1 (3)

把(3)代入(1)得Dn等于(n-1)(Dn-2 +Dn-1)

于是我们得到递推公式 (4)

Dn等于(n-1)(Dn-2 +Dn-1)

D1等于0,D2等于1

解法五:利用递推公式(4),我们有

D3等于(3-1)(D1 +D2)等于2×(0+1)等于2,

D4等于(4-1)(D2 +D3)等于3×(1+2)等于9,

故有9种方法.

显然,与前述数种方法相比,递推法更具有一般性,利用递推公式(4),我们还可以较易地解决一些中学里常见的排列组合题.

例1.设有编号为1,2,3,4,5,6的六个球和编号为1,2,3,4,5,6的六个盒子,现将这六个球放入这六个盒内,要求每个盒子内投放一个球,并且恰好有两个球的编号与盒子编号相同,试求这样投放方法的种数.

解:从编号为1,2,3,4,5,6的六个球中任选两个的方法数为C62.我们把选出的两个球放在与它编号相同的盒子里,剩下的四个球的投放方法满足递推公式(4)的条件.所求的投放方法数为

C62×D4等于15×9等于135(种).

例2.八人坐成一排,现要调换五个人的位置,其余三个人位置不动,共有( )种调换方法.

解:五个人调换位置,即五个人都不坐在原来的位置上.所以任意五个人调换位置的方法数D5满足递推公式(4)的条件.

由例1知D5等于44.

∴共有C85×D5等于56×44等于2464(种)

另一方面,掌握递推的数学思想对解某些其它应用性问题也是很有帮助的.例如下面的问题用递推的思想来解答将很明了.

综观上述,可见运用递推法求解某些排列组合应用题,思路明了,并可以找到一般的递推关系用于解决同类问题,有助于培养逻辑思维能力.

相关论文

对排列组合中一类传球问题的

本论文是一篇荷叶相关论文总结,关于对排列组合中一类传球问题的相关学年毕业论文范文。免费优秀的关于荷叶及青蛙及池塘方面论文范文资料,适。

一题多解法

这是一篇关于贺年卡相关专科毕业论文范文,与一题多解法相关专升本毕业论文开题报告。是论文题目专业与贺年卡及教育改革及中学数学教学改革。

几何题的复数解法

该文为复数方面学年毕业论文范文,与几何题的复数解法相关专科论文选题,可作为论文题目专业复数论文写作研究的大学硕士与本科毕业论文开题。

化学中考物质鉴别类型题的解法

本文关于溶液及物质及试剂方面的免费优秀学术论文范文,溶液类论文范本,与化学中考物质鉴别类型题的解法相关在职研究生毕业论文范文,对不。

如何运用正交分解法解力学题

本论文是一篇加速度方面毕业论文选题,关于如何运用正交分解法解力学题相关本科论文范文。免费优秀的关于加速度及分解及正交方面论文范文资。