元素不尽相异的排列问题

有关重复的排列组合问题我们常见的排列、组合问题，其中的元素通常是不可重复的，下面我们看几类可重复的排列、组合问题。

一. 有重复排列–––分步计数原理例1. 4个同学争夺3项竞赛冠军，冠军获得者共有几种可能情况？解：完成这件事情可分三步：〔1〕第一项冠军有4种可能；〔2〕第二项冠军有4种可能；〔3〕第三项冠军有4种可能。

所以可能情况有：4×4×4＝64〔种〕。

一般地，从n 个不同元素里取出允许重复的m 个元素，按一定顺序排成一列，那么，第1、第2、…、第m 个位置上选取元素的方法都有n 种。

由分步计数原理得每次从n 个不同元素里取出允许重复的m 个元素的排列数为：N n n n n m n m n N m n m =⋅⋅⋅⋅=∈≤ (,,)*相关练习：用0，1，2，…，9这10个数字可组成多少个8位数字的 号码？〔108〕二. 不尽相异元素的排列–––组合法例2. 小麦、大麦品种各1种，种在5种不同土质的试验田里，3块种小麦，2块种大麦，有多少种种法？解：这5个不尽相异的元素有3个相同，另2个相同，所以共有：C C 535210==〔种〕种法。

一般地，在n 个不尽相异的元素里，如果有m 1个元素相同，又有m 2个元素相同，并且m 1＋m 2＝n ，那么这n 个元素的不同排列种数N C C n m n m==12。

三. 相同元素分组––––隔板法例3. 5个相同小球放到4个不同盒子里，每盒至少有1个，共有多少种放法？ 解法1：每盒先放入1球，剩下1球任选1盒，共有：C 414=〔种〕放法。

解法2：〔第一隔板法〕5个小球可形成6个空隙，由于每盒至少放1个小球，所以除去两边空隙还剩4个空，只要在这4个位置上隔进3个板，即可满足要求。

所以有：C 434=〔种〕放法。

例4. 将5个相同小球放到4个不同盒子里〔盒子可空〕，共有多少种放法？ 解法1：〔分类法〕第一类：全部放入1个盒子里，有：C 414=〔种〕放法；第二类：放入2个盒子里，有：C 42424⨯=〔种〕放法；第三类：放入3个盒子里，有：C 43624⨯=〔种〕放法；第四类：放入4个盒子里，有4种放法。

排列中的问题与方法本文主要介绍了排列中的几类问题：相异元素不许重复的排列问题、相异元素允许重复的排列问题、不尽相异元素的排列问题。

其中，比较简单的问题的相关例题只给出了答案，复杂的问题详细的解答和评注。

本文主要适合数学基础较好的学生和教师阅读。

一、两个基本原理如果完成一件事件有几类办法，每类办法有若干种不同的方法，而这些方法彼此互相独立（不论采取哪一类办法中的哪一种方法都能达到完成这一事件目的），那么用加法原理求解．如果完成一件事件必须分几个步骤，每个步骤可以有若干种不同的方法，而这些步骤是相互依赖的（只有依次连续完成各个步骤，这一事件才算完成），那么用乘法原理求解．二、排列1. 相异元素不许重复的排列问题例１ 用０到９这十个数字，可以组成多少个没有重复数字的四位数？（答案：3298482296A A +⨯⨯=）环状排列：元素环绕在一条封闭的曲线上的排列．例２ 将６盆不同品种的菊花安放在圆形花台的周围，有几种不同的安置方法？思考 显然，将６盆围城一圈和放成一排，从相对顺序来看是不同的．放成一排，有头有尾；围成一圈，无首尾之分．我们用,,,,,a b c d e f 代表６盆菊花，就图１－１来考察．一列，那么就得到６种不同的排法：abcdef bcdefa cdefabdefabc efabcd fabcde 一种排列时就有６种．这样，原题就归结为相异元素不许重复的线状排列问题．解 设不同的放置方法有x 种，则相对的线状排列有6x 种．666x A = 65651206A x A ∴=== 评注 把本题的思路推广到一般情形，有1) n 个相异元素的环状全排列的种数：11n n A --；2) 从n 个相异元素里，每次取出m 个相异元素的环状排列的种数：m n A m． 2. 相异元素允许重复的排列问题例３ 有３封信，投入４个信箱，有几种投信方法？（答案：3464=）3. 不尽相异元素的排列问题例４ 把４个相同的红球，３个相同的白球，３个相同的蓝球，２个相同的黄球和一个黑球排成一列，有多少种不同的排列方法？思考 这是一个不尽相异元素的全排列问题．解题的关键是把原题转化为相异元素的全排列问题，为了便于探索解题途径，不妨先考察下面的简化问题：把４个相同的红球和３个相同的白球排成一列，有多少种不同的方法？用字母,R W 分别表示红球和白球，则问题就是求４个相同的元素R 和３个相同的元素W 的全排列种类．我们用递推的方法来分析，设所求的全排列有x 种，在其中任取一种，如：RWWRWRR ⑴固定W 的位置，把４个R 的位置空下来，即WW W用1234,,,R R R R ４个相异元素排在这四个空位上，显然就有4!种排法．这就是说，经过上述替换，排列⑴可以变成4!种新排列．因此，x 种所求排列就变成了4!x 种新排列了． 同样，在4!x 种新排列中，任取一种，如：2314R WWR WR R ⑵ 固定1234,,,R R R R 的位置，把W 的位置空下来，即2314R R R R以123,,W W W ３个相异元素排在空位上，有3!种排法．这就是说，经过第二次替换，排列⑵又变成了3!种新排列．经过两次替换，所求x 种不尽相异元素的全排列，变成了4!3!x 种７个相异元素的全排列．即得4!3!7!x = 7!354!3!x ∴==． 循着上述思路，原题即可得解．解 设不同的排列方法有x 种，即 4!3!3!2!1!(43321)!x =++++ 13!36036004!3!3!2!1!x ∴==． 评注本题是一个不尽相异元素的全排列问题．一般的，n 个不尽相异元素，全部取出来排列，叫做n 个不尽相异元素的全排列，简称n 元全排列．如果把解题思路推广到一般情形，有在n 个不尽相异元素里，如果其中1n 个元素是相同的一类；2n 个元素是相同的一类；…；m n 个元素是相同的一类．而12m n n n n ++⋅⋅⋅+=，则这n 个元素的全排列种数是12!!!!m n n n n ⋅⋅⋅．。

