2012公务员-数学运算之排列组合专题

行测数学运算之排列组合专题

基本知识点回顾：

1、排列：从N不同元素中，任取M个元素（被取元素各不相同）按照一定的顺序排成一列，叫做从N个不同元素中取出M个元素的一个排列。

2、组合：从N个不同元素中取出M个元素并成一组，叫做从N个不同元素中取出M个元素的一个组合（不考虑元素顺序） 3、分步计数原理（也称乘法原理）：完成一件事，需要分成n个步骤，做第1步有m1种不同的方法，做第2步有m2种不同的方法……做第n步有mn种不同的方法。那么完成这件事共有N＝m1×m2×…×mn种不同的方法。 4、分类计数原理：完成一件事有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法……在第n类办法中有mn种不同的方法，那么完成这件事共有N= m1+ m2+…+ mn种不同的方法。

一、排列组合部分是中学数学中的难点之一，原因在于

(1)从千差万别的实际问题中抽象出几种特定的数学模型，需要较强的抽象思维能力；

(2)限制条件有时比较隐晦，需要我们对问题中的关键性词(特别是逻辑关联词和量词)准确理解；

(3)计算手段简单，与旧知识联系少，但选择正确合理的计算方案时需要的思维量较大；

(4)计算方案是否正确，往往不可用直观方法来检验，要求我们搞清概念、原理，并具有较强的分析能力。

二、两个基本计数原理及应用 (1)加法原理和分类计数法 1．加法原理

2．加法原理的集合形式 3．分类的要求

每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同(即分类不重)；完成此任务的任何一种方法，都属于某一类(即分类不漏)

(2)乘法原理和分步计数法 1．乘法原理

2．合理分步的要求

任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同

[例题分析]排列组合思维方法选讲 1．首先明确任务的意义

例1. 从1、2、3、……、20这二十个数中任取三个不同的数组成等差数列，这样的不同等差数列有________个。

分析：首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问

题。

设a,b,c成等差，∴ 2b=a+c, 可知b由a,c决定，

又∵ 2b是偶数，∴ a,c同奇或同偶，即：从1，3，5，……，19或2，4，6，8，……，20这十个数中选出两个数进行排列，由此就可确定等差数列，因而本题为C(10,2)*2*2=180

2．注意加法原理与乘法原理的特点，分析是分类还是分步，是排列还是组合 例2．在一块并排的10垄田地中，选择二垄分别种植A，B两种作物，每种种植一垄，为有利于作物生长，要求A，B两种作物的间隔不少于6垄，不同的选法共有______种。

分析：条件中“要求A、B两种作物的间隔不少于6垄”这个条件不容易用一个包含排列数，组合数的式子表示，因而采取分类的方法。 第一类：A在第一垄，B有3种选择； 第二类：A在第二垄，B有2种选择； 第三类：A在第三垄，B有1种选择， 同理A、B位置互换 ，共12种。

例3．从6双不同颜色的手套中任取4只，其中恰好有一双同色的取法有________。

(A)240 (B)180 (C)120 (D)60 分析：显然本题应分步解决。

（一）从6双中选出一双同色的手套，有6种方法； （二）从剩下的十只手套中任选一只，有10种方法。

（三）从除前所涉及的两双手套之外的八只手套中任选一只，有8种方法； （四）由于选取与顺序无关，因而（二）（三）中的选法重复一次，因而共240种。

例4．身高互不相同的6个人排成2横行3纵列，在第一行的每一个人都比他同列的身后的人个子矮，则所有不同的排法种数为_______。

分析：每一纵列中的两人只要选定，则他们只有一种站位方法，因而每一纵列的排队方法只与人的选法有关系，共有三纵列，从而有C(6.2)*C(4.2)*C(2.2)=90种。

例5．在11名工人中，有5人只能当钳工，4人只能当车工，另外2人能当钳工也能当车工。现从11人中选出4人当钳工，4人当车工，问共有多少种不同的选法? 分析：采用加法原理首先要做到分类不重不漏，如何做到这一点？分类的标准必须前后统一。

以两个全能的工人为分类的对象，考虑以他们当中有几个去当钳工为分类标准。 第一类：这两个人都去当钳工，C(5.2)*C(4.4)=10

第二类：这两人有一个去当钳工， C(2.1)*C(5.3)*C(5.4)=100 第三类：这两人都不去当钳工， C(5.4)*C(6.4)=75

因而共有185种。

例6．现有印着0，l，3，5，7，9的六张卡片，如果允许9可以作6用，那么从中任意抽出三张可以组成多少个不同的三位数?

