7、排列组合问题之全错位排列问题(一个通项公式和两个递推关系)

全错位排列以前接触过这样的题⽬，但是现在稍微系统点⾸先看⼀下百度百科对全错位排列的解释：基本简介全错位排列：即被著名数学家(Leonhard Euler，1707－1783)称为组合数论的⼀个妙题的“装错信封问题”。

“装错信封问题”是由当时最有名的数学家(Johann Bernoulli，1667－1748)的⼉⼦(DanidBernoulli，1700－1782)提出来的，⼤意如下：⼀个⼈写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？公式证明n个相异的元素排成⼀排a1，a2，...，an。

则ai(i=1，2，...，n)不在第i位的排列数为：公式证明：设1，2，...，n的全排列t1，t2，...，tn的集合为I,⽽使ti=i的全排列的集合记为Ai(1<=i<=n)，则Dn=|I|-|A1∪A2∪...∪An|.所以Dn=n!-|A1∪A2∪...∪An|.注意到|Ai|=(n-1)!，|Ai∩Aj|=(n-2)!，...，|A1∩A2∩...∩An|=0!=1。

由：Dn=n!-|A1∪A2∪...∪An|=n!-C(n,1)(n-1)!+C(n,2)(n-2)!-C(n,3)(n-3)!+...+(-1)^nC(n,n)*0!=n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)（可以举例试试，很好懂）应⽤：（1）简单排列1个元素没有全错位排列，2个元素的全错位排列有1种，3个元素的全错位排列有2种，4个元素的全错位排列有9种，5个元素的全错位排列有44种。

递推公式数学家欧拉按⼀般情况给出了⼀个递推公式：⽤A、B、C……表⽰写着n位友⼈名字的信封，a、b、c……表⽰n份相应的写好的信纸。

把错装的总数为记作f(n)。

假设把a错装进B⾥了，包含着这个错误的⼀切错装法分两类：（1）b装⼊A⾥，这时每种错装的其余部分都与A、B、a、b⽆关，应有f(n-2)种错装法。

全错位排列与多个特殊元素特殊位置（C ．T ）T 2=1，T 3=2，T n = (n -1) ( T n -1+T n -2) ，（n ≥3）( T n 为全错位排列数)错位排列问题题一 4名同学各写一张贺卡，先集中起来，然后每人从中拿出一张别人写的贺卡，则四张贺卡的不同分配方式共有 种.题二 将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同，则共有 种不同的放法.这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题（所有元素均为特殊元素）.题三 五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有 种.题三可以分类解决：第一类，所有同学都不坐自己原来的位置；第二类，恰有一位同学坐自己原来的位置； 第三类，恰有两位同学坐自己原来的位置.对于第一类，就是上面讲的全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题， 我们称这种排列问题为部分错位排列问题. (多个特殊元素，多个特殊位置) 部分错位排列(多个特殊元素，多个特殊位置)例1：5个人站成一排，其中甲不站第一位，共有多少种不同的站法。

解一：（特殊元素特殊位置优先处理）第一步：安排甲这特殊元素，有14C 种；第二步：安排其他人，其余的四个人（元素），不受限制，故有44A 种站法。

由分步乘法原理得14C 44A =96种站法。

解二：（排除法）先考虑5个人的全排列，有55A 种不同的排法，然后除去甲排第一（有44A 种）这样得到共有：55A －44A ＝96种。

例2：5个人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法。

解一：（特殊元素特殊位置优先处理） 分析：有两个特殊元素，分类讨论，减少限制条件。

第一类：甲站在第二位，则其他的四人（含乙），不受限制，有44A 种站法。