公务员考试行测数量关系：排列组合异素不均分的分堆与分配问题公务员考试行测卷中，要说最难的题型，可能一千个读者心中有一千个哈姆雷特，各有各的说法。

但是要说到最容易出错的题型，那非排列组合不可。

但是排列组合在目前的公务员考试中尤其是国考，几乎是每年必考的题型，所以还是需要花精力去学习掌握。

今天带大家一起来学习其中的一个小知识点，即异素不均分的分堆与分配问题，主要是为了和我们之前所说的异素均分的分堆与分配形成对比和区分。

一、异素不均分的分堆与分配概念并不难理解，所谓的异素，就是指被分的元素是不相同的，有区别的。

而不均分则是指分完后每一份数量不一样，比如说四个不同颜色的小球，分作两份，分别为1个和3个，这就是个异素不均分的问题。

而分堆与分配，又是有区别的，分堆就是把元素按照要求分开就行，比如说分成1个和3个，就可以了。

分配则是在分堆的基础上需要将分好的堆再分配给相应的对象。

比如说4个颜色不同的小球，分给小王和小李，其中一人拿3个，另一人则拿1个，这就是不均分的分配问题。

二、实际应用中的具体计算方法我们通过一个例题来理解两种不同的分堆分配方式的具体计算。

例1：将标有A、B、C、D的四本书分作两组，其中一组3本，一组1本，有多少种分法【参考解析】通过上边的描述我们知道，这属于异素不均分的分堆问题，直接按照分步思想来操作就可以了，第一步从4本书中选出3本，第二步则选出剩下的1本，即所以当我们把不同元素进行不均分分堆时，只需要按照基本的分步思想去操作即可。

例2：将标有A、B、C、D的四本书分给甲、乙两个人，其中甲1本，乙2本，有多少种分法【参考解析】这个题属于不均分分堆之后的指定分配，当我们分好堆的时候，其实已经确定了每一堆的归属，所以计算方式和结果，和例题1是一样的。

例3：将标有A、B、C、D的四本书分给甲、乙两个人，其中有人拿1本，有人拿3本，有多少种分法【参考解析】这个题属于不均分分堆之后的随机分配，当我们分好堆的时候，还不确定每一堆的归属，所以在计算的时候，还需要增加一步，即把两堆数量不同的书分给两个人，即希望大家可以多做练习，熟练掌握技巧。