分析：有同学认为只要把0，l，3，5，7，9的排法数乘以2即为所求，但实际上抽出的三个数中有9的话才可能用6替换，因而必须分类。 有0无9 6*4＝24 有9无0 6*6*2=72 有9有0 4*4*2=32 无9无0 4×6＝24

因此共有152种方法。

5*5*4*2-4*4*3=152,

例7．停车场划一排12个停车位置，今有8辆车需要停放，要求空车位连在一起，不同的停车方法是________种。

分析：把空车位看成一个元素，和8辆车共九个元素排列，因而共有P(9.8)种停车方法。

3．特殊元素，优先处理；特殊位置，优先考虑

例8．六人站成一排，求

(1)甲不在排头，乙不在排尾的排列数

(2)甲不在排头，乙不在排尾，且甲乙不相邻的排法数 分析：

（1）先考虑排头，排尾，但这两个要求相互有影响，因而考虑分类。 第一类：乙在排头，有P(5.5)种站法。

第二类：乙不在排头，当然他也不能在排尾，有C(4.1)C(4.1)P(4.4)种站法， 法2:P(6.6)-P(5.5)*2+P(4.4) （2）

第一类：甲在排尾，乙在排头，有种方法。 第二类：甲在排尾，乙不在排头，有种方法。 第三类：乙在排头，甲不在排头，有种方法。 第四类：甲不在排尾，乙不在排头，有种方法。 共312种。

法2:甲乙相邻的排法数

C(4,1)*C(3,1)*2*P(3,3)+P(4,4)+P(4,4)=192 头尾取非甲乙，乙头，甲尾。 504-192=312

例9．对某件产品的6件不同正品和4件不同次品进行一一测试，至区分出所有次品为止。若所有次品恰好在第五次测试时被全部发现，则这样的测试方法有多少种可能?

分析：本题意指第五次测试的产品一定是次品，并且是最后一个次品，因而第五

次测试应算是特殊位置了，分步完成。 第一步：第五次测试的有C(4.1)种可能； 第二步：前四次有一件正品有C(6.1)种可能。 第三步：前四次有P(4.4)种可能。 C(4.1)*C(6.1)*P(4.4)

4．捆绑与插空

例10. 8人排成一队 (1)甲乙必须相邻 (2)甲乙不相邻

(3)甲乙必须相邻且与丙不相邻 (4)甲乙必须相邻，丙丁必须相邻 (5)甲乙不相邻，丙丁不相邻

分析：

(1)甲乙必须相邻 ，就是把甲乙 捆绑(甲乙可交換) 和7人排列 P(7.7)*2 (2)甲乙不相邻 P(8.8)-P(7.7)*2 (3)甲乙必须相邻且与丙不相邻

先求甲乙必须相邻且与丙相邻 P(6.6)*2*2

甲乙必须相邻且与丙不相邻 P(7.7)*2-P(6.6)*2*2 (4)甲乙必须相邻，丙丁必须相邻 P(6.6)*2*2 (5)甲乙不相邻，丙丁不相邻 P(8.8)-P(7.7)*2*2+P(6.6)*2*2

例11. 某人射击8枪，命中4枪，恰好有三枪连续命中，有多少种不同的情况? 分析：∵ 连续命中的三枪与单独命中的一枪不能相邻，因而这是一个插空问题。另外没有命中的之间没有区别，不必计数。即在四发空枪之间形成的5个空中选出2个的排列，即P(5.2).

例12. 马路上有编号为l，2，3，……，10 十个路灯，为节约用电又看清路面，可以把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，在两端的灯也不能关掉的情况下，求满足条件的关灯方法共有多少种?

分析：即关掉的灯不能相邻，也不能在两端。又因为灯与灯之间没有区别，因而问题为在7盏亮着的灯形成的不包含两端的6个空中选出3个空放置熄灭的灯。 ∴ 共C(6.3)=20种方法。

例13. 三个相同的红球和两个不同的白球排成一行，共有多少种不同的方法? 分析：

三个相同的红球,有4個空，两个不同的白球， 可以一個一個插，也可以2個一起插、

P(4.2)+P(4.1)*2=20

4．间接计数法.(1)排除法

例14. 三行三列共九个点，以这些点为顶点可组成多少个三角形? 分析：有些问题正面求解有一定困难，可以采用间接法。

所求问题的方法数=任意三个点的组合数-共线三点的方法数，C(9.3)-8

例15．正方体8个顶点中取出4个，可组成多少个四面体?

分析：所求问题的方法数=任意选四点的组合数-共面四点的方法数， ∴ 共C(8.4)-12=70-12=58个。

例16. l，2，3，……，9中取出两个分别作为对数的底数和真数，可组成多少个不同数值的对数?