排列组合问题经典题型与通用方法1.相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组，当作一个大元素参与排列.例1.,,,,A B C D E五人并排站成一排，如果,A B必须相邻且B在A的右边，则不同的排法有〔〕A、60种B、48种C、36种D、24种2.相离问题插空排:元素相离〔即不相邻〕问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素的空位和两端.例2.七人并排站成一行，如果甲乙两个必须不相邻，那么不同的排法种数是〔〕A、1440种B、3600种C、4820种D、4800种3.定序问题缩倍法:在排列问题中限制某几个元素必须保持一定的顺序，可用缩小倍数的方法.例3.A,B,C,D,E五人并排站成一排，如果B必须站在A的右边〔,A B可以不相邻〕那么不同的排法有〔〕A、24种 B、60种 C、90种 D、120种4.标号排位问题分步法:把元素排到指定位置上，可先把某个元素按规定排入，第二步再排另一个元素，如此继续下去，依次即可完成.例4.将数字1，2，3，4填入标号为1，2，3，4的四个方格里，每格填一个数，则每个方格的标号与所填数字均不相同的填法有〔〕A、6种B、9种C、11种D、23种5.有序分配问题逐分法:有序分配问题指把元素分成假设干组，可用逐步下量分组法.例5.〔1〕有甲乙丙三项任务，甲需2人承担，乙丙各需一人承担，从10人中选出4人承担这三项任务，不同的选法种数是〔〕A、1260种B、2025种C、2520种D、5040种〔2〕12名同学分别到三个不同的路口进行流量的调查，假设每个路口4人，则不同的分配方案有〔〕A、4441284C C C种 B、44412843C C C种 C、4431283C C A种 D、444128433C C CA种6.全员分配问题分组法:例6.〔1〕4名优秀学生全部保送到3所学校去，每所学校至少去一名，则不同的保送方案有多少种？〔2〕5本不同的书，全部分给4个学生，每个学生至少一本，不同的分法种数为〔〕A、480种 B、240种 C、120种 D、96种7.名额分配问题隔板法:例7：10个三好学生名额分到7个班级，每个班级至少一个名额，有多少种不同分配方案？8.限制条件的分配问题分类法:例8.某高校从某系的10名优秀毕业生中选4人分别到西部四城市参加中国西部经济开发建设，其中甲同学不到银川，乙不到西宁，共有多少种不同派遣方案？9.多元问题分类法：元素多，取出的情况也多种，可按结果要求分成不相容的几类情况分别计数再相加。

行测技巧：排列组合问题之错位重排公务员行测考试主要是考量大家的数学推理能力和逻辑分析能力，下面由我为你精心准备了“行测技巧：排列组合问题之错位重排”，持续关注本站将可以持续获取更多的考试资讯！行测技巧：排列组合问题之错位重排公务员考试中虽然数量关系的题目比较难，但是有些特殊的题型是可以直接套用固定公式的。

这些题型解题的关键就在于区分题型以及记住相应结论。

错位重排就是这种题型。

接下来就给大家介绍一下什么是错位重排，以及这类题型该如何作答。

错位重排是一个排列组合问题。

是伯努利和欧拉在错装信封时发现的，因此又称伯努利-欧拉装错信封问题。

【题型表述】编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法?【解析】这个问题如果数量比较少时还比较简单，比如说n=1时，0种;n=2时，1种。

但是n一旦比较大时就比较麻烦了。

其实对这类问题有个固定的递推公式，如果记n封信的错位重排数为Dn，则D1=0，D2=1，Dn=(n-1)(Dn-2+Dn-1)(n>2)。

其实在考试中n一般不会超过5，也就是说我们只需记住Dn的前几项：D1=0，D2=1，D3=2，D4=9，D5=44。

我们只需要记住结论，进行计算就可以。

我们来看一下考题是如何考察的。

【例1】四位厨师聚餐时各做了一道拿手菜。

现在要求每人去品尝一道菜，但不能尝自己做的那道菜。

问共有几种不同的尝法?A.6种B.9种C.12种D.15种【解析】答案：B。

记住结论D4=9。

直接锁定答案。

【例2】办公室工作人员一共有8个人，某次会议，已知全部到场。

问：恰好有3个人坐错位置的情况一共有多少种?A.78B.96C.112D.146【解析】答案：C。

8个人有3个坐错了，我们首先得确定哪3个坐错了。

即C(8，3)=56。

3个人坐错相当于3个人都没有坐在他原来的位置上，也就说相当于三个元素的错位重排，一共有2种。

再用分步相乘得到一共有56X2=112种。

全错位排列先看下面例子：例1 5个人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法。

