计数原理、排列组合题型与方法

《计数原理、排列组合题型与方法》由会员分享，可在线阅读，更多相关《计数原理、排列组合题型与方法（18页珍藏版）》请在金锄头文库上搜索。

1、计数原理、排列组合题型与方法基本思路：大的方向分类，类中可能有步或类例1：架子上有不同的2个红球，不同的3个白球，不同的4个黑球若从中取2个不同 色的球，则取法种数为.解：先分类、再分步，共有取法2x3 + 2x4+3x4 = 26种故填26.基本思路：大的方向分步，步中可能有类或步例1：如图所示，使电路接通，开关不同的开闭方式有（）A. 11种 B. 20 种C. 21 种 D. 12 种解：分两步，第一部分接通，则可能有一个接通或者两个都接通，有3种可能；第二部 分接通，则可能恰有一个接通或恰有两个接通或者都接通，有7种可能。从而总共有3 7=21 种方式。基本思路：排除法间接求解例1：

2、（2013济南模拟）电路如图所示，在A，B间有四个开关, 若发现A，B之间电路不通，则这四个开关打开或闭合的方式有 （）A.3种B.8种C.13 种D.16 种解：各个开关打开或闭合有2种情形，故四个开关共有24种可能，其中能使电路通的情 形有：1, 4都闭合且2和3中至少有一个闭合，共有3种可能，故开关打开或闭合的不同情 形共有24-3 = 13（种）.故选C.剔除重复元素例1： （2013四川）从1，3, 5, 7, 9这五个数中，每次取出两个不同的数分别记为a，b, 共可得到1 ga-lgb的不同值的个数是（）A.9 B.10 C.18 D.20解：lga1gb=1gb，而3=9，1=3

3、，故所求为A22=18个，故选C投信问题例1：将5封信投入3个邮筒，不同的投法共有（）A.53 种 B.35 种 C.3 种 D.15 种解：第1封信，可以投入第1个邮筒，可以投入第2个邮筒，也可以投入第3个邮筒， 共有3种投法；同理，后面的4封信也都各有3种投法所以，5封信投入3个邮筒，不同的 投法共有35种故选B.例 2 ：有六名同学报名参加三个智力竞赛项目，在下列情况下各有多少种不同的报名方法？ （不一定六名同学都能参加）（1）每人恰好参加一项，每项人数不限；（2）每项限报一人，且每人至多参加一项；（3）每项限报一人，但每人参加的项目不限解 （1）每人都可以从这三个比赛项目中选报一项，各

4、有 3 种不同选法，由分步乘法计数原 理，知共有选法36=729（种）.（2）每项限报一人，且每人至多参加一项，因此可由项目选人，第一个项目有6 种选法，第 二个项目有5种选法，第三个项目只有4种选法，由分步乘法计数原理，得共有报名方法 6x5x4 = 120（种）.（3）由于每人参加的项目不限，因此每一个项目都可以从这六人中选出一人参赛，由分步乘 法计数原理，得共有不同的报名方法 63=216（种）.数字排列问题例1：用数字0， 1， 2， 3， 4， 5组成没有重复数字的四位数.（1）可组成多少个不同的四位数？（2）可组成多少个不同的四位偶数？解：（1）直接法：AgA5 = 3OO;间接法

5、：A4-A3 = 300.（2）由题意知四位数的个位上必须是偶数，同时暗含了千位不能是 0，因此该四位数的个 位和千位是“特殊位置”，应优先处理;另一方面，0 既是偶数，又不能排在千位，属“特殊元 素”，应重点对待.解法一：（直接法）0在个位的四位偶数有A5个；0不在个位时，先从2, 4中选一个放在 个位，再从余下的四个数（不包括0）中选一个放在千位，应有A2A4A4个.综上所述，共有 A53A12A14A24= 156（个）.解法二：（间接法）从这六个数字中任取四个数字组成最后一位是偶数的排法，有A1A5个， 其中千位是0的有A1A4个，故适合题意的数有A3A5-A2A4=156（个）.点拨

