1、排列组合题型汇总教师用例 1 分别求出符合下列要求的不同排法的种数 ,(1 6名学生排 3排,前排 1人,中排 2人,后排 3人; (2 6名学生排成一排,甲不在排头也不在排尾;(3从 6名运动员中选出 4人参加 4100米接力赛,甲不跑第一棒,乙不跑第四棒; (4 6人排成一排,甲、乙必须相邻; (5 6人排成一排,甲、乙不相邻;(6 6人排成一排,限定甲要排在乙的左边,乙要排在丙的左边(甲、乙、丙可以不相邻解:(1分排坐法与直排坐法一一对应,故排法种数为 72066=A(2甲不能排头尾,让受特殊限制的甲先选位置,有 14A 种选法,然后其他 5人选,有55A 种选法,故排法种数为 4805
2、514=A A(3有两棒受限制,以第一棒的人选来分类:乙跑第一棒,其余棒次则不受限制,排法数为 35A ;乙不跑第一棒,则跑第一棒的人有 14A 种选法,第四棒除了乙和第一棒选定的人外, 也有 14A 种选法,其余两棒次不受限制,故有 221414A A A 种排法,由分类计数原理,共有 25224141435=+A A A A 种排法(4将甲乙“捆绑”成“一个元”与其他 4人一起作全排列共有 2405522=A A 种排法 (5甲乙不相邻,第一步除甲乙外的其余 4人先排好;第二步,甲、乙选择已排好的 4人的左、右及之间的空挡插位,共有 2544A A (或用 6人的排列数减去问题(2后排列
3、数为 48024066=-A (6三人的顺序定,实质是从 6个位置中选出三个位置,然后排按规定的顺序放置这三人,其余 3人在 3个位置上全排列,故有排法 1203336=A C 种点评:排队问题是一类典型的排列问题, 常见的附加条件是定位与限位、 相邻与不相邻 例 2 假设在 100件产品中有 3件是次品,从中任意抽取 5件,求下列抽取方法各多少 种? (1没有次品; (2恰有两件是次品; (3至少有两件是次品 解:(1 没有次品的抽法就是从 97件正品中抽取 5件的抽法, 共有 64446024597=C 种(2 恰有 2件是次品的抽法就是从 97件正品中抽取 3件, 并从 3件次品中抽 2
4、件的抽 法,共有 44232023397=C C 种(3至少有 2件次品的抽法,按次品件数来分有二类:第一类,从 97件正品中抽取 3件,并从 3件次品中抽取 2件,有 32973C C 种 第二类从 97件正品中抽取 2件,并将 3件次品全部抽取,有 23973C C 种 按分类计数原理有 4469763329723397=+C C C C 种 点评:此题是只选“元”而不排“序”的典型的组合问题,附加的条件是从不同种类的 元素中抽取,应当注意:如果第(3题采用先从 3件次品抽取 2件(以保证至少有 2件是次品 , 再从余下的 98件产品中任意抽取 3件的抽法, 那么所得结果是 4662883
5、9823=C C 种,其结论是错误的,错在“重复” :假设 3件次品是 A 、 B 、 C ,第一步先抽 A 、 B 第二步再抽 C 和其余 2件正品,与第一步先抽 A 、 C (或 B 、 C ,第二步再抽 B (或 A 和其余 2件正品是同一种抽法,但在算式 39823C C 中算作 3种不同抽法例 3 求证: m n m n m n A mA A =+-111 ; 12112+-+=+m n m n m n m n C C C C证明:利用排列数公式左 (1!1! 1! ! n m n n m n m -=+- (1! 1! !n m n m n n m -+-=-=-mn A m n
6、n ! ! 右另一种证法:(利用排列的定义理解从 n 个元素中取 m 个元素排列可以分成两类:第一类不含某特殊元素 a 的排列有 mn A 1-第二类含元素 a 的排列则先从 (1-n 个元素中取出 (1-m 个元素排列有 11-m n A 种, 然 后将 a 插入,共有 m 个空档,故有 11-m n A m 种, 因此 m n m n m n A A m A =+-111利用组合数公式 左 !2! 11! 1! 1! m n m n m n m n m n m n -+-+-+=(11211!1! 1!+-+-+-+m n m m m m n m n m n m n =(=+-+=+-+=
7、+12!1! 1! 212! 1! 1! m n C m n m n n n m n m n 右另法:利用公式 111-+=m n m n m n C C C 推得左 (=+=+=+-+1211111m n n n m n m n m n m n m n C C C C C C C 右点评:证明排列、组合恒等式通常利用排列数、组合数公式及组合数基本性质 例 4 已知 f 是集合 d c b a A , , , =到集合 2, 1, 0=B 的映射 (1不同的映射 f 有多少个?(2若要求 (4=+d f c f b f a f 则不同的映射 f 有多少个? 分析:(1确定一个映射 f ,需要确
8、定 d c b a , , , 的像(2 d c b a , , , 的象元之和为 4,则加数可能出现多种情况,即 4有多种分析方案,各 解:(1 A 中每个元都可选 0,1,2三者之一为像,由分步计数原理,共有 433333= (2根据 d c b a , , , 对应的像为 2的个数来分类,可分为三类:第一类:没有元素的像为 2,其和又为 4,必然其像均为 1,这样的映射只有一个;第二类:一个元素的像是 2,其余三个元素的像必为 0,1,1,这样的映射有 121314=P C 个;第三类:二个元素的像是 2,另两个元素的像必为 0,这样的映射有 624=C 个由分类计数原理共有 1+12+
9、6=19点评:问题(1可套用投信模型:n 封不同的信投入 m 个不同的信箱,有 nm 种方 法;问题(2的关键结合映射概念恰当确定分类标准,做到不重、不漏 例 5 四面体的顶点和各棱的中点共 10个点(1设一个顶点为 A ,从其他 9点中取 3个点,使它们和点 A 在同一平面上,不同的 取法有多少种?(2在这 10点中取 4个不共面的点,不同 的 取 法 有多少种? 解:(1如图,含顶点 A 的四面体的三个面 上, 除点 A 有 353C 种外都有 5个点,从中取出 3点必与点 A 共面,共 取法 含顶点 A 的棱有三条,每条棱上有 3个点,它们与所对棱的中点共面,共有 3种取法根据分类计数原
10、理和点 A 共面三点取法共有 333335=+C 种(2 取出的 4点不共面比取出的 4点共面的情形要复杂, 故采用间接法:先不加限制任取 4点(410C 种取法减去 4点共面的取法 取出的 4点共面有三类:第一类:从四面体的同一个面上的 6点取出 4点共面,有 464C 种取法第二类:每条棱上的 3个点与所对棱的中点共面,有 6种取法 第三类:从 6条棱的中点取 4个点共面,有 3种取法根据分类计数原理 4点共面取法共有 6936446=+C故取 4个点不共面的不同取法有 (14136446410=+-C C (种点评:由点构成直线、平面、几何体等图形是一类典型的组合问题,附加的条件是点共三
11、、排列组合解题备忘录 :m个不同的元素必须相邻,有 mm Pm个不同元素互不相邻,分别“插入”到n个“间隙”中的m个位置有 m n P 种 m个相同的元素互不相邻, 分别 “插入” 到n个 “间隙” 中的m个位置, 有 m n C 种若干个不同的元素“等分”为 m个组 , 要将选取出每一个组的组合数的乘积除以mmP (去除重复数四.排列组合问题中的数学思想方法(一 .分类讨论的思想:许多“数数”问题往往情境复杂,层次多,视角广,这就需 要我们在分析问题时,选择恰当的切入点,从不同的侧面,把原问题变成几个小问题, 分而 治之,各种击破。例 . 已知集合 A 和集合 B 各含有 12个元素, A
12、B 含有 4个元素,求同时满足下列条 件的集合 C 的个数:1 C A B 且 C 中含有 3个元素, 2 C A 解:如图,因为 A , B 各含有 12个元素, A B 含有 4个元素, 所以 A B 中的元素有 12+12-4=20个,其中属于 A 的有 12个,属于 A 而不属于 B 的有 8个,要使 C A ,则 C 中的元素至少含在 A中,集合 C 的个数是:1只含 A 中 1个元素的有 12128C C ; 2含 A 中2个元素的有 21128C C ; 3含 A 中 3个元素的有 30128C C ,故所求的集合 C 的个数共有 12128C C +21128C C +3012
13、8C C =1084个(二 . 等价转化的思想:很多 “数数” 问题的解决, 如果能跳出题没有限定的 “圈子” , 根据题目的特征构思设计出一个等价转化的途径, 可使问题的解决呈现出 “要柳暗花明” 的格局。1. 具体与抽象的转化例 . 某人射击 7枪,击中 5枪,问击中和末击中的不同顺序情况有多少种?分析:没击中用“ 1”表示,击中的用“ 0”表示,可将问题转化不下列问题:数列1234567, , , , , , a a a a a a a 有两项为 0, 5项是 1,不同的数列个数有多少个?解:1两个 0不相邻的情况有 26C 种, 2两个 0相邻的情况有 16C 种,所以击中和末 击中的
14、不同顺序情况有 26C +16C =21种。2不同的数学概念之间的转化例 . 连结正方体 8个顶点的直线中,为异面直线有多少对?分析:正面求解或反面求解(利用补集,虽可行,但容易遗漏或重复,注意这样一个事 实, 每一个三棱锥对应着三对异面直线, 因而转化为计算以正方体顶点, 可以构成多少个三 棱锥解:从正文体珠 8个顶点中任取 4个,有 48C 种,其中 4点共面的有 12种, (6个表面 和 6个对角面 将不共面的 4点可构一个三棱锥, 共有 48C -12个三棱锥, 因而共有 3(48C -12 =174对异面直线。综上所述, 有以上几种解排列组合的方法, 此外, 当然也还有其他的方法要靠
15、我们去发 现和积累,我们要掌握好这些方法,并且能够灵活运用,这样,在日常生活中,我们们能轻 易解决很多问题。教师点评:对排列组合问题的处理方法总结得很细、 很全面, 而且挖掘出其中所蕴藏的 数学思想方法,对学习排列组合有一定的指导性。 (三容斥原理与计数 1、文氏图:在文氏图中 , 以下图形的含义如下: 矩形:其内部的点表示全集的所有元素; 矩形内的圆(或其它闭曲线 :表示不同的集合; 圆(或闭曲线内部的点:表示相应集合的元素。 2、三交集公式:A+B+C=A B C+AB+BC+AC -ABC(A B C 指的是 E , ABC 指的是 D (四模型构造例 1. 4名同学各写一张贺卡,先集中
16、起来,然后每人从中拿出一张别人写的贺卡,则 四张贺卡的不同分配方式共有 种 . 例 2. 将编号为 1, 2, 3, 4的四个小球分别放入编号为 1, 2, 3, 4的四个盒子中, 要求每个盒子放一个小球, 且小球的编号与盒子的编号不能相同, 则共有 种不同的放 法 .这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题,我们把这种限 制条件的排列问题叫做 全错位排列问题 .例 3. 五位同学坐在一排,现让五位同学重新坐,至多有两位同学坐自己原来的位置, 则不同的坐法有 种 .解析:可以分类解决:第一类,所有同学都不坐自己原来的位置;第二类,恰有一位同学坐自己原来的位置;第三类,恰有两
17、位同学坐自己原来的位置 .对于第一类,就是上面讲的全错位排列问题;对于第二、第三类有部分元素还占有原 来的位置, 其余元素可以归结为全错位排列问题, 我们称这种排列问题为 部分错位排列问题 .设 n 个元素全错位排列的排列数为 T n ,则对于例 3,第一类排列数为 T 5,第二类先确 定一个排原来位置的同学有 5种可能,其余四个同学全错位排列,所以第二类的排列数为5T 4,第三类先确定两个排原位的同学,有 25C =10种,所以第三类的排列数为 10T 3,因此例3的答案为:T 5+5T 4+10T 3.例 4、把 8个相同的球放入 4个不同的盒子,有多少种不同方法?解:取 3块相同隔板,连
18、同 8个相同的小球排成一排,共 11个位置。由隔板法知,在 11个位置中任取 3个位置排上隔板,共有 C 311种排法。311C =12391011=165(种 所以,把 8个相同的球放入 4个不同的盒子,有 165种不同方法。点评 :相同的球放入不同的盒子, 每个盒子放球数不限,适合 隔板法 。 隔板的块数要比盒子数少 1。五.排列组合中的 易错题1没有理解两个基本原理出错排列组合问题基于两个基本计数原理,即加法原理和乘法原理,故理解“分类用加、分步用乘”是解决排列组合 问题的前提 .例 1(1995年上海高考题 从 6台原装计算机和 5台组装计算机中任意选取 5台 , 其中 至少有原装与组
19、装计算机各两台 , 则不同的取法有 种 .误解:因为可以取 2台原装与 3台组装计算机或是 3台原装与 2台组装计算机,所以 只有 2种取法 .错因分析:误解的原因在于没有意识到“选取 2台原装与 3台组装计算机或是 3台原装 与 2台组装计算机”是完成任务的两“类”办法,每类办法中都还有不同的取法 .正解:由分析,完成第一类办法还可以分成两步:第一步在原装计算机中任意选取 2台,有 26C 种方法;第二步是在组装计算机任意选取 3台,有 35C 种方法,据乘法原理共有 3526C C 种方法 . 同理, 完成第二类办法中有 2536C C 种方法 . 据加法原理完成全部的选取过程共 有 +3
20、526C C 3502536=C C 种方法 .例 2 在一次运动会上有四项比赛的冠军在甲、乙、丙三人中产生,那么不同的夺冠情 况共有( 种 .(A 34A (B 34 (C 43 (D 34C误解:把四个冠军,排在甲、乙、丙三个位置上,选 A .错因分析:误解是没有理解乘法原理的概念,盲目地套用公式 .正解:四项比赛的冠军依次在甲、乙、丙三人中选取,每项冠军都有 3种选取方法,由 乘法原理共有 433333=种 .说明:本题还有同学这样误解,甲乙丙夺冠均有四种情况,由乘法原理得 34. 这是由于 没有考虑到某项冠军一旦被一人夺得后,其他人就不再有 4种夺冠可能 .2判断不出是排列还是组合出错
21、在判断一个问题是排列还是组合问题时, 主要看元素的组成有没有顺序性, 有顺序的是 排列,无顺序的是组合 .例 3 有大小形状相同的 3个红色小球和 5个白色小球,排成一排,共有多少种不同的 排列方法?误解:因为是 8个小球的全排列,所以共有 88A 种方法 .错因分析:误解中没有考虑 3个红色小球是完全相同的, 5个白色小球也是完全相同的, 同色球之间互换位置是同一种排法 .正解:8个小球排好后对应着 8个位置, 题中的排法相当于在 8个位置中选出 3个位置 给红球,剩下的位置给白球,由于这 3个红球完全相同,所以没有顺序,是组合问题 . 这样共有:5638=C 排法 .3重复计算出错在排列组
22、合中常会遇到元素分配问题、 平均分组问题等, 这些问题要注意避免重复计数, 产生错误。例 4(2002年北京文科高考题 5本不同的书全部分给 4个学生,每个学生至少一本, 不同的分法种数为( (A 480 种 (B 240种 (C 120种 (D 96种误解:先从 5本书中取 4本分给 4个人,有 45A 种方法,剩下的 1本书可以给任意一个人有 4种分法,共有 480445=A 种不同的分法,选 A .错因分析:设 5本书为 a 、 b 、 c 、 d 、 e ,四个人为甲、乙、丙、丁 . 按照上述分法可 能如下的表 1和表 2:表 1是甲首先分得 a 、乙分得 b 、丙分得 c 、丁分得
23、d ,最后一本书 e 给甲的情况;表 2是 甲首先分得 e 、乙分得 b 、丙分得 c 、丁分得 d ,最后一本书 a 给甲的情况 . 这两种情况是完 全相同的,而在误解中计算成了不同的情况。正好重复了一次 .正解:首先把 5本书转化成 4本书,然后分给 4个人 . 第一步:从 5本书中任意取出 2本捆绑成一本书,有 25C 种方法;第二步:再把 4本书分给 4个学生,有 44A 种方法 . 由乘法原理,共有 25C 24044=A 种方法,故选 B . 例 5 某交通岗共有 3人,从周一到周日的七天中,每天安排一人值班,每人至少值 2天,其不同的排法共有( 种 .(A 5040 (B 126
24、0 (C 210 (D 630误解:第一个人先挑选 2天,第二个人再挑选 2天,剩下的 3天给第三个人,这三个人再进行全排列 . 共有:1260332527=A C C ,选 B . 错因分析:这里是均匀分组问题 . 比如:第一人挑选的是周一、周二,第二人挑选的是 乙 丙 丁 a 甲 e d c b 表 1 乙丙 丁 a甲 e d cb 表 2周三、周四;也可能是第一个人挑选的是周三、周四,第二人挑选的是周一、周二,所以在 全排列的过程中就重复计算了 . 正解:6302332527=A C C 种 . 4遗漏计算出错在排列组合问题中还可能由于考虑问题不够全面,因为遗漏某些情况,而出错。 例 6
25、 用数字 0, 1, 2, 3, 4组成没有重复数字的比 1000大的奇数共有( (A 36个 (B 48个 (C 66个 (D 72个误解:如右图,最后一位只能是 1或 3有两种取法, 又因为第 1位不能是 0,在最后一位取定后只有 3种取 法,剩下 3个数排中间两个位置有 23A 种排法,共有 363223=A 个 .错因分析:误解只考虑了四位数的情况,而比 1000大的奇数还可能是五位数 .正解:任一个五位的奇数都符合要求, 共有 363233=A 个, 再由前面分析四位数个数和五位数个数之和共有 72个,选 D .5忽视题设条件出错在解决排列组合问题时一定要注意题目中的每一句话甚至每一
26、个字和符号, 不然就可能 多解或者漏解 .例 7 (2003全国高考题 如图,一个 地区分为 5个行政区域,现给地图着色,要求相邻区域不得使用同一颜色,现有 4种颜色可供选择,则不同的着色方法共有 种 . (以数字作答误解:先着色第一区域,有 4种方法,剩下 3种颜色涂四个区域,即有一种颜色涂相对的两块区域,有 1222213=A C 种,由乘法原理共有:48124=种 . 错因分析:据报导,在高考中有很多考生填了 48种 . 这主要是没有看清题设“有 4种颜 色可供选择 .” ,不一定需要 4种颜色全部使用,用 3种也可以完成任务 . 正解:当使用四种颜色时,由前面的误解知有 48种着色方法
27、;当仅使用三种颜色时:从 4种颜色中选取 3种有 34C 种方法,先着色第一区域,有 3种方法,剩下 2种颜色涂四个区域,只能是一种颜色涂第 2、 4区域,另一种颜色涂第 3、 5区域,有 2种着色方法,由乘法原理有 242334=C 种 . 综上共有:722448=+种 .例 8 已知 02=-b ax 是关于 x 的一元二次方程, 其中 a 、 4, 3, 2, 1b , 求解集不同的一 元二次方程的个数 .误解:从集合 4, 3, 2, 1中任意取两个元素作为 a 、 b ,方程有 24A 个,当 a 、 b 取同一个数时方程有 1个,共有 13124=+A 个 .错因分析:误解中没有注
28、意到题设中:“求解集不同 .的”所以在上述解法中要去掉 同解情况,由于 =4221b a b a 和 同解、 =2412b a b a 和 同解,故要减去 2个。 正解:由分析,共有 11213=-个解集不同的一元二次方程 .6未考虑特殊情况出错在排列组合中要特别注意一些特殊情况,一有疏漏就会出错 .例 9 现有 1角、 2角、 5角、 1元、 2元、 5元、 10元、 20元、 50元人民币各一张, 100元人 民币 2张,从中至少取一张,共可组成不同的币值种数是( (A1024种 (B1023种 (C1536种 (D1535种误解:因为共有人民币 11张,每张人民币都有取和不取 2种情况,
29、减去全不取的 1种情 况,共有 10231210=-种 .错因分析:这里 100元面值比较特殊有两张,在误解中被计算成 4 种情况,实际上只 有不取、取一张和取二张 3种情况 .正解:除 100元人民币以外每张均有取和不取 2种情况, 100元人民币的取法有 3种情况, 再减去全不取的 1种情况,所以共有 15351329=-种 .7题意的理解偏差出错例 10 现有 8个人排成一排照相,其中有甲、乙、丙三人不能相邻的排法有( 种 .(A 5536A A (B 336688A A A - (C 3335A A (D 4688A A - 误解:除了甲、乙、丙三人以外的 5人先排,有 55A 种排法
30、, 5人排好后产生 6个空档,插入甲、乙、丙三人有 36A 种方法,这样共有 5536A A 种排法,选 A . 错因分析:误解中没有理解“甲、乙、丙三人不能相邻”的含义,得到的结果是“甲、 乙、丙三人互不相邻 .”的情况 . “甲、乙、丙三人不能相邻”是指甲、乙、丙三人不能同时 相邻,但允许其中有两人相邻 .正解:在 8个人全排列的方法数中减去甲、乙、丙全相邻的方法数,就得到甲、乙、丙三人不相邻的方法数,即 336688A A A -,故选 B .8解题策略的选择不当出错有些排列组合问题用直接法或分类讨论比较困难,要采取适当的解决策略,如间接法、 插入法、捆绑法、概率法等,有助于问题的解决
31、.例 10 高三年级的三个班到甲、乙、丙、丁四个工厂进行社会实践,其中工厂甲必须 有班级去,每班去何工厂可自由选择,则不同的分配方案有( .(A 16种 (B 18种 (C 37种 (D 48种误解:甲工厂先派一个班去,有 3种选派方法,剩下的 2个班均有 4种选择,这样共 有 48443=种方案 .错因分析:显然这里有重复计算 . 如:a 班先派去了甲工厂, b 班选择时也去了甲工厂, 这与 b 班先派去了甲工厂, a 班选择时也去了甲工厂是同一种情况,而在上述解法中当作了 不一样的情况,并且这种重复很难排除 .正解:用间接法 . 先计算 3个班自由选择去何工厂的总数, 再扣除甲工厂无人去的情况, 即:37333444=-种方案 .
