4．2　排列与组合

4．2　排列与组合

排列组合是组合学最基本的概念．所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序．组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序．排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数．排列组合与古典概率论关系密切．

方法简述

1．限制条件优先考虑法

例1　从a,b,c,d,e这5个元素中取出4个放在4个不同的格子中,且元素b不能放在第二个格子里,问共有多少种不同的放法?

点拨　这里b是特殊元素,第二个位置是特殊位置,因此要先“照顾”特殊,再考虑“一般”．

解答　这里b是特殊元素,应先排b,但考虑取出的4个元素中可能有b也可能没有b,因此对此问题应该分为两类．

第一类:若取出的4个元素中有b,则排b有种排法;再从a,b,c,e中取出3个,排在另外的三个格子中,有种,所以此类的排法总数为种;

第二类:若取出的4个元素中没有b,则有种排法．

所以共有(种)不同的排法．

反思　优先考虑元素b的安排,再考虑其他元素．

例2　某天某班的课程安排要排数学、语文、英语、物理、化学、体育六门课程,根据课程特点,第一节不能排体育,第六节不能排数学,那么一共有多少种不同的排法?

点拨　将六门课程看作是元素,把节次看作是位置,因此这个问题中可以把第一节与第六节看作是特殊位置,也可以将体育与数学看作是特殊元素．

解答　依第一节课的排法进行分类:

第一节排数学,第六节排体育的排法有种;

第一节排数学,第六节不排体育的排法有种;

第一节不排数学,第六节排体育的排法有种;

第一节和第六节都不排数学和体育的排法有种．

由分类加法计数原理,所求的不同的排法为:＝504(种)．

反思　两个限制条件优先考虑

例3　用数字0,1,2,3,4,5组成没有重复数字的数

(1)能组成多少个六位数?

(2)能组成多少个六位奇数?

(3)能组成多少个能被5整除的六位数?

(4)能组成多少个比240135大的数?

点拨　应注意0这一特殊元素,它不能排在首位这一特殊位置,在解答过程中,以位置优先,较容易解决,但若以特殊元素为主,也可以解决．

解答　(1)第一位数字不能为0,有种方法,其他各位数字有种不同的排法,故共能组成的六位数有

(2)要使六位数为奇数,其个位数字必须是1或3或5中的一个,且第一位数字不能为0,故所求的六位奇数的个数为

(3)要使六位数能被5整除,其个位数字必须为5或0．当个位数字是0时,有个;当个位数字是5时,有个,因此能被5整除的六位数的个数为

(4)要比240135大,首先必须是六位数,有以下几类情况:

首位数字是3或4或5时,各有个;

首位数字是2时,第二位数字是4或5,但不包含240135在内,有(－1)个;

因此共有比240135大的数的个数为

反思　这类问题还要注意排成的数字是不允许有重复数字的情况．

2．分类讨论法

例4　4个不同的红球和6个不同的白球放入同一个袋中,现从中取出4个球:

(1)若取出的红球的个数不少于白球的个数,则有多少种不同的取法?

(2)取出一个红球记2分,取出一个白球记1分,若取出4个球总分不小于5分,则有多少种不同的取法?

点拨　(1)由于取出的4个球中红球的个数不少于白球的个数,因此至少要取出2个红球,可分为三类:①全部取出红球;②取出3个红球;③取出2个红球,可用搭配法进行求解．

解答　(1)依题意可知,取出的4个球中至少有2个红球,可分为三类:

①全取出红球,有种不同的取法;②取出的4个球中有3个红球1个白球,有种取法;③取出的4个球中有2个红球2个白球的取法有种不同的取法．

由分类加法计数原理知,共有不同的取法．

(2)依题意知,取出的4个球中至少要有1个红球,从红白10个球中取出4个球的取法有种不同的取法,而全是白球的取法有C46种,从而满足题意的取法有