分析：由于底数不能为1。

（1）当1选上时，1必为真数，∴ 有一种情况。 （2）当不选1时，从2--9中任取两个分别作为底数，真数，共P(8.2)其中log2 4=log3 9，log4 2=log9 3, log2 3=log4 9, log3 2=log9 4. 因而一共有P(8.2)+1-4=53个。

例17. 六人排成一排，

要求甲在乙的前面，(不一定相邻)，共有多少种不同的方法? 如果要求甲乙丙按从左到右依次排列呢? 分析：

1.实际上,甲在乙的前面和甲在乙的后面两种情况对称,具有相同的排法数。因而有P(6.6)/2=360种。 2.先考虑六人全排列；其次甲乙丙三人实际上只能按照一种顺序站位，因而前面的排法数重复了P(3.3)种， ∴ 共P(6.6)/P(3.3)=120种。

例18．5男4女排成一排，要求男生必须按从高到矮的顺序，共有多少种不同的方法?

分析：首先不考虑男生的站位要求，共P(9.9)种；男生从左至右按从高到矮的顺序，只有一种站法，因而上述站法重复了P(5.5)次。因而有P(9.9)/P(5.5)=9×8×7×6=3024种。

若男生从右至左按从高到矮的顺序，只有一种站法， 同理也有3024种，综上，有6048种。

5．挡板的使用

例20．10个名额分配到八个班，每班至少一个名额，问有多少种不同的分配方法?

分析：把10个名额看成十个元素，在这十个元素之间形成的九个空中，选出七个位置放置档板，则每一种放置方式就相当于一种分配方式。因而共C(9.7)=36种。

6．注意排列组合的区别与联系：所有的排列都可以看作是先取组合，再做全排列；同样，组合如补充一个阶段(排序)可转化为排列问题。

错因： ５个教师是互不相同的，而用挡板时，要求这些元素必须相同.即把问题改为：把５个名额分配给３个班，每班至少有１人.问有几种不同的分法？５个名额是没有区别顺序的.可用挡板法解决.

正解：先把５位老师分成三堆，有两类：１、１、３和１、2、2分别有

和种，再分到三个班里，共有＝１５０种.

【点评】 类似上面的分配问题，当元素有区别时，要利用分组办法解决，当元素无区别时，可用挡板模型来解决. 3. 挡板模型与双排问题 在元素无区别分配问题中，通常考虑用挡板模型来解决，但一定要注意题目给出的条件，否则极易出错.

【例５】 从５个班中选１０人组成一个篮球队（无任何要求），有几种选法？ 错解： 选把１０个指标排好，插入９块挡块：０|０|０|０|０|０|０|０|０|０

然后在９块挡板中任取４块即可分成５份，有

＝１２６种分法.

错因： 问题并没有给出“每班至少１人”这个条件，而采用挡板解决时，实际上它就是要求每班至少有１人参加.事实上，这１０个名额可给一个班，也可给两个班…

正解：因为把１０个指标分成５个部分，只须４块挡板，称为第一类元素，１０个指标为第二类元素，共１４个元素.当这些元素都有区别时共有

种排法.

但１０个指标，４块挡板各组之间不管怎么变化，其实就是一种情况的共有

＝１００１种不同分法（或）.

【点评】 当分组数超过３个时，若没有给出“每组至少有１个”这个条件时，是不能用挡板法解决的，而要用双排列方法解决.而双排问题就是把元素分成相同的两类，然后加以解决.

两类元素排列的问题涉及面很广，它实质上就是有重复元素排列的一种简单情形，在历年的公考中时有出现，应予以重视.

天字一号的排列组合题

一） 1,2,3,4作成数字不同的三位数，试求其总和？但数字不重复。[解析]组成3位数我们以其中一个位置(百位,十位,个位)为研究对象就会发现当某个位置固定比如是1,那么其他的2个位置组成3位数 我们以其中一个位置(百位,十位,个位)为研究对象就会发现 当某个位置固定 比如是1,那么其他的2个位置上有多少种组合? 这个大家都知道 是剩下的3个数字的全排列 P32

我们研究的位置上每个数字都会出现P32次 所以每个位置上的数字之和就可以求出来了 个位是:P32*(1+2+3+4)=60 十位是:P32*(1+2+3+4)*10=600 百位是:P32*(1+2+3+4)*100=6000 所以总和是6660

（二） 将“PROBABILITY ”11个字母排成一列，排列数有______种，若保持P, R, O次序，则排列数有______种。 [解析]