6、： 本例是有限制条件的排列问题，先满足特殊元素或特殊位置的要求，再考虑其他元素或 位置，同时注意题中隐含条件0不能在首位.例 2：用数字 2， 3 组成四位数，且数字 2， 3 至少都出现一次，这样的四位数共有个（用数字作答）.解析 数字2，3至少都出现一次，包括以下情况：“2”出现1次，“3”出现3次，共可组成C4=4（个）四位数.“2”出现2次，“3”出现2次，共可组成C4=6（个）四位数.“2”出现3次，“3”出现1次，共可组成C=4（个）四位数. 综上所述，共可组成14个这样的四位数.例3： （2014武汉模拟）如果正整数M的各位数字均不为4,且各位数字之和为6,则称M 为“幸运数”，

7、则三位正整数中的“幸运数”共有个.解：不含4,且和为6的三个自然数可能为（1, 2, 3）, （1, 5, 0）, （2, 2, 2）, （3, 3, 0）, （6, 0, 0）.因此三位正整数中的“幸运数”有A3 + 2A+1+A2+1 = 14（个）.故填14.错位排列例1：将数字1，2, 3, 4填入标号为1，2, 3, 4的四个方格中，每格填一个数，则每个方格的标号与所填数字均不相同的填法有种.解析 编号为1的方格内填数字2,共有3种不同填法；编号为1的方格内填数字3,共有3种不同填法；编号为1的方格内填数字4,共有3种不同填法.于是由分类加法计数原理，得共有3 + 3 + 3=9（种

8、）不同的填法.例2： （2013成都模拟）用6个字母A, B, C, a, b, c编拟某种信号程序（大小写有区别）. 把这6个字母全部排到如图所示的表格中，每个字母必须使用且只使用一次，不同的排列方 式表示不同的信号，如果恰有一对字母（同一个字母的大小写）排到同一列的上下格位置，那 么称此信号为“微错号”，则不同的“微错号”总个数为（）A.432B.288C.96D.48解：根据题意，分3步进行：先确定排到同一列的上下格位置的一对字母，有C3=3 种情况，将其放进表格中，有C3 = 3种情况，考虑这一对字母的顺序，有A2=2种不同顺序; 再分析第二对字母，其不能排到同一列的上下格位置，假设选

9、定的一对大小写字母为A 和a,则分析B与b: B有4种情况，b的可选位置有2个；最后一对字母放入最后两个位 置，有A2=2种放法则共有3x3x2x4x2x2=288个“微错号”故选B选派分配问题例1： 2010年广州亚运会组委会要从小张、小赵、小李、小罗、小王五名志愿者中选派 四人分别从事翻译、导游、礼仪、司机四项不同工作，若其中小张和小赵只能从事前两项工 作，其余三人均能从事这四项工作，则不同的选派方案共有（）A. 36 种B. 12 种C. 18 种D. 48 种解：根据题意分2种情况讨论，若小张或小赵入选，则有选法C2iC2iA33=24；若小张、小赵都入选，则有选法A22A32=12，

10、共有选法12+24=36种，故选A.例2： 2015年开春之际，六中食堂的伙食在百升老师的带领下进行了全面升级.某日5 名同学去食堂就餐，有米饭，花卷，包子和面条四种主食.每种主食均至少有一名同学选择 且每人只能选择其中一种.花卷数量不足仅够一人食用，甲同学因肠胃不好不能吃米饭，则 不同的食物搭配方案种数为( )A.96 B.120 C.132 D.240解：分类讨论：甲选花卷，则有2人选同一种主食，方法为；=18，剩下2人选其余主食, 方法为盘|=2，共有方法18x2=36种；甲不选花卷，其余4人中1人选花卷，方法为4种，甲包子或面条，方法为2种，其余3人, 若有1人选甲选的主食，剩下2人选