这个问题在高中很多参考书上都有，有几种解法，其中一解法是用排除法：先考虑5个有的全排列，有A55种不同的排法，然后除去甲排第一（有A44种）与乙排第二（也有A44种），但两种又有重复部分，因此多减，必须加上多减部分，这样得到共有：A55－2A44＋A33＝78种。

现在考虑：例2 5个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法。

仿上分析可得：A55－3A44＋3A33－A22＝64种这与全错位排列很相似。

全错位排列——即n 个元素全部都不在相应位置的排列。

看下面的问题例3 5个人站成一排，其中A 不站第一位，B 不站第二位，C 不站第三位，D 不站第四位，E 不站第五位，共有多少种不同的站法。

解析：上面例1，例2实际上可以看成n 个不同元素中有m （m≤n ）不排在相应位置。

公式一：n 个不同元素排成一排，有m 个元素（m≤n ）不排在相应位置的排列种数共有：从而这个问题可能用上面的公式得出：()A C A C A C A m n m n m m m n n m n n m nn ------∙∙-++∙+∙-1 (222111)这个公式在n ＝m 时亦成立A55－C(5,1)?A44＋C(5,2)?A33－C(5,3)?A22＋C(5,4)?A11－C(5,5)?A00＝44种（注意A00＝0!＝1）再看1993年高考题：同室四人各写一张贺年卡，先集中起来。

然后每人从中拿一张别人送出的贺年卡。

则四张贺年卡不同的分配方式有(A)6种 (B)9种 (C)11种 (D)23种解析：由上面公式得：A44－C(4,1)?A33＋C(4,2)?A22－C(4,3)?A11＋C(4,4)?A00＝9种，∴选择B 答案因此可得到全错位排列的公式：n 个不同元素排成一排，第一个元素不在第一位，第二个元素不在第二位，……，第n 个元素不在第n 位的排列数为：()A C A C A C A n n n n n n n n n n n n n nn ------∙∙-++∙+∙-1 (222111)这实际上是公式一的特殊情况。

全错位排列n个相异的元素排成一排，，...，。

则(i=1，2，...，n)不在第i位的排列数N为公式证明：设Ai表示元素ai在第i个位置。

不难得出N=n!-(A1∪A2∪A3……∪An)根据容斥原理（文章最后有简单说明）展开得=证毕.全错位排列的递推公式（真的有递推公式，当时只是感觉应该会出现递推的。

不过这个递推公式貌似推导不出结果的）第一个位置有n-1种可能。

设a2在第一个位置，那么如果a1在第二个位置，就是剩下的n-2个元素的全错位排列记为N（n-2）。

所以N=（n-1）*（N（n-2））+X那么a1不在第二个位置呢？此时我们把a1看成a2，既然a1不在第二个位置，我们有理由相信这相当于a2（由a1充当），a3，a4，……an，的全排列数。

即N（n-1）也就是X=（n-1）*N（n-1）所以N(n)=(n-1) （N(n-1)+N(n-2)）当然这并不难的出，关键是要从这个递推关系中推出通项公式。

比较复杂了。

（瑞士数学家欧拉（Leonhard Euler，1707－1783)按一般情况给出了这个递推公式）此问题也被称为Install the wrong envelope problem（装错信封问题）N(n)=(n-1) （N(n-1)+N(n-2)）公式可重新写成N(n)-nNf(n-1)=-[N(n-1)-N(n-1)f(n-2)] (n>2)于是可以得到N(n)-nN(n-1)=-[N(n-1)-(n-1)N(n-2)]=((-1)^2)[N(n-2)-(n-2)N(n-3)]=((-1)^3)[N(n-3)-(n-3)N(n-4)]=……=[(-1)^(n-1)][N(3)-3N(2)]=[(-1)^(n-2)][N(2)-2N()]通过列举可知N(1)=0 N（2）=1 N(3)=2 N(4)=9最终可以得到一个更简单的递推式N(n)=nN(n-1)+(-1)^(n-2)等价于N(n)=n*N(n-1)+(-1)^(n) n=2,3,4……（前几项验证成立）这个递推公式按现在的知识还不够推导出结果。

全错位排列 先看下面例子：例15个人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法。