这个题目就是直线全排列出现相同元素的问题:在我的另外一个帖子里面有介绍:http://bbs.qzzn.com/read-htm-tid-9487547.html (1)我们首先把相同元素找出来,B有2个, I 有2个 我们先看作都是不同的11个元素全排列 这样就简单的多是P11,11 然后把相同的元素能够形成的排列剔除即可 P11/(P2,2*P2,2)=9979200。

(2)第2个小问题 因要保持PRO的顺序，就将PRO视为相同元素（跟B，I类似的性质），则其排列数有11！/（2！×2！×3！）= 166320种。

（三） 李先生与其太太有一天邀请邻家四对夫妇共10人围坐一圆桌聊天，试求下列各情形之排列数：

 （1）男女间隔而坐。 （2）主人夫妇相对而坐。  （3）每对夫妇相对而坐。  （4）男女间隔且夫妇相邻。 （5）夫妇相邻。

（6）男的坐在一起，女的坐在一起。 [解析]

(1) 这个问题也在http://bbs.qzzn.com/read-htm-tid-9487547.html介绍过 先简单介绍一下环形排列的特征,环形排列相对于直线排列缺少的就是参照物.第一个坐下来的人是没有参照物的,所以无论做哪个位置都是一样的. 所以从这里我们就可以看出 环形排列的特征是 第一个人是做参照物,不参与排列. 下面就来解答6个小问题:

(1)先让5个男的或5个女的先坐下来 全排列应该是 P44, 空出来的位置他们的妻子(丈夫), 妻子(丈夫)的全排列这个时候有了参照物所以排列是P55 答案就是 P44*P55=2880种

(2)先让主人夫妇找一组相对座位入座 其排列就是P11(记住不是P22 ),这个时候其他8个人再入座,就是P88,所以此题答案是 P88

(3)每对夫妇相对而坐,就是捆绑的问题.5组相对位置有一组位置是作为参照位置给第一个入座的夫妇的,剩下的4组位置就是P44, 考虑到剩下来的4组位置夫妇可以互换位置即 P44*2^4=384

(4)夫妇相邻,且间隔而坐. 我们先将每对夫妇捆绑 那么就是5个元素做环形全

排列 即P44 这里在从性别上区分 男女看作2个元素 可以互换位置 即答案是P44*2=48种(值得注意的是,这里不是*2^4 因为要互换位置,必须5对夫妇都得换 要不然就不能保持男女间隔)

(5) 夫妇相邻 这个问题显然比第4个问题简单多了,即看作捆绑 答案就是P44 但是这里却是每对夫妇呼唤位置都可以算一种方法的. 即 最后答案是P44*2^5

(6)先从大方向上确定男女分开座,那么我们可以通过性别确定为2个元素做环形全排列.即P1,1 , 剩下的5个男生和5个女生单独做直线全排列 所以答案是P1,1 *P55*P55

（四）在一张节目表中原有8个节目，若保持原有节目的相对顺序不变，再增加三个节目，求共有多少种安排方法？ [解析]

这个题目相信大家都见过 就是我们这次2008年国家公务员考试的一道题目: 这是排列组合的一种方法 叫做2次插空法或多次插空法 直接解答较为麻烦，我们知道8个节目相对位置不动,前后共计9个间隔,故可先用一个节目去插9个空位，有C9取1种方法；这样9个节目就变成了10个间隔,再用另一个节目去插10个空位，有C10取1种方法；同理用最后一个节目去插10个节目形成的11个间隔中的一个，有C11取1方法，由乘法原理得：所有不同的添加方法为9*10*11=990种。

方法2: 我们先安排11个位置,把8个节目按照相对顺序放进去,在放另外3个节目,11个位置选3个出来进行全排列 那就是P11,3=11*10*9=990

（五） 0，1，2，3，4，5五个数字能组成多少个被25整除的四位数？

[解析] 这里考察了一个常识性的问题 即 什么样数才能被25整除 即这个数的后2位必须是25或者50，或者75或者00 方可.

后两位是25的情况有:千位只有3个数字可选(0不能) 百位也是3个可选 即3*3=9种

后两位是50的情况有:剩下的4个数字进行选2位排列 P4,2=12种 75不可能，因为数字中没有7 00也不可能，因为数字不能重复 共计 9+12=21种

环状排列：又称圆排列, 是讲事物沿着一圆周來作排列, 只考虑事物的相对位

置, 而不计较各物件所在的实际位置。 此排列可旋转, 但不可翻转。底下先看一个问题:

甲乙丙三人围一圆桌而坐, 共有几种坐法? 解这个问题, 我们先考虑甲乙丙三人做直线排列的状况:

(圖1)

(圖2)

共计6种情形。若将(圖1)的直线排列首尾相接, 成为一圈, 如(圖3)