11、其余主食，方法为3=6；若没有人选甲选的主食，方 法为磅A2=6,共有4x2x (6+6) =96种， 故共有36+96=132种，故选：C.分堆与分配问题例1：现有6本不同的书：(1) 甲、乙、丙三人每人两本，有多少种不同的分配方法？一堆3本，有多少种不同的分堆方法？一人2本，一人3本，有多少种不同的分配方法? 另两人每人分1本，有多少种不同的分配方法？ 再从剩下的4本书中取2本给乙，最后两本给丙，(2) 分成三堆，每堆2本，有多少种分堆方法？(3) 分成三堆，一堆1本，一堆2本，(4) 分给甲、乙、丙三人，一人1本，(5) 甲、乙、丙三人中，一人分4本，解：(1)在6本书中，先取2本给甲，

12、C2C2匕勺=15(种)分堆方法;共有C2C4C2=90(种)分配方法；(2) 6本书平均分成3堆，用上述分法重了 A3倍，故共有予(3) 从6本书中，先取1本作为一堆，再在剩下的5本中取2本作为一堆，最后3本作为 一堆，共有C6C|C3=60(种)分堆方法；(4) 在(3)的分堆中，甲、乙、丙三人任取一堆，共有C1C2C3A3 = 360(种)分配方法.C4C1C1(5) 先分堆、再分配，共有七!丄虫3=90(种)分配方法.点拨：平均分配给不同人的分法等于平均分堆的分法乘以堆数的全排列分堆到位相当于分堆 平均分堆到指定位置后各堆再全排列，平均分堆不到指定位置，其分法数为： 堆数的阶乘 对于分

13、堆与分 配问题应注意：处理分配问题要注意先分堆再分配被分配的元素是不同的(像“名额”等则 是相同元素，不适用），位置也应是不同的（如不同的“盒子”）.分堆时要注意是否均匀如6分 成（2， 2， 2）为均匀分组，分成（1， 2， 3）为非均匀分组，分成（4， 1， 1）为部分均匀分组.例 2：4 个不同的球， 4 个不同的盒子，把球全部放入盒内.（1）恰有 1 个盒不放球，共有多少种放法？（2）恰有 2 个盒不放球，共有多少种放法？解：（1）为保证“恰有 1 个盒不放球”，先从4 个盒子中任意取出去一个，问题转化为“4 个 球，3个盒子，每个盒子都要放入球，共有多少种放法？”即把4 个球分成 2

14、，1，1 的三组， 然后进行全排列，共有4“4；A3 144（种）放法.（2）确定2个空盒有C4种方法.4个球放进2个盒子可分成（3, 1）, （2, 2）两类，第一类为 有序不均匀分组，有 C3C1A2种放法；第二类为有序均匀分组，有 等2.A2种放法，故共有 上彳仑肉+号人2上2=84（种）.相邻捆绑，不邻插空例 1 ： 3 名女生和 5 名男生排成一排（1）如果女生全排在一起，有多少种不同排法？（2）如果女生都不相邻，有多少种排法？（3）如果女生不站两端，有多少种排法？（4）其中甲必须排在乙前面（可不邻），有多少种排法？（5）其中甲不站左端，乙不站右端，有多少种排法？解 （1）（捆绑法）

15、由于女生排在一起，可把她们看成一个整体，这样同五个男生合在一起有6个元素，排成一排有Ag种排法，而其中每一种排法中，三个女生间又有A3种排法，因 此共有AgA3=4 320（种）不同排法.（2）（插空法）先排5个男生，有A?种排法，这5个男生之间和两端有6个位置，从中选取3 个位置排女生，有A6种排法，因此共有A5A3=14 400（种）不同排法.（3）法一（位置分析法）因为两端不排女生，只能从5个男生中选2人排列，有人5种排法， 剩余的位置没有特殊要求，有Ag种排法，因此共有A$A6=14 400（种）不同排法.法二（元素分析法）从中间6个位置选3个安排女生，有A?种排法，其余位置无限制，有 A?种排法，因此共有AgA5 = 14 400（种）不同排法.（4）8名学生的所有排列共A?种，其中甲在乙前面与乙在甲前面的各占其中2，符合要求 的排法种数为苏8 = 20 160（种）.（5）甲、乙为特殊元素，左、右两边为特殊位置法一（特殊元素法）甲在最右边时，其他的可全排，有a7种；甲不在最右边时，可从余下6个位置中任选一个，有人6种.而乙可排在除去最右边位置后剩余的6