例析排列组合问题类型及解题常用方法排列组合问题一般可分为相异元素不许重复的排列组合问题，相异元素允许重复的排列组合问题和不尽相异元素的排列组合问题.对于复杂的排列组合问题往往是对元素或位置进行限制，因此掌握一些基本排列组合的题型对学好本节内容是很有必要的.一、相异元素不许重复的排列组合问题1. 若对元素无特殊要求，这类问题比较简单，直接运用排列数、组合数定义就可以解决，只需分清是组合问题还是排列问题即可.例1 有北京、上海、广州三个车站，需准备几种车票？有几种票价？解析车票与起点、终点顺序有关，故是排列问题；而票价与顺序无关，故是组合问题. 因此有[A23=6]种车票，有[C23=3]种票价.2. 相异元素有限制条件的排列问题，常用方法有：特殊元素优先法、相邻问题捆绑法、相邻问题插入法等.例2 6人站成一排，其中甲既不站在最左端也不站在最右端，有多少种不同的站法？解析因为甲不能站在左、右两端，故第一步考虑甲，除去两端位置甲有4种站法；第二步让其余的5人站在其他5个位置上，有[A55=120]种站法.故满足题目条件的站法共有[4×A55=480]种.例3 5个男生和3个女生排成一排，3个女生必须排在一起，有多少种不同的排法？解析将3个女生看成一个元素，与5个男生进行排列，共有[A66=720]种排法；然后女生内部再进行排列，有[A33=6]种排法.故共有[A66A33=4320]种排法.点拨对于某些元素要求排在一起的问题，可用“捆绑法”将这些元素看作一个整体、看作一个元素，与其他元素进行排列，然后相邻元素间内部再进行排列.例4 7人排成一排，甲、乙、丙3人互不相邻有多少种排法？解析先将其余4人排成一排，有[A44=24]种排法，再将甲、乙、丙3人插入其余4人之间和两端的5个缝隙中，有[A35=60]种排法，故共有[A44A35=1440]种排法.点拨对于某些元素要求间隔排列的问题一般运用插入法. 在插入时，要先排无限制条件的元素，再将不相邻的元素插入已排好元素位置间的缝隙中.例5 有9本不同的书，分成3堆.（1）每堆3本有多少种不同的分法；（2）一堆5本，其他两堆各2本，有多少种不同的分法；（3）若一堆4本，一堆3本，一堆2本有多少种不同的分法.解析（1）此分堆属于平均分组问题，并且不计每堆顺序，所以分堆方法共有[C39C36C33A33=560]种.（2）分堆中，有两堆是均匀的，故有[C59C24C22A22=378]种.（3）非均匀分堆，由于不知3堆中哪一堆4本，哪一堆3本，哪一堆2本，故有[C49C35C22]=1260种.点拨对于分组、分堆问题，要注意是“均匀分”还是“非均匀分”，均匀分组要除以分组数的全排列数（堆与堆之间没有顺序），而不均匀分组则不用除以分组数的全排列数.二、相异元素允许重复的排列组合问题不能直接用[Amn]解决，因元素可重复出现，往往需分步考虑，运用计数乘法原理来解决.例6 有3封信和4个邮筒，则将信投入邮筒的所有不同投法种数有（）A. [A34]B. [43]C.[34]D.[C34]解析 [Amn]，[Cmn]只能表示没有重复的排列组合问题，而本题中明显可以将多封信投入到一个邮筒中，是一个可重复问题，应考虑运用分步原理来做. 每封信都有4种可能的投法，故有[4×4×4=64]种不同的投法.答案 B例7 用5种不同的颜色给图中4个区域涂色，若每一区域涂一种颜色，相邻区域不能同色，共有多少种涂色方法.[1][2][3][4]解析这是一道染色排列组合问题，很容易错误地认为就是[A45=120]，但仔细分析可知，1，3区域可以同色，故应分步考虑. 先涂区域2有5种方法，再涂区域4有4种方法，剩下三种颜色涂区域1，3各有3种方法，故共有[5×4×3×3=180]种涂法.点拨对于这类染色问题，一般采取分步或分类计数的方法进行解决.三、不尽相异的元素的排列组合问题这类排列组合问题，直接考虑很难解决，分类讨论又十分麻烦. 有些排列组合问题，从表面上看是不尽相异的元素排列组合，但若交换元素与位置关系，运用转化思想，变换角度来考虑，问题就可能转化为相异元素的排列组合问题.例8 有2个a，3个b，4个c，共9个字母排列成一排，有多少种排法？解析将9个字母看作元素，1～9位置作为位子，这是一个不尽相异元素的全排列.若转换角度，将1～9号位置作元素，字母作位置，那么问题就转化为一个相异元素不许重复的组合问题，故有[C29C37C44=1260]种不同的排法.例10 3面红旗、2面黄旗，全部都升上旗杆作信号，共能表示多少种不同的信号？解析由于同色旗间没有顺序，因此只用考虑红旗或黄旗中的一种在5个空处的位置即可，故有[C35=C25=10]种信号.例11 从5个班中选10人组成校篮球队，每班至少1人，有多少种选法？解析这是一道选人问题，只要把人选出来就可以了，不用考虑顺序，因此可以将10个人看成10个相同的小球，放入5个不同的盒子中，每个盒子至少1球，可先把10个球排成一排，再在其中9个间隙中选4个位置插入4块“挡板”，将总体分成5个部分对应着5个盒子，故有[C49=126]种选法，这种计数方法叫做隔板法，可专门用来解决同种元素的分配问题.以上是对一些常见排列组合问题的分类和小结，它们对应着不同的题型，在解题过程中需灵活多变，其实在解决大多数计数问题时，往往要交叉用到排列、组合，不能拘泥于某种分类，但必须要清楚排列和组合间的区别.。