(圖3)

我们可以发现(圖3)的中间与右边两圆, 都是左边的圆逆时针旋转的结果, 所以应属于同一类圆。

同理, 若将(圖2)的直线排列首尾相接, 成为一圆, 如(圖4), 也可发现此三个也属于同一类。

故共有 种排列方式。

所以若个不同事物在做环状排列时, 先求其直线排列, 因每个排列方式中,

在环状排列均视为同一种。故环状排列数为直线排列数/排列之个数。底下我们给出『环状排列』的公式：

(1) 个不同物件的环状排列数为

(2) 个不同物件中, 任取 个的环状排列数为 。

接下來我們介紹『項鍊排列』, 因項鍊沒有正反面之分, 所以項鍊排列數就是環狀排列數除以2。

【例1】五對夫婦圍圓桌而坐, 試問男女相間坐的方法數為何?

先直線排列:

故環狀排列數為 。

【例2】五對夫婦圍圓桌而坐, 試問每對夫妻相鄰而坐的方法數為何?

先直線排列:

故環狀排列數為 。

【例3】有8個不同顏色的珠子, 全部串成一項圈, 試問其方法數有多少種? [解]:

先將其想像成8個不同的物品做環狀排列, 故其方法數有,

其次因項鍊沒有正反面之分, 故須除以2, 所以共有種。

【例4】有8個不同顏色的珠子, 取6個串成一項鍊, 試問其方法數有多少種？ [解]:P86/6*2=1680

【例5】四對夫妻圍圓桌而坐, 下列各情況, 各有幾種坐法?

(1) 男女相隔且夫妻相鄰, (2) 每對夫妻相對,

(3) 恰有三對夫妻相鄰, (4) 夫妻不相鄰且男女相間隔。 (1) 12, (2) 48, (3) 384, (4) 12。

【例6】李先生與其太太有一天邀請社區4對夫婦共10人圍成一桌吃飯， 求下列各情形的排列數：

(1)任意入坐。 (2)男女相間而坐。 (3)主人夫婦相對而坐。 (4)每對夫婦相對而坐。 (5)男女相間夫婦相鄰。 (6)夫婦相鄰。 (1)9! (2)4!5! (3)8! (4)4!24 (5)4! 2 (6)4!25

【例7】五對夫婦共10人，圍一圓桌而坐，求下列各條件的坐法有幾種： (1) 男女相間隔。 (2) 每對夫婦均相鄰。 (3) 夫婦相鄰且男女相間隔。 (4) 每對夫婦相對。

【解】(1)五位先生先坐，有 ( 5－1 ) !＝4! ( 種 ) 坐法，

太太再坐入「×」的位置，有5! 種坐法， 故共有4!×5!＝2880 ( 種 ) 坐法

(2) 每對夫婦各視為一體，5個個體圍圓桌而坐，有 ( 5－1 ) !＝4! ( 種 ) 坐法，

上述每種坐法，每對夫婦可互換位置，有25種方法， 故共有4!×25＝768 ( 種 ) 坐法

(3) 5位先生先坐，有 ( 5－1 ) !＝4! ( 種 ) 坐法，

上述每種坐法中，5位太太只有2種坐法 ( 都坐自己先生的左方或右方 )，

故共有4!×2＝48 ( 種 ) 坐法 (4)解一、

1 先讓一對夫婦入坐，坐法只有1種，再讓其餘4對夫婦入○

坐，有4! 種坐法

2 上述每種坐法中，其餘4對夫婦的每對夫婦可互換位置，方法有24○種

故共有1×4!×24＝384 ( 種 ) 坐法

解二、先选1人入坐，对面的人就固定了，有1种，从8个人再选1人入坐，有8种，再从剩下的6人中选1人，有6种，接着从剩下的4人中选1人，有4种，最后从剩下的2人中选1人，有2种。 8*6*4*2=384种。

【例8】6位男生與6位女生圍一圓圈跳土風舞，請問：

(1) 6位男生排在一起，6位女生排在一起，排法有幾種？ (2) 男女相間隔的排法有幾種？

【解】(1) 將6位男生視為一體，6位女生也視為一體，2個個體的環狀排

列只有1種排法，

而6位男生的直線排列，有6! 種排法，6位女生的直線排列也有6! 種排法，

故共有1×6!×6!＝518400 ( 種 ) 排法

(2) 6位男生先作環狀排列，有 ( 6－1 ) !＝5! ( 種 ) 排法， 然後6位女生再分別排入男生的間隔中，有6! 種排法，

故共有5!×6!＝86400 ( 種 ) 排法

本文来源：https://www.bwwdw.com/article/wogf.html