这个问题在高中很多参考书上都有，有几种解法，其中一解法是用排除法：先考虑5个有的全排列，有 A55种不同的排法，然后除去甲排第一(有 A44种)与乙排第 二(也有A44种)，但两种又有重复部分，因此多减，必须加上多减部分，这样得到共有：A55 — 2A44 + A33 = 78 种。

现在考虑：例2 5个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同 的站法。

仿上分析可得： A55 — 3A44 + 3A33 — A22 = 64种这与全错位排列很相似。

全错位排列一一即n 个元素全部都不在相应位置的排列。

看下面的问题例3 5个人站成一排，其中 A 不站第一位，B 不站第二位，C 不站第三位，D 不站第四位, E 不站第五位，共有多少种不同的站法。

解析：上面例1,例2实际上可以看成n 个不同元素中有 m ( men)不排在相应位置。

公式一：n 个不同元素排成一排，有m 个元素(m en)不排在相应位置的排列种数共有：从 而这个问题可能用上面的公式得出：n 1n 2 n _2 A n -C m 入」C m 入之这个公式在n = m 时亦成立A55 — C(5,1)?A44 + C(5,2)?A33 — C(5,3)?A22 + C(5,4)?A11 — C(5,5)?A00 = 44 种(注意 A00 = 0! = 1)再看1993年高考题：同室四人各写一张贺年卡， 先集中起来。

然后每人从中拿一张别人送出的贺年卡。

则四张贺 年卡不同的分配方式有(A)6 种(B)9 种 (C)11 种 (D)23 种解析：由上面公式得：A44 — C(4,1)?A33 + C(4,2)?A22 — C(4,3)?A11 + C(4,4)?A00 = 9 种，.••选择 B 答案因此可得到全错位排列的公式：n 个不同元素排成一排，第一个元素不在第一位，第二个元素不在第二位，……，第n 个元 素不在第n 位的排列数为： n 1 n 4 2 A n -C^A n. C n *A 这个公式很有用，只要有特殊元素不站特殊位置的问题, 可以用这个公式很快得到解决，希望这个公式对大家有所帮助将n 个编号为1、2、3...n 的小球投入到编号为1、2、3...n 的n 个盒子中，其中第i 号球不 投到第i 号盒子中(i = 1,2,3,...n )的投法数为全错排列问题.这个问题是由瑞士的数学家欧拉解决的，公式为：其中n >2on•C^A 这实际上是公式一的特殊情况。

排列组合错位重排 Document serial number【KK89K-LLS98YT-SS8CB-SSUT-SST108】排列组合-错位重排题型概述：错位重排作为排列组合的一种模型，原理很复杂，但是应用上面很简答。

那我们就通过几个例题来学习下这种题型。

题型要点：错位题型最直接的就是记住公式：一个元素错位重排的时候情况为0（因为只有一个，不可能排错），两个元素错位重排情况为1，三个为2，四个为9，五个为44，…………。

从0,1,2,9,44可以看出后面的数为前面两数和的倍数，那我们后面的情况也就不难推导出来。

Dn =（n-1）（Dn-2+Dn-1），（D1=0，D 2=1，D3=2）。

如果从排列组合的角度展开，我们分别看下：三个错排：三个全排列−三个序排−一个序排=A33−1−A31=2四个错排：四个全排列−四个序排−两个序排−一个序排=四个全排列−四个序排−两个错排−三个错排=A44−1−A42×1−A41×2=9五个错排：五个全排列−五个序排−三个序排−两个序排−一个序排=五个全排列−五个序排−两个错排−三个错排−四个错排=A55−1−A52×1−A52×2−A54×9=44………………………………例题：1.四位厨师聚餐时各做了一道拿手菜，现在要求每个人去品尝一道菜，但不能尝自己做的那道菜，问共有几种不同的尝法？（11年浙江）A.6种B.9种C.12种D.15种2.五个瓶子都贴有标签，其中恰好贴错了三个，则贴错的可能情况有多少种？（07年北京）A.60B.46C.40D.203.要把A、B、C、D四包不同的商品放到货架上，但是，A不能放在第一层，B不能放在第二层，C不能放在第三层，D不能放在第四层，那么，不同的放法共有（）种。

（09年云南）A.6B.7C.8D.9。