排列与组合的八大典型错误（一）一．知识点归纳1．排列的概念：从n 个不同元素中，任取m （m n ≤）个元素（这里的被取元素各不相同）按照一定的顺序．．．．．排成一列，叫做从n 个不同元素中取出m 个元素的一个排列．．．．2．排列数的定义：从n 个不同元素中，任取m （m n ≤）个元素的所有排列的个数叫做从n 个元素中取出m 元素的排列数，用符号mn A 表示3．排列数公式：(1)(2)(1)m n A n n n n m =---+ （,,m n N m n *∈≤）4阶乘：!n 表示正整数1到n 的连乘积，叫做n 的阶乘规定0!1=．5．排列数的另一个计算公式：m n A =!()!n n m -6组合的概念：一般地，从n 个不同元素中取出m ()m n ≤个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合7．组合数的概念：从n 个不同元素中取出m ()m n ≤个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数．．．．用符号m n C 表示．8．组合数公式：(1)(2)(1)!m m n nm m A n n n n m C A m ---+== 或)!(!!m n m n C m n -=),,(n m N m n ≤∈*且9组合数的性质1：m n nm n C C -=．规定：10=n C ；10．组合数的性质2：m n C 1+＝m n C +1-m nC 02413512n n n n n n n C C C C C C -+++=+++= ;012n nn n n C C C ++= 11.“16字方针”是解决排列组合问题的基本规律，即：分类相加，分步相乘，有序排列，无序组合，。

12.“２4个技巧”是迅速解决排列组合的捷径二．基本题型讲解例1分别求出符合下列要求的不同排法的种数,（1）6名学生排3排，前排1人，中排2人，后排3人；（2）6名学生排成一排，甲不在排头也不在排尾；（3）从6名运动员中选出4人参加4×100米接力赛，甲不跑第一棒，乙不跑第四棒；（4）6人排成一排，甲、乙必须相邻；（5）6人排成一排，甲、乙不相邻；（6）6人排成一排，限定甲要排在乙的左边，乙要排在丙的左边（甲、乙、丙可以不相邻）.解：（1）分排坐法与直排坐法一一对应，故排法种数为72066=A （2）甲不能排头尾，让受特殊限制的甲先选位置，有14A 种选法，然后其他5人选，有55A 种选法，故排法种数为4805514=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）后排列数为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件的抽法，共有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件的抽法，那么所得结果是46628839823=C C 种，其结论是错误的，错在“重复”：假设3件次品是A 、B 、C ，第一步先抽A 、B 第二步再抽C 和其余2件正品，与第一步先抽A 、C （或B 、C ），第二步再抽B （或A ）和其余2件正品是同一种抽法，但在算式39823C C 中算作3种不同抽法例3求证：①m nm 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 --+⋅-==-()==-m n A m n n !!右另一种证法：（利用排列的定义理解）从n 个元素中取m 个元素排列可以分成两类：①第一类不含某特殊元素a 的排列有mn A 1-第二类含元素a 的排列则先从()1-n 个元素中取出()1-m 个元素排列有11--m n A 种，然后将a 插入，共有m 个空档，故有11--⋅m n A m 种，因此m nm 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 ＝()()()()()()()==+-++=+++-+=++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 ，需要确定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+6=19（个）点评：问题（1）可套用投信模型：n 封不同的信投入m 个不同的信箱，有n m 种方法；问题（2）的关键结合映射概念恰当确定分类标准，做到不重、不漏例5四面体的顶点和各棱的中点共10个点（1）设一个顶点为A ，从其他9点中取3个点，使它们和点A 在同一平面上，不同的取法有多少种？（2）在这10点中取4个不共面的点，不同的取法有多少种？解：（1）如图，含顶点A 的四面体的三个面上，除点A 外都有5个点，从中取出3点必与点A 共面，共有353C 种取法含顶点A 的棱有三条，每条棱上有3个点，它们与所对棱的中点共面，共有3种取法根据分类计数原理和点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 （种）点评：由点构成直线、平面、几何体等图形是一类典型的组合问题，附加的条件是点共线与不共线，点共面与不共面，线共面与不共面等三、排列组合解题备忘录：⑴ｍ个不同的元素必须相邻，有m mP 种“捆绑”方法⑵ｍ个不同元素互不相邻，分别“插入”到ｎ个“间隙”中的ｍ个位置有m n P 种不同的“插入”方法⑶ｍ个相同的元素互不相邻，分别“插入”到ｎ个“间隙”中的ｍ个位置，有m n C 种不同的“插入”方法⑷若干个不同的元素“等分”为ｍ个组,要将选取出每一个组的组合数的乘积除以m m P (去除重复数)四．排列组合问题中的数学思想方法（一）．分类讨论的思想：许多“数数”问题往往情境复杂，层次多，视角广，这就需要我们在分析问题时，选择恰当的切入点，从不同的侧面，把原问题变成几个小问题，分而治之，各种击破。

数学竞赛讲义：排列与组合【赛点直击】一、两个基本原理加法原理 设A 为完成一件事情的所有方法的集合，它可以划分为n 个互不相交的非空子集A 1，A 2，…，A n ，|A i |=m i (i=1,2,…,n)，那么完成这件事情的总方法数为：N=|A|=m 1+m 2+…+m n ；使用加法原理的关键在于对所计数的对象进行完全分类．乘法原理 设A 为完成一件事情的所有方法的集合，且完成这件事情需要几个步骤，实现第i(i=1,2,…,n)个步骤的方法的集合为A i ，|A i |=m i ,那么完成这件事情的总方法数为N=|A|=m 1×m 2×…×m n ；使用乘法原理的关键在于对所计数的对象进行完全分步． 二、相异元素的排列与组合（1）从n 个不同元素中，任取m 个不同元素的排列数是!(1)(1)()!mn n A n n n m n m =⋅-⋅⋅-+=-；（2）从n 个不同元素中，任取m 个不同元素的组合数是!()!m n n C n m =-；三、圆排列定义 从n 元集中任取r 个不同元素，仅按元素之间的相对位置而不分首尾排成一个圆圈，这种排列称为n 个不同元素的r-圆排列，其排列数记为rn H ．由定义，不难求得：r n H 与组合数r n C 和排列数r n A 的关系为：rA r C H rnr nr n =-=)!1(．事实上设已将某r 个不同元素在圆周上排好，并从某个元素开始将它们依次记为r A A A ,,,21 ，现在保持这个顺序不变，让1A 去任意选择圆周上的r 个位置之一，有r 种不同的选择，这r 种选择所对应的排列形式不同实则相同由于r 个元素的全排列数为!r ，故r 个元素的圆排列数为)!1(-r ，故n 个元素的圆排列数为)!1(-r C rn ．四、重复排列定义 从n 元集中允许重复地任取r 个元素排成一列，称为n 个不同元素的r-可重排列．利用乘法原理易证明，n 个不同元素的r-可重排列数为r n ，这类问题一般可直接用乘法原理求解． 五、不全相异元素的全排列定义 设n 个元素可分为k 组，每一组中的元素是相同的，不同组间的元素是不同的，其中第i 组的元素个数为i n ),...,2,1(k i =，n n n n k =+++...21，则这n 个元素的全排列称为不全相异元素的全排列．n 个元素的不全相异元素的全排列个数为!!...!!21k n n n n ，证明如下：先把每组中的元素看作是不相同的，则n 个不同元素的全排列数为!n ，然后分别将每个组的元素还其本来面目——每个组的元素是相同的，则在这!n 个全排列中，每个排列都重复出现了12!!...!k n n n 次，所以不全相异元素的全排列数为!!...!!21k n n n n ．六、多组组合定义 将n 个不同的元素分成k 组的组合称为n 个不同元素的k -组合．对于一个n 个不同元素的k -组合，若第i 组有i n 个元素，（k i ,...,2,1=），则不难证明不同的分组方法数为!!...!!21,...,,21k n n n n n n n n C k=事实上，我们把分组的过程安排成相继的k 个步骤：第一步，从n 个不同元素中选1n 个，有1n n C 种方法；第二步，从1n n -个元素中选2n 个有21nn n C -种方法，……，第k 步，从121...-----k n n n n 个元素选k n 个元素，有k k nn n n n C )...(121-+++-种方法，再由乘法原理得证．七、重复组合定义 从n 个不同的元素中任取r 个允许重复出现的组合称为n 个不同元素的r —可重组合．不难证明，n 个不同元素的r —可重组合的个数为rr n C 1-+．事实上，设（r a a a ,...,,21）是取自{1,2,…,n}中的任一r-可重复组合，并设r a a a ≤≤≤...21，令)1(1r i i a b i i ≤≤-+=，从而11a b =，122+=a b ，233+=a b ，…，1-+=r a b r r ，显然下面两组数是一对一的：r a a a ≤≤≤...21，11...211321-+≤-+<<+<+<≤r n r a a a a r设=A {}r i r a a a n a a a a ≤≤≤∈...},,...,2,1{|),...,,(2121，=B{}r i r b b b r n b b b b <<<-+∈...},1,...,2,1{|),...,,(2121，则由A 、B 之间存在一一对应，可知r r n C B A 1||||-+==，得证．在上述证明中，设r-可重复组合r a a a ,...,,21中含有1x 个1，2x 个2，…，n x 个n ，则r x x x n =+++...21，且显然有（r a a a ,...,,21）与（n x x x ,...,,21）一一对应，因此我们立即可得：定理1 不定方程r x x x n =+++...21的非负整数解的个数为rr n C 1-+．定理2 不定方程r x x x n =+++...21的正整数解的个数为11--n r C ．证明：令1-=i i x y ，其中1≥i x ，（n x x x ,...,,21）是已知方程的正整数解，则n r y y y n -=+++...21 （*），由定理1知，方程（*）有1111)(-------+==n r nr r nr r n n C C C 个正整数解．【赛题解析】例1．在由n 2个小方格组成的正方形中，有多少个由整数个小方格组成的大小或位置不同的正方形？解：由整数个小方格组成的大小位置不同的正方形可分成n 类，第k 类为k ×k 的正方形，共有2)1(+-k n 个(k=1,2,…,n)，于是由加法原理得所求正方形的总个数为)12)(1(61)1(12++=+-=∑=n n n k n N nk ． 说明：此题将问题进行分类，直接用加法及乘法原理进行求解，两个原理是解决排列组合问题最基本的工具． 例2．设整数a,b,c 为三角形三边，a+b=n ∈N,1≤c ≤n-1，求这样的整边三角形的个数 解：不妨设b ≥a ，有1≤a ≤[2n]，这样的整边三角形可分为两类． 第一类：c 为最大边，令i a =，则i n b -=，n-i ≤c ≤n-1，这样的三角形有i i n n =+---1)()1(个；第二类：c 不为最大边，则b a c c b >+>,，故i n c i n a b -<<-=-2，故112--≤≤+-i n c i n ，这样的三角形有11)12()1(-=++----i i n i n ．由加法原理，使a+b=n 的整边三角形的个数为∑=-+=]2[1)1()(ni i i n f 2]2[⎪⎭⎫⎝⎛=n ．例3．有多少个能被3整除而又含有数字6的五位数？解：易知，在由10000～99999这90000个五位数中，共有30000个可被3整除，下面先求其中不含数字6的有多少个．这件事情可分步来完成：在最高位，不能为0和6，因此有8种可能的情况，在千、百、十位上，不能为6，各有9种可能的情况，在个位上，不能为6，且应使整个五位数能被3整除，因此所出现的数应与前4位数字之和被3除的余数有关：当该余数为2时，个位上可为1，4，7中的一个；当该余数为1时，个位上可为2，5，8中的一个；当该余数为0时，个位上可为0，3，9中的一个，总之，不论前4位数如何，个位数字都有3种可能情况．所以这类五位数的个数为8×9×9×9×3=17496，因此，含数字6而又可被3整除的五位数的个数为30000-17496=12504种可能．例4．从1，2，3，4，……，49中取出六个不同的数字，其中至少有两个是相邻的取法种数是多少？ 解：设126,,,a a a 是取自1，2，3，4，……，49中的六个不同的数，不妨设126a a a <<<，显然12345612345a a a a a a ≤-≤-≤-≤-≤-，且123456,1,2,3,4,5a a a a a a -----互不相同的充要条件是：126,,,a a a 中不含相邻的数．作六元数组126(,,,)a a a 对应于123456(,1,2,3,4,5)a a a a a a -----，则在取自1至49之间的六个不同且没有相邻的数构成的六元组集合与所有取自1至44之间的六个不同的数构成的六元组集合之间建立了一一对应，因此这两个集合中六元组的个数都为644C ，而1至49之间的六个不同的数构成的六元组的个数为649C ，于是，其中有相邻数的六元组的个数为664944C C -．说明：本题通过对应的方法将数相邻的问题转化为元素互异的问题，从而得到求解，对应的方法是解决排列组合问题的一种常用方法．例5．如图ABCDEF为六边形，一只青蛙开始在顶点A处，它每次可随意跳到相邻两个顶点之一．（1）若在5次内跳到D点，则停止跳动；若5次内不能跳到D点，跳完5次也停止跳动．问这只青蛙从开始到停止，可能出现的不同跳法有几种？（2）若青蛙共跳12次，最终跳回到A点的不同跳法有几种？解：（1）由条件，青蛙的跳法只可能出现两种情况：①跳3次到达D点，有2种跳法．②跳5次停止（前3次不到D点），注意到前3次的32种跳法中，有2种到达D点，故前3次有3226-=种跳法，而后2次有22种跳法，因此有26224⨯=种跳法．由①、②可知，共有2+24=26种不同的跳法．（2）设青蛙每逆时针跳一步记为+1，每顺时针跳一步记为-1，共跳12次，将所有这些数相加，若其和为6的倍数，则青蛙跳回A处，若其和不为6的倍数，则青蛙不可能跳回原处，若其和为0，则必为6个+1和6个-1相加，共有612C种可能；若其和为6，则必为9个+1和3个-1相加，共312C种；若其和为-6，则必为3个+1和9个-1相加，共312C种；若其和为12，则有1种可能，若其和为-12，也有一种可能，因此满足要求的不同跳法总数为63121222C C++种．例6．将一个四棱锥S-ABCD的每个顶点染上一种颜条棱的两端点异色，如果只有5种颜色可供使用，那么不同的染色方法的总数是多少？解法一：由题设，四棱锥S-ABCD的顶点S、A、B所染的颜色互不相同，它们共35A种染色方法．当S、A、B已染好时，不妨设其颜色分别为1、2、3，若C染颜色2，则D可染颜色3、4、5之一，有3种染法；若C染颜色4，则D 可染颜色3或5，有2种染法；若C染颜色5，则D可染颜色3或4，也有2种染法，由此可见，当S、A、B已染好时，C与D还有7种染法，从而总的染色方法数为7×35A=420种．解法二：满足题设条件的染色至少要用三种颜色．（1）若恰用三种颜色，可先从5种颜色中任选一种染顶点S，再从余下的四种颜色中任选两种染A、B、C、D四点，此时只能A与C、B与D分别同色，故有60122415=⋅CCC种方法；（2）若恰用四种颜色染色，可以先从5种颜色中任选一种染顶点S，再从余下的四种颜色中任选两种染A与B，由于A与B颜色可以交换，故有24A种染法，再从余下的两种颜色中任选一种染D或C，而D与C中另一个只需染与其相对顶点同色即可，故有24012122415=CCAC种方法；（3）若恰用5种颜色染色，易知有12055=A种染法．综上所知，满足题意的总染色方法数为60+240+120=420种．类题：（2003年高考江苏第15题）某城市在中心广场建造一个花囿，花囿分为6个部分（如图），现要栽种4种不同颜色的花，每部分栽种一种且相邻部分不能栽种同样颜色的花，不同的栽种方法有______________种（以数字作答）．解法一：1、2、3两两相邻，颜色应互不相同，故有34A种不同种法；1、2、3种好后，用树图方法不难得到4、5、6共有5种种法，由乘法原理得共有34A×5=120种种法．解法二：先种1，有4种颜色可选取，2、3、4、5、6形成一个圆环，要求用3种颜色涂上，且相邻的颜色不同即可转化为如下问题：将一个圆分成5个扇形，将三种颜色涂入其中，相邻的扇形涂不同的颜色．先涂1S，有三种涂法，再涂2S，有两种涂法，再涂3、4各有两种涂法，再涂5，如果只要求它与4颜色不同，则仍有两种涂法，这样共有3×2×2×2×2=48种涂法，但这48种涂法中有两类：一类5与1颜色不同，这种涂法符合题意，其数设为5a一类5与1颜色相同，这种涂法不合题意，如果把5与1合并看成一个扇形，这类涂法就相当于把圆分成4个扇形，按题设要求，其数为4a，即5a+4a=48，同理，34aa+=24，而6333==Aa，∴5a=30，故最后的结果为：30×4=120种．此问题可一般化为：把一个圆分成)2(≥nn个扇形，依次记为,,,,21nSSS 每个扇形都可用红、白、蓝三种不同颜色之任一种涂色，且三种颜色均至少用一次，要求相邻的扇形颜色互不相同，问有多少种涂色法？略解：同上可得： ,6,5,4,2311=⨯=+--n a a n n n ，63=a ．若没有条件“颜色均至少用一次”，结果为 ,6,5,4,2311=⨯=+--n a a n n n ，62=a ．更一般的情形是：把一个圆分成)2(≥n n 个扇形，依次记为,,,,21n S S S 每个扇形都可用r 种不同颜色之任一种涂色，要求相邻的扇形颜色互不相同，问有多少种涂色法？ 有11(1),4,5,6,n n n a a r r n --+=⨯-=，可得n n n r r a )1()1)(1(-+--=说明：当我们用集合划分的方法对问题进行分类计数时，有时不可能一次性获得成功，这就需要通过建立递推关系来求解，我们把这种计数方法称为递推方法．例7．设集合A={1,2,3,…,366}，如果A 的一个二元子集B={a ,b }满足17|a +b ，则称B 具有性质P ． （1） 求A 的具有性质P 的所有二元子集的个数；（2） 求A 的两两不相交且具有性质P 的所有二元子集的个数．解：（1）a +b ≡0(mod17)，即a ≡k (mod17)且b ≡17-k (mod17)，k =0,1,2,…,16， 将1,2,3,…,366按模17可分为17类[0],[1],…[16]；因366=17×21+9，故|[1]|=|[2]|=…=|[9]|=22，|[10]|=|[11]|=…=|[16]|=|[0]|=21， 欲17|a +b ，当且仅当a ,b ∈[0]或a ∈[k ]，b ∈[17-k ]，当a ,b ∈[0]时，具有性质P 的二元子集的个数为221C 个；当a ∈[k ]，b ∈[17-k ]，k =1,2,…,7时，具有性质P 的二元子集有1211227C C 个； 当a ∈[8]，b ∈[9]时，具有性质P 的二元子集有121121C C 个； 所以A 的具有性质P 的二元子集总个数为39287121121121122221=++C C C C C 个． 说明：如果把子集换成数对（a ,b ），则共有2×3928个． （2）为使二元子集两两不交，可作如下搭配： a ,b ∈[0]时，共有10个子集；a ∈[k ]，b ∈[17-k ]，k=1,2,…,7，有21个子集； 当a ∈[8]，b ∈[9]时，有22个子集．故A 的具有性质P 的两两不交的二元子集共有10+7×21=179个．例8．8个女孩和25个男孩围成一圈，任何两个女孩之间至少站两个男孩，问共有多少种不同的排列方法（只要把圈旋转一下就重合的排法认为是相同的）．解：以1个女孩和2个男孩为一组，且使女孩恰好站在两个男孩中间，余下的9个男孩和这8个组被看成是17个元素，显然这17个元素任意的圆排列数为1616A 种再次，分在8个组内的16个男孩在16个位置上的排列是1616A ，所以总的排列方法数为：16161616925A A C ．说明：此题为圆排列问题．例9．试求从集合{}n A ,...,2,1=到集合{}m B ,...,2,1=的映射的个数． 解：由映射的定义知，每一个到B 的映射对应着m 个不同元素的n -可重排列，故从A 到B 的映射的个数为nm ．例10．一段楼梯共有12级台阶，某人上楼时，有时一步迈一台阶，有时一步迈两台阶，问此人共有多少种上楼的方法？解：现将“一步迈两级台阶”这一动作记为a ，因为楼梯共有12级台阶，故动作a 至多只能做6次；再记“一步迈一级台阶”的动作为b ，则上楼的整个过程由k 个a 及12-2k 个b 组成，这里k 可取0，1，2，3，4，5，6，对于某个k ，其全排列数为：)!212(!]!212([k k k k --+)!212(!)!12(k k k --=，因此，上楼的方法共有：∑=--60)!212(!)!12(k k k k =233种． 解法2：以k =4为例，即4个两级，4个一级，相当于共8步，其中有四步为两级，即相当于从8步中选4步跨两级，其余跨一级，故结果应为48C ；一般地上楼的整个过程由k 个a 及12-2k 个b 组成，相当于共跨k +(12-2k )=12-k 步，其中有k 步为a ，故结果为kk C -12,这里k 可取0,1,2,3,4,5,6，故最终结果为∑=-612k k kC．解法3：设走n 次台阶的方法总数为n a ，对每种走法可划分为两类第一类：第一步走1级，有1-n a 种走法；第二类：第一步走2级，有2-n a 种走法，故21--+=n n n a a a ，且2,121==a a ，故易得23312=a ．因Fibonacci 数列}{n F 满足2,1321===F F F ，故1+=n n F a ，由上面的一些方法还可知：∑=--=]2[01n k kk n n CF ．若将所跨的每一级台阶，此人均用红、白两种颜色做上记号，则标有不同颜色的路线共有∑=---=⋅]2[02132ni i n i in n C种，其递推关系式为5,2,22121==-=--a a a a a n n n ．例11．把n 个不同的球，分别装入m 个盒子中，使其中1m 个盒子中每个都有1p 个球，2m 个盒子中每个都有2p 个球，…，k m 个盒子中每个都有k p 个球，这里，k k k m p m p m p n m m m m +++=+++=...,...221121，求下列情况下，各有多少种不同放法：（1）盒子均不相同；（2）装有相同数目的球的盒子相同．解：（1）这是一个将n 个不同元素分为m 组的多组组合，故不同的放法数有k m k m m p p p n f )!...()!()!(!2121=； （2）因为相同数目的球的盒子相同（不加区别），故所求放法数为!!...!21k m m m f．例12．电视台在n 天内共播出r 次商业广告，问若每天至少播p 次广告（r np ≤），就每天播出广告的次数而言，共有几种播出方法？ 解：设第i 天播出广告i x 次，由题设知：r x x x n =+++...21，),...,2,1(n i p x i =≥，令p x y i i -=，则0...21≥-=+++np r y y y n ，故问题转化为求上述不定方程的非负整数解的个数，从而知广告播放的方法数为npr n np r C --+-1)(．巩 固 练 习1．n 名同学(n ≥3)站成一圈，其中A 、B 两人不能相邻的站法有多少种？ 解：n 名同学站成一圈有(n-1)!种站法，其中使A 、B 相邻的站法有2×(n-2)!种，从而A 、B 不相邻的站法为(n -1)!-2×(n-2)!=(n-3)(n-2)!种站法．2．设集合A 、B 的并集为一个n 元集，A ≠B ．（1） 若（A ，B ）与（B ，A ）视为不同的对，则这样的A 、B 共有多少个？ （2） 若（A ，B ）与（B ，A ）视为相同的对，则这样的A 、B 共有多少个？解：（1）设集合A 中有k 个元素，则集合B 中必含有A 中没有的n-k 个元素，再加上A 的k 个元素中取0个、1个、…k 个，故共有kk n C 2个，故总数为∑=nk k knC2=n 3个，除去A 与B 相同（均为全集）的1个，共n 3-1个；（2）由题意，（A ，B ）与（B ，A ）一一对应，故结果为)13(21-n个． 3．在一个正六边形的六个区域栽种观赏植物，如图，要求同一块中种同一植物，相邻的两块种不同的植物，现有4种不同的植物可供选择，则有多少种不同的栽种方案．解：考虑A 、C 、E 种同一种植物，此时共有4×3×3×3=108种；考虑A 、C 、E 种两种植物，此时共有3×4×3×3×2×2=432种方法；考虑A 、C 、E 种三种植物，此时共有34C ×2×2×2=192种方法；故总计有108+432+192=732种方案．4．如图，矩形ABCD 的边在网格线上，并且AB 是AD 的k 倍（k 为正整数），考虑沿网格的边从A 到C 所有可能的最短路径．证明：在这些路径中，含AB 1的条数是含AD 1的条数的k 倍．横向的m-1节，纵向的n 节，因此共有1nm n C +-条，解：含AB 1的最短路径，除AB 1外，还应含同理，含AD 1的最短路径有1mm n C+-条，而11!(1)!!(1)!n m n mm n C m n m k C n m n+-+--===-，因此命题得证． 5．马路上有编号为1，2，3，…，2005的2005只路灯，为节约用电，现要求把其中的200只灯关掉，但不能同时关掉相邻的两只或三只，也不能关掉两端的路灯，求满足条件的关灯方法共有多少种？解：任意一种关灯的方法，都对应着一种满足题设条件的亮灯与暗灯的排列，于是总是转化为1805只亮灯中插入200只暗灯，且任何两只暗灯不相邻，而且不在两端，也就是在1805只亮灯所形成的1804个间隙中选200个插入暗灯，其方法有2001804C 种．6．把2005个不加区别的小球分别放在10个不同的盒子里，使得第i 个盒子中至少有i 个球)10,...,2,1(=i ，问不同放法的总数是多少？ 解：先在第i 个盒子里放入i 个球，这时共放了1+2+…+10=55个球，还余下2005-55=1950个球，故问题转化为把1950个球任意放入10个盒子（允许有的盒子不放球），相当于一个不定方程的非负整数解的个数问题，共有195019509101950119591959C C C +-==种．7．n 个人)3(≥n 站成一圈，其中某指定的两人A 、B 肯定不相邻的站法有多少种？ 答案：)!2(2)!1(---n n ．8．甲、乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由一号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，……，直到一方队员全部淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数是多少？解：不妨先设甲方胜出，则问题等价于求方程7...721=+++x x x 的非负整数解的个数，有6137177C C =-+种，同理，乙方胜的比赛过程也有6137177C C =-+种，故可能出现的比赛过程有6132C 种．9．有男生m n +人，女生m 人（1,≥n m ），（1）这m n 2+个人排成一列，女生不相邻，首尾都是男生，有多少种排法？ （2））这m n 2+个人围成一圈，女生不相邻，有多少种排法？解：（1）m m n A m n 1)!(-++；（2）先作男生圆排列，然后插入，共mm n A m n +-+)!1(．10．方程3...210321=++++x x x x 的非负整数解共有多少个？ 解：由题意，1,01=x ，故分情况讨论如下：若01=x ，则3...1032=+++x x x ，非负整数解的个数为：1653139=-+C ； 若11=x ，则1...1032=+++x x x ，非负整数解的个数为：91119=-+C ．综上，非负整数解的个数为：165+9=174个．11．一个盒子里有7个分别标有号码1，2，…，7的球，每次取出一个，记下它的号码后再放回盒子，共取（放）4次，求4次中最大标号恰是5的取法数？解：最大标号为5，相当于从1，2，…，5中取，共取（放）4次，共有45种取法；从中剔除四次中最大标号均不是5的种数，结果为4544-=369．12．已知集合{}2,,,|12≥∈∈==-n N n C z z z z A n ，在复平面上，以A 中的复数的对应点为顶点可构成多少个直角三角形？ 解：易求得{}122,,,1,0-=n A εεε ，其中nieπε=（n ≥2）设各复数在复平面上对应点依次为O 、A 0、A 1、A 2、…、A 2n-1，则A 0A 1A 2…A 2n-1为正2n 边形，易知在j i A OA ∆中以j i A A ,为顶点的内角均为锐角，所以，由O 、A 0、A 1、A 2、…、A 2n-1为顶点的直角三角形可分为两类： 第一类：以O 为直角顶点的直角三角形，不失一般性，可设︒=∠900K OA A ，则nk ππ=2，所以)(2N k k n ∈=，这说明这类直角三角形存在当且仅当n 为偶数时，这时，这样的直角三角形有2n 个；第二类：不以O 为直角顶点的直角三角形这样的直角三角形的顶点均匀分布在单位圆周上，即由A 0、A 1、A 2、…、A 2n-1构成，这些点可确定n 条直径，于是可构成)22(-n n 个直角三角形综上所述，由加法原理，所求直角三角形的总个数为⎩⎨⎧-=+-=为奇数为偶数n n n n n n n n n f ),1(2,22)22()(2．。