计数原理与排列组合(教师用)Word文档格式.doc
《计数原理与排列组合(教师用)Word文档格式.doc》由会员分享，可在线阅读，更多相关《计数原理与排列组合(教师用)Word文档格式.doc（19页珍藏版）》请在冰点文库上搜索。
种不同的方法
说明：
1）各类办法之间相互独立,都能独立的完成这件事，要计算方法种数,只需将各类方法数相加,因此分类计数原理又称加法原理
2）首先要根据具体的问题确定一个分类标准，在分类标准下进行分类，然后对每类方法计数.
例1、在填写高考志愿表时，一名高中毕业生了解到A、B两所大学各有一些自己感兴趣的强项专业，具体情况如下：
A大学：
生物学化学医学物理学工程学
B大学：
数学会计学信息技术学法学
如果这名同学只能选一个专业，那么他共有多少种选择呢？
A村
B村
C村
北
南
中
问题2.如图,由A村去B村的道路有3条，由B村去C村的道路有2条。
从A村经B村去C村，共有多少种不同的走法?
二、分步计数原理
完成一件事，需要分成n个步骤。
做第1步有m1种不同的方法，做第2步有m2种不同的方法，……，做第n步有mn种不同的方法，则完成这件事共有
1）各个步骤相互依存,只有各个步骤都完成了,这件事才算完成,将各个步骤的方法数相乘得到完成这件事的方法总数,又称乘法原理
2）首先要根据具体问题的特点确定一个分步的标准，然后对每步方法计数.
例2、设某班有男生30名，女生24名。
现要从中选出男、女生各一名代表班级参加比赛，共有多少种不同的选法？
例3、浦江县的部分电话号码是05798415×
×
后面每个数字来自0～9这10个数,问可以产生多少个不同的电话号码?
第二部分：
排列
一、问题引入
从甲、乙、丙3名同学中选出2名参加一项活动，其中1名同学参加上午的活动，另一名同学参加下午的活动，有多少种不同的选法？
问题2：
从1、2、3、4这4个数字中，每次取出3个排成一个三位数，共可得到多少个不同的三位数？
问题1和2的共同点是什么？
二、排列
1、对排列定义的理解.
定义：
一般地，从n个不同的元素中任取m（m≤n）个元素，按照一定顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列.
2、相同排列.
如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序也必须完全相同.
3、排列数.
从n个不同元素中取出m（m≤n）个元素的所有不同的排列的个数，称为从n个不同元素中取出m个元素的排列数.用符号表示.
且有：
正整数1到n的连乘积叫做n的阶乘，用表示，所以n个不同元素的全排列公式可以写成：
规定0!
=1，所以An0＝1。
注意：
例1、A，B，C，D四名同学重新换位（每个同学都不能坐其原来的位子），试列出所有可能的换位方法．
解：
假设A，B，C，D四名同学原来的位子分别为1,2,3,4号，列出树形图如下：
换位后，原来1,2,3,4号座位上坐的同学的所有可能排法有：
BADC，BCDA，BDAC，CADB，CDAB，CDBA，DABC，DCAB，DCBA.
练习2：
四人A、B、C、D坐成一排，其中A不坐在排头，写出所有的坐法．
例2设a∈N*，且a＜27，则（27－a）（28－a）…（34－a）等于（ ）
A．A27－a8B．A34－a27－aC．A34－a7D．A34－a8
解析：
8个括号是连续的自然数，依据排列数的概念，选D.
练习1：
解不等式：
A8m＋2＜6A8m.
原不等式可化为＜6·
，化简得m2－15m＋50＜0，
即（m－5）（m－10）＜0，解得5＜m＜10，又，即m≤6，所以m＝6.
计算
（1）；
（2）1！
＋2·
2！
＋3·
3！
＋…＋n·
n！
.（3）；
（4）.
[解析]
（1）方法一：
＝＝＝.
方法二：
＝＝＝＝.
n!
＝（2！
－1）＋（3！
－2！
）＋（4！
－3！
）＋…＋[（n＋1）！
－n！
]＝（n＋1）！
－1.
（3）＝＝1.
（4）＝·
（n－m）！
·
＝·
＝1.
例3、求证：
An＋1m－Anm＝mAnm－1.
[解析] 证法一：
An＋1m－Anm＝－
＝＝·
＝m·
＝mAnm－1.
练习：
求证：
An＋1n＋1＝An＋1n＝（n＋1）Ann
证明：
∵An＋1n＋1＝（n＋1）×
n×
（n－1）×
…×
3×
2×
1，An＋1n＝（n＋1）×
2，
（n＋1）Ann＝（n＋1）×
＝（n＋1）×
1，
∴An＋1n＋1＝An＋1n＝（n＋1）Ann.
巩固练习：
1、某年全国足球甲级（A组）联赛共有14个队参加，每队要与其余各队在主、客场分别赛一次，共进行多少场比赛？
2、
（1）从5本不同的书中选3本选给3名同学，每人各1本，共有多少种不同选法？
（2）从5种不同的书中买3本选给3名同学，每人各1本，共有多少种不同选法？
3、用0,1,2,3,4,5这六个数字可以组成多少个符合下列条件的无重复的数字？
（1）六位奇数；
（2）个位数字不是5的六位数；
（3）不大于4310的四位偶数．
[解题过程]
（1）方法一（直接法）：
第一步，排个位，有A31种排法；
第二步，排十万位，有A41种排法；
第三步，排其他位，有A44种排法．
故共有A31A41A44＝288个六位奇数．
方法二（排除法）：
6个数字全排列有A66个，
0,2,4在个位上的排列数有3A55个，
1,3,5在个位上且0在十万位上的排列数有3A44个，
故对应的六位奇数的排列数为
A66－3A55－3A44＝288（个）．
（2）方法一（排除法）：
0在十万位和5在个位的排列都不对应符合题意的六位数，这两类排列中都含有0在十万位和5在个位的情况．
故符合题意的六位数共有A66－2A55＋A44＝504（个）．
方法二（直接法）：
十万位数字的排法因个位上排0与不排0而有所不同，因此需分两类．
第一类，当个位排0时，有A55个；
第二类，当个位不排0时，有A41A41A44个．
故共有符合题意的六位数有A55＋A41A41A44＝504（个）．
（3）①当千位上排1,3时，有A21A31A42个．
②当千位上排2时，有A21A42个．
③当千位上排4时，形如40×
，42×
的各有A31个；
形如41×
的有A21A31个；
形如43×
的只有4310和4302这两个数，
故共有A21A31A42＋A21A42＋2A31＋A21A31＋2＝110（个）．
题后感悟：
排列问题的本质是“元素”占“位子”问题，有限制条件的排列问题的限制条件主要表现在某元素不排在某个位子上，或某个位子不排某些元素，解决该类排列问题的方法主要是按“优先”原则，即优先排特殊元素或优先满足特殊位子，若一个位子安排的元素影响到另一个位子的元素个数时，应分类讨论．
组合
问题3：
从3名同学中选出2名的可能选法是多少？
问题4：
区别问题1与问题3的不同点。
二、组合
1、组合定义：
从n个不同的元素中任取m（m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合.
排列与组合的联系与区别。
共同点：
两者都是从n个不同的元素中任取m（m≤n）个元素；
不同点：
排列与元素周期律的顺序有关，组合与元素的顺序无关。
只有元素相同且顺序相同的两个排列才是相同的，只要两个组合的元素相同，不论元素的顺序是否相同，它们都是相同的组合。
2、组合数：
从n个不同元素中取出m（m≤n）个元素的所有不同组合的个数，称为从n个不同元素中取出m个元素的组合数.用符号表示.
探究2：
从4个不同的元素中取出3个元素的排列与组合的关系？
从n个元素中取出m个元素的排列与组合的关系？
3、组合数公式：
Cn0＝1
例1判断下列问题是排列问题，还是组合问题．
（1）从1,2,3，…，9九个数字中任取3个，组成一个三位数，这样的三位数共有多少个？
（2）从1,2,3，…，9九个数字中任取3个，然后把这三个数字相加得到一个和，这样的和共有多少个？
（3）从a，b，c，d四名学生中选2名学生，去完成同一件工作有多少种不同的选法？
（4）5个人规定相互通话一次，共通了多少次电话？
（5）5个人相互各写一封信，共写了多少封信？
（1）当取出3个数字后，如果改变三个数字的顺序，会得到不同的三位数，此问题不但与取出元素有关，而且与元素的安排顺序有关，是排列问题．
（2）取出3个数字之后，无论怎样改变这三个数字之间的顺序，其和均不变，此问题只与取出的元素有关，而与元素的安排顺序无关，是组合问题．
（3）2名学生完成的是同一件工作，没有顺序，是组合问题．
（4）甲与乙通一次电话，也就是乙与甲通一次电话，无顺序区别为组合问题．
（5）发信人与收信人是有区别的，是排列问题．
例2（2011·
大纲全国卷）某同学有同样的画册2本，同样的集邮册3本，从中取出4本赠送给4位朋友，每位朋友1本，则不同的赠送方法共有（ ）
A．4种 B．10种C．18种 D．20种
分两种情况：
①选2本画册，2本集邮册送给4位朋友有C42＝6种方法；
②选1本画册，3本集邮册送给4位朋友有C41＝4种方法，所以不同的赠送方法共有6＋4＝10（种），故选B.
某人决定投资于8种股票和4种债券，经纪人向他推荐了12种股票和7种债券．问：
此人有多少种不同的投资方式？
需分两步：
第1步，根据经纪人的推荐在12种股票中选8种，共有C128种选法；
第2步，根据经纪人的推荐在7种债券中选4种，共有C74种选法．根据分步乘法计数原理，此人有C128·
C74＝17325种不同的投资方式．
现有10名大学生，其中男生6名，女生4名．
（1）现要从中选2名参加会议，有多少种不同的选法？
（2）现要从中选出男、女大学生各2名去参加会议，有多少种不同的选法？
（1）从10名大学生中选2名去参加会议的选法数就是从10个不同元素中取出2个元素的组合数，即C102＝＝45种．
（2）从6名男大学生中选2名的选法有C62种，从4名女大学生中选2名的选法有C42种，根据分步乘法计数原理，因此共有选法C62·
C42＝·
＝90种．
例3一位教练的足球队共有17名初级学员，他们中以前没有一个参加过比赛，按照足球比赛规则，比赛时一个足球队的上场队员是11人，问：
（1）这位教练从这17名学员中可以形成多少种学员上场方案？
（2）如果在选出11名上场队员时，还在确定其中的守门员，那么教练员有多少种方式做这件事情？
例4
（1）平面内有10个点，以其中每2个点为端点的线段共有多少条？
（2）平面内有10个点，以其中每两个点为端点的有向线段共有多少条？
（1）以正方体的顶点为顶点，可以确定多少个四面体？
（2）以正方体的顶点为顶点，可以确定多少个四棱锥？
（1）正方体8个顶点可构成C84个四点组，其中共面的四点组是正方体的6个表面及正方体6组相对棱分别所在的6个平面的四个顶点，故可确定四面体C84－12＝58（个）．
（2）由
（1）知，正方体共面的四点组有12个，以这每一个四点组构成的四边形为底面，以其余的四个点中任一点为顶点都可以确定一个四棱锥，故可以确定四棱锥12C41＝48（个）．
.
（1）四面体的一个顶点为A，从其他顶点和各棱中点中取3个点，使它们和点A在同一平面上，有多少种不同的取法？
（2）四面体的顶点和各棱中点共10个点，在其中取4个不共面的点，有多少种不同的取法．
（1）直接法：
如图，
含顶点A的四面体的3个面上，除点A外都有5个点，从中取出3点必与点A共面共有3C53种取法；
含顶点A的三条棱上各有三个点，它们与所对的棱的中点共面，共有3种取法．根据分类计数原理，与顶点A共面三点的取法有3C53＋3＝33种．
（2）间接法：
如图，从10个点中取4个点的取法有C104种，除去4点共面的取法种数可以得到结果．从四面体同一个面上的6个点取出的4点必定共面．有4C64＝60（种），四面体的每一棱上3点与相对棱中点共面，共有6种共面情况，从6条棱的中点中取4个点时有3种共面情形（对棱中点连线两两相交且互相平分），故4点不共面的取法为：
C104－（60＋6＋3）＝141（种）．
例5在100件产品中，有98件合格品，2件次品，从这100件产品中任意抽出3件，
（1）有多少种不同的抽法？
（2）抽出的3件中恰好有1件是次品的抽法有多少种？
（3）抽出的3件中至少有1件是次品的抽法有多少种？
（2011·
北京高考）用数字2,3组成四位数，且数字2,3至少都出现一次，这样的四位数共有________个．（用数字作答）
数字2,3至少都出现一次，包括以下情况：
“2”出现1次，“3”出现3次，共可组成C41＝4（个）四位数．
“2”出现2次，“3”出现2次，共可组成C42＝6（个）四位数．
“2”出现3次，“3”出现1次，共可组成C43＝4（个）四位数．
综上所述，共可组成14个这样的四位数．答案：
14
“抗震救灾，众志成城”，在我国甘肃舟曲的抗震救灾中，某医院从10名医疗专家中抽调6名奔赴某灾区救灾，其中这10名医疗专家中有4名是外科专家．问：
（1）抽调的6名专家中恰有2名是外科专家的抽调方法有多少种？
（2）至少有2名外科专家的抽调方法有多少种？
（3）至多有2名外科专家的抽调方法有多少种？
（1）分步：
首先从4名外科专家中任选2名，有C42种选法，再从除外科专家的6人中选取4人，有C64种选法，所以共有C42·
C64＝90种抽调方法.
（2）“至少”的含义是不低于，有两种解答方法，
方法一（直接法）：
按选取的外科专家的人数分类：
①选2名外科专家，共有C42·
C64种选法；
②选3名外科专家，共有C43·
C63种选法；
③选4名外科专家，共有C44·
C62种选法；
根据分类加法计数原理，共有C42·
C64＋C43·
C63＋C44·
C62＝185种抽调方法.
方法二（间接法）：
不考虑是否有外科专家，共有C106种选法，考虑选取1名外科专家参加，有C41·
C65种选法；
没有外科专家参加，有C66种选法，所以共有：
C106－C41·
C65－C66＝185种抽调方法.
（3）“至多2名”包括“没有”、“有1名”、“有2名”三种情况，分类解答．
①没有外科专家参加，有C66种选法；
②有1名外科专家参加，有C41·
③有2名外科专家参加，有C42·
C64种选法.
所以共有C66＋C41·
C65＋C42·
C64＝115种抽调方法
练习3：
某市工商局对35种商品进行抽样检查，鉴定结果有15种假货，现从35种商品中选取3种，试求：
（1）其中某一种假货必须在内，不同的取法有多少种？
（2）其中某一种假货不能在内，不同的取法有多少种？
（3）恰有2种假货在内，不同的取法有多少种？
（4）至少有2种假货在内，不同的取法有多少种？
（5）至多有2种假货在内，不同的取法有多少种？
（1）其中某一假货必须在内，则需从剩余的34种商品中选取2种，不同的取法有C342＝＝561（种）．
（2）其中某一假货不能在内，则需从剩余的34种商品中选取3种，共有C343＝5984（种）．
（3）恰有两种假货在内，则假货有C152种选法，1种真货的取法有C201种，故3种商品的取法有C152×
C201＝2100种．
（4）至少有2种假货，直接法为C152C201＋C153＝2555种，
间接法为C353－C203－C151C202＝2555种．
（5）至多有2种假货，直接法为C203＋C202C151＋C201C152＝6090（种），
间接法：
C353－C153＝6090（种）．
4、两个性质公式：
①②
①从n个不同元素中取出m个元素后就剩下n-m个元素，因此从n个不同元素中取出n-m个元素的方法是一一对应的，因此是一样多的就是说从n个不同元素中取出n-m个元素的唯一的一个组合.（或者从n+1个编号不同的小球中，n个白球一个红球，任取m个不同小球其不同选法，分二类，一类是含红球选法有一类是不含红球的选法有）
②根据组合定义与加法原理得；
在确定n+1个不同元素中取m个元素方法时，对于某一元素，只存在取与不取两种可能，如果取这一元素，则需从剩下的n个元素中再取m-1个元素，所以有C，如果不取这一元素，则需从剩余n个元素中取出m个元素，所以共有C种，依分类原理有.
5、几个常用组合数公式
例6 计算：
（1）；
（2）．
分析：
本题如果直接计算组合数，运算比较繁．本题应努力在式子中创造条件使用组合数的性质，第
（1）题中，，经此变形后，可继续使用组合数性质．第
（2）题有两个考虑途径，一方面可以抓住项的变形，求和；
另一方面，变形，接着，…，反复使用公式．
（1）原式．
（2）原式．
另一方法是：
原式
．
利用第
（2）小题的手段，我们可以得到组合数的一个常用的结论：
．
左边右边．
例7、计算下列各式的值．
（1）3C83－2C52；
（2）C10098＋C200199；
（3）C73＋C74＋C85＋C96；
（4）Cn5－n＋Cn＋19－n.
[解题过程]
（1）3C83－2C52＝3×
－2×
＝148.
（2）C10098＋C200199＝C1002＋C2001＝＋200＝5150.
（3）原式＝C84＋C85＋C96＝C95＋C96＝C106＝C104＝210.
（4）由⇒4≤n≤5.
∵n∈N*，∴n＝4或5.当n＝4时，原式＝C41＋C55＝5.
当n＝5时，原式＝C50＋C64＝16.
计算：
（1）C85＋C10098·
C77；
（2）C50＋C51＋C52＋C53＋C54＋C55；
（3）Cn＋1n·
Cnn－1.
（1）原式＝C83＋C1002×
1＝＋＝56＋4950＝5006.
（2）原式＝2（C50＋C51＋C52）＝2（C61＋C52）＝2×
＝32.
（3）方法一：
原式＝Cn＋1n·
Cn1＝·
n＝·
n＝（n＋1）n＝n2＋n.
原式＝（Cnn＋Cnn－1）·
Cnn－1＝（1＋Cn1）·
Cn1＝（1＋n）n＝n2＋n.
（1）已知－＝，求C8m.
（2）解方程：
Cx＋2x－2＋Cx＋2x－3＝Ax＋33.
[解]
（1）原方程变形为－
＝，
∴1－＝，即m2－23m＋42＝0，
（2）原方程可化为Cx＋3x－2＝Ax＋33，即Cx＋35＝Ax＋33，
∴＝，∴＝，
∴x2－x－12＝0解得x＝4或x＝－3
课后作业
一、知识点熟记
1、做一件事，完成它有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法……在第n类办法中有mn种不同的方法。
那么，完成这件事共有
N=种不同的方法；
完成一件事，需要分n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法……做第n步有mn种不同的方法。
那么，完成这件事共有N=种不同的方法；
2、排列数的计算公式为=；
组合数的计算公式=
（3）两个性质公式：
①②
二、题组分析
1、某小组有8名男生，6名女生，要从中选出一名同学代表小组发言，不同的选法共有（）
A、48种B、24种C、14种D、13种
2、有一位同学要从三门不同的知识类选修课、二门不同的技能类选修课、四门不同的艺术类选修课中各选一门，不同的选法有（）
A、9种B、20种C、24种D、15种
3、某商场有5个出入门，某人从任一门进入，购物完后从一门走出，不同的走法的种数为（）
A、5种B、16种C、25种D、20种
4、由甲地直达丙地有2种走法，由甲地到乙地有3种走法，由乙地到丙地有4种走法，则由甲地到丙地所有不同走法有（ ）种
A、5B、24C、14D、10
5、用1、2、3、4、5这五个数字，组成没有重复数字的三位数，则可排出奇数的个数为（）
A、24B、30C、36D、60
6、18×
17×
16×
15×
9等于（）
A、B、C、D、
7、现有5支足球队争夺冠、亚军，那么不同的结果有（）种
A、9B、20C、35D、125
8、现有5人照相，甲站中间的排法有（ ）
A、24种B、72种C、96种D、60种
9、一个画展在5个学校轮流展出，每个学校展出一次，则不同的展出次序有（）种
A、5B、25C、D、120
10、用1,2,3,4,5,6，这六个数字组成不重复的三位数的个数是（）
A、６0B、120C、180D、240
11、在5本不同数学书、3本不同故事书、2本不同美术书中任取一本书，有几种不同的取法（）
升级会员 