反思　在解决某些问题时,直接法往往不能奏效,需要利用间接法去求解,即把问题中不符合题意要求的情况求出来,用总数减去即可得到所要求解的结果．直接法与间接法在使用时要根据题目的特点进行恰当地选择,在直接法不便解题时,应考虑使用间接法．(https://www.daowen.com)

3．挡板法

例5　某运输公司有7个车队,每个车队的车均多于4辆,现从这个公司中抽调出10辆车,并且每个车队中至少抽取1辆车,那么共有多少种不同的抽调方式?

点拨　要抽调10辆车,可以看作是将10个抽取名额分配到7个车队中去,每个车队至少有一个名额,可以使用挡板法．

解答　由于每个车队的车均多于4辆,只需将10个份额分成7份．可将10个元素排成一排,在相互之间的9个空档(除去两端)中插入6个挡板,即可将元素分成7份,因而有＝84(种)抽调方法．

反思　指标分配问题是指n个相同的元素分配给m个不同的单位(n＞m),每个单位至少分配一个元素．该问题常用挡板法来解决,在元素的个数不是太多时,有时也可以用分类法来解决．在有些问题中,有时还需要分析,把相似的其他问题转化为挡板问题,比如求方程a＋b＋c＝10有多少组不同的正整数解,就相当于把10个相同的糖果分给3个小朋友,每位小朋友至少一个,有多少种不同的分法．

易错解读

例6　有10只不同的试验产品,其中4只是次品,6只是正品．现每次取1只进行测试,直到4只次品全部测出为止,求最后1只次品恰好在第五次测试时被发现的不同的情形有多少种?

解答　设想有5个位置,先从6只正品中任选1只,放在前四个位置的任一个上,有×种方法;再把4只次品在剩余的四个位置上任意排列,有种排法,故不同的情形有××＝576(种)．

易错点　本题的实质是前五次测试中有1只是正品,4只次品,且第五次测试的是次品．

例7　(1)平面内有10个点,以其中每2个点为端点的线段共有多少条?

(2)平面内有10个点,以其中每2个点为端点的有向线段共有多少条?

解答　(1)以平面内10个点中每2个点为端点的线段的条数,就是从10个不同的元素中取出2个元素的组合数,即线段共有

(2)由于有向线段的两个端点中一个是起点、另一个是终点,以平面内10个点中每2个点为端点的有向线段的条数,就是从10个不同元素中取出2个元素的排列数,即有向线段共有＝10×9＝90(条)．

易错点　注意排列与组合的区别．

例8　在100件产品中,有98件合格品,2件次品．从这100件产品中任意抽出3件．

(1)有多少种不同的抽法?

(2)抽出的3件中恰好有1件是次品的抽法有多少种?

(3)抽出的3件中至少有1件是次品的抽法有多少种?

解答　(1)所求的不同抽法的种数,就是从100件产品中取出3件的组合数,所以共有＝161700(种)．

(2)从2件次品中抽出1件次品的抽法有种,从98件合格品中抽出2件合格品的抽法有种,因此抽出的3件中恰好有1件次品的抽法有

(3)解法一:从100件产品抽出的3件中至少有1件是次品,包括有1件次品和有2件次品两种情况．在第(2)小题中已求得其中1件是次品的抽法有种,因此根据分类加法计数原理,抽出的3件中至少有一件是次品的抽法有

解法二:抽出的3件产品中至少有1件是次品的抽法的种数,也就是从100件中抽出3件的抽法种数减去3件中都是合格品的抽法的种数,即C3100－C398＝161700－152096＝9604(种)．

易错点　“至少”“至多”的问题,通常用分类法或间接法求解．

经典训练

(第1题图)

1．如图所示,用6种不同的颜色给图中的4个格子涂色,每个格子涂一种颜色,要求最多使用3种颜色且相邻的两个格子颜色不同,则不同的涂色方法共有________种(用数字作答)．

2．某校开设9门课程供学生选修,其中A,B,C三门由于上课时间相同,至多选一门,学校规定每位同学选修4门,共有_________种不同选修方案．(用数字作答)

3．记者要为5名志愿者和他们帮助的2位老人拍照,要求排成一排,2位老人相邻但不排在两端,不同的排法共有(　)．

A．1440种　B．960种　C．720种　D．480种

(第4题图)

4．如图所示是某汽车维修公司的维修点分布图,公司在年初分配给A,B,C,D四个维修点的某种配件各50件,在使用前发现需将A,B,C,D四个维修点的这批配件分别调整为40,45,54,61件,但调整只能在相邻维修点之间进行,那么完成上述调整,最少的调动件次(n个配件从一个维修点调整到相邻维修点的调动件次为n)为(　)．

A．15　B．16　C．17　D．18

5．从班委会5名成员中选出3名,分别担任班级学习委员、文娱委员与体育委员,其中甲、乙二人不能担任文娱委员,则不同的选法共有_________种．(用数字作答)

6．圆上有10个点:

(1)过每2个点画一条弦,一共可画_________条弦;

(2)过每3个点画一个圆内接三角形,一共可画_________个圆内接三角形．

7．(1)凸五边形有_________条对角线;(2)凸n边形有_________条对角线．

8．计算:(1);　(2)÷．

9．甲、乙、丙、丁、戊5个足球队进行单循环比赛．(1)共需比赛多少场?(2)若各队的得分互不相同,则冠、亚军的可能情况共有多少种?

10．空间有10个点,其中任何4点不共面．(1)过每3个点作一个平面,一共可作多少个平面?(2)以每4个点为顶点作一个四面体,一共可作多少个四面体?