全装错信问题即全错位排列问题及拓展

全装错信问题即全错位排列问题及拓展

——龙城老欧全装错信问题又称全错位排列问题，最早由瑞士数学家伯努利提出，最后由伯努利与他的学生欧拉讨论解决，这个问题就是——

我们将编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信都和信封的编号不同，即1不能装进1，2不能装进2，3不能装进3……问有多少种装法？

看到这个问题时，我们的第一反应就是退到简单处入手研究，如果只有一封信，2封信，3封信，4封信，……，然后从中再思考，之间是否有共性，是否有关联，共性用归纳，关联构成递推，或者其他。

〖解法〗

容易知道：a[1]=0,a[2]=1，a[3]=2，a[4]=6;

依我们设a[i]为i封信的全错位排列数据递归推理那么有

a[i]=(a[i-1]+a[i-2])×(i-1)， (i>=3)。

为什么？为什么？为什么？大多数人看不明白。

不急，尽量先自己思考，不行的话，听我来解释：

思考1：对于插入第i个元素，只可能有两种情况：

第一种情况:插入第i个元素时，前i-1个已经错位排好，则选择其中任意一个与第i个互换一定满足要求,选择方法共i-1种，前i-1位错排f[i-1]种，记f[i-1]*(i-1),如下图：

第二种情况:插入第i个元素时，前i-1个中恰有一个元素恰好在自己的位置上，即恰好只有一个元素不满足错位排列，其他i-2个错位排好，则将i与j交换，j在i-2位中的插入共i-1种，前i-2位错排a[i-2]种，记f[i-2]*(i-1)，如下图：

以上两种情况求和可得: a[i]=(a[i-1]+a[i-2])×(i-1) (i>=3)

我们还可以这样思考：

思考2：有(i-1)个人已经都坐在在自己的板凳上了，现在第i个人张三带着自己的板凳来了，下面我们来对这i个人进行全错位排排坐，

方法1：前面(i-1)个人中的某一个带着板凳出来与第i个人张三互换板凳坐（有（i-1）种方法），其它(i-2)个人进行全错位排列（有a[i-2]种方法），这样就整体上都是全错位；

方法2：第i 个人张三走进去与将(i-1)个人中的某一个人换出来（i-1种方法），换出来的人（不妨称是李四）坐张三的板凳，换出来的李四的板凳看作张三的新板凳，这样又面临了(i-1)个元素进行全错位排列问题（a[i-2]种方法），这样就整体上也都是全错位了。 两种方法合起来求和可得i 个元素进行全错位排列数:

a[i]=(a[i-1]+a[i-2])×(i-1) (i>=3) ， a[1]=0,a[2]=1， 这样就可以源源不断地求任意i 个元素的全排列数了。

那么能不能建立a[i]关于i 的函数呢？这有点难，但也是可行的！ 通项公式研究：

这样我们就得到通项公式了！

这个太难了！换个“平易近人”的形式给你：

n （n 至少比1大）个元素全部错位的排列数1111()![(1)]2!3!4!!n f n n n =?-+-+-

〖拓展〗 进一步研究一个新问题：

n 封信装入n 个信封，其中恰有m （m 小于n ，比1大）封信装错的情况数为f(n,m) 这样就得到一个部分错位排列问题公式：

1111(,)()![(1)]2!3!4!!m m n n n f n m C f m C m m ==-+-+-

这个很容易理解，先把信全部放对，再分两步思考，第一步，选出m 封信，第二步将这m 封信信全部装错，乘法原理问题得解。

学会了吗？尝试练习一下吧！

练习一

1、将8封信装入8个信封，信全部装错的情况有多少种？

2、编号为1-7的7位同学去抢编号为1-7的7张椅子坐，每个人坐的椅子与自己的编号都不相同的情况有多少种？

3、9对夫妻参加舞会，在跳交谊舞时（男女搭配，全部参加）跳舞双方都不是夫妻档的情况有多少种？

练习二

1、将8封信随机装入8个写好的信封，恰有2封信装对的情况有多少种？

2、编号为1-7的7为同学去抢编号为1-7的7张椅子坐，恰有3个人的编号与椅子的编号相同的情况有多少种？

3、9对夫妻参加舞会，在跳交谊舞时（男女搭配，全部参加），在场恰好有3对夫妻搭档跳舞的情况有多少种？

国家公务员：排列组合之错位排序

国家公务员：排列组合之错位排序 排列组合的数量题目当中，有一些技巧我们常常会用到，今天我们就一起来看一下排列组合问题中常用的方法——错位排序。 我们来讨论一个问题：这是一个很经典的数学问题：有一个人写了n封信件，对应n个信封，然而粗心的秘书却把所有信件都装错了信封，那么一共有多少种装错的装法？ 这个问题可抽象为以下一个数学问题：已知一个长度为n的有序序列｛a1,a2,a3,…,an｝，打乱其顺序，使得每一个元素都不在原位置上，则一共可以产生多少种新的排列？首先考虑几种简单的情况： 原序列长度为1 序列中只有一个元素，位置也只有一个，这个元素不可能放在别的位置上，因此原序列长度为1时该为题的解是0。 原序列长度为2 设原序列为{a,b}，则全错位排列只需将两个元素对调位置{b,a}，同时也只有这一种可能，因此原序列长度为2时该问题的解是1。 原序列长度为3 设原序列为{a,b,c}，则其全错位排列有：{b,c,a},{c,a,b}，解是2。 原序列长度为4 设原序列为{a,b,c,d}，则其全错位排列有：{d,c,a,b},{b,d,a,c},{b,c,d,a},{d,a,b,c},{c,d,b,a},{c,a,d,b},{d,c,b,a},{c,d,a,b},{b,a,d,c}，解是9。 在往下数，次数会更多，那我们就可以用不完全归纳得出规律：f(n)=(n-1)f(n-2)+(n-1)*f(n-1)=(n-1)[f(n-2)+f(n-1)] 。 很明显，规律不太好记。但是我们不用记，因为在公务员考试当中，题目一般情况下比较简单，我们只需要记住D1=0；D2=1；D3=2；D4=9；D5=44。即可下面我们一起来看一道例题： 【例】（2015-山东-59）某单位从下属的5个科室各抽调了一名工作人员，交流到其他科室，如每个科室只能接收一个人的话，有多少种不同的人员安排方式？（）

全错位排列

全错位排列与多个特殊元素特殊位置 （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 种站法。 第二类：第一步安排特殊元素甲，甲不站在第二位，则甲也不能站在第一位，故甲的站法有 13C 种；第二步安排乙，乙不站第二位，也不能选择甲以经站的一个位置，故乙的站法有13C 种； 第三步安排其他人，其余的三个人（元素），不受限制，故有33A 种站法。由分步乘法原理得 13C 13C 33A 种站法。 由分类加法原理得44A +13C 13C 33A =78种。

错位重排专题

错位重排问题专项 错位重排 1-6个元素的错位重排数分别为0，1，2，9，44，265递推公式：Dm=（m-1）*[D（m-1）+D（m-2）]； 错位重排模型：把编号为1-m的小球分别放入编号为1-n的箱子错位重排（即1号球不在1号箱子、2号球不在2号箱子…m号球不在m号箱子），且每个箱子一个球，有多少种不同情况？ 楚香凝证明：假设总情况数为D（m）种，如果让1号球先选，有（m-1）种选择；假设1号球选的2号箱子，接下来让2号球选箱子，进行分类讨论： ①如果2号球选的1号箱子，相当于剩下的（m-2）个球进行错位重排，有D（m-2）种； ②如果2号球选的不是1号箱子，则题目可转化为把编号为2→m的小球分别放入编号为 1、3→m的箱子错位重排（即2号球不在1号箱子、3号球不在3号箱子…m号球不在m号箱子），相当于m-1个球错位重排，有D（m-1）种； 所以可得D（m）=（m-1）*[D（m-1）+D（m-2）]，得证； 例1：相邻的4个车位中停放了4辆不同的车，现将所有车开出后再重新停入这4个车位，要求所有车都不得停在原来的车位中，则一共有多少种不同的停放方式？【北京2014】 A.9 B.12 C.14 D.16 楚香凝解析： 解法一：四种元素错位重排有9种，选A 解法二：ABCD四辆车分别停放在一二三四号位置，A先选有三种情况，假设A选了二号，那么B再选、有三种选择，剩下C和D都只有一种选择，共3*3=9种，选A 例2：相邻的4个车位中停放了4辆不同的车，现将所有车开出后再重新停入这4个车位，要求有三辆车不能停在原来的车位中，则一共有多少种不同的停放方式？ A.2 B.6 C.8 D.9 楚香凝解析：先选出停的正确的那辆车C（4 1）=4种，剩下三辆车错位重排有2种，共4*2=8种，选C 例3：相邻的4个车位中停放了4辆不同的车，现将所有车开出后再重新停入这4个车位，要求有两辆车不能停在原来的车位中，则一共有多少种不同的停放方式？ A.2 B.6 C.8 D.9 楚香凝解析：先选出停的正确的两辆车C（4 2）=6种，剩下两辆车错位重排有1种，共6*1=6种，选B

听说“9”和“44”与错位排列更配哦-全错位排列问题

听说“9”和“44”与错位排列更配哦-全错位排列问题亲，如果我说记住两个数字就能搞定数量关系中的一类难题，你信吗? 先不用忙着回答! 或许你将信将疑，但等你看完此文，你一定能找到足够的理由让自己相信。 一、问题导入 【引例1】唐僧、孙悟空、猪八戒、沙和尚4人在某公司不同岗位任职，现在需要调换岗位，要求每个人都不能在自己原来的岗位，则共有种不同的安排方法。 【引例2】有4名同学各写了一张贺卡，先全部收集起来，然后每人从中拿出一张贺卡，要求每个人都不拿自己的贺卡，则四张贺卡的不同分配方式共有种。 【引例3】将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同(即1不放1，2不放2，3不放3，4不放4，也就是说4个全部放错)，则共有种不同的放法。 不难发现，以上三个引例都是同一类问题，答案是多少呢?下面用枚举法给大家答案：假设原来顺序：A、B、C、D 枚举的时候注意按照一定规律进行，如果看成1、2、3、4号位置，那么第一步A可以放2、3、4号位置中的任意一个，第二步把B的位置确定，第三步确定C和D的位置：第1种错位排列：B、A、D、C(A在2位，B在1位，C、D位置就唯一确定了); 第2种错位排列：D、A、B、C(A在2位，B在3位，C、D位置就唯一确定了); 第3种错位排列：C、A、D、B(A在2位，B在4位，C、D位置就唯一确定了); 第4种错位排列：B、D、A、C(A在3位，B在1位，C、D位置就唯一确定了); 第5种错位排列：C、D、A、B(A在3位，B在4位，C、D位置可以是1、2); 第6种错位排列：D、C、A、B(A在3位，B在4位，C、D位置也可以是2、1); 第7种错位排列：B、C、D、A(A在4位，B在1位，C、D位置就唯一确定了); 第8种错位排列：C、D、B、A(A在4位，B在3位，C、D位置可以是1、2); 第9种错位排列：D、C、B、A(A在4位，B在3位，C、D位置也可以是2、1)。 可见，4个元素的错位排列一共有9种。即以上三道引例的答案都是9种。 那么，问题来了：图图老湿，我不想一个一个的枚举，眼睛都看花了，肿么办?而且如果下次不是4个元素了呢?答案又肿么办? 请耐心看下文。提前声明一下：接下来这一段需要一定的数学知识，如果觉得自己数学还不错的话可以详细逐字阅读;如果说NO，也没关系嗒，只需你记住最后结论即可哦! 二、理论推导

错位排列和禁位排列

错位排列和禁位排列

错位排列和禁位排列 1.问题提出 （1）某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？ （2）有5个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5个客人都不戴自己帽子的戴法有多少种？ 上述两个问题，实质上是同一种类型的问题，被著名数学家欧拉 （Leonard Euler ，1707 —1783）称为“组合数论”的一个妙题的“装错信封问题”的两个特例。“装错信封问题”是由当时最有名的数学家约翰?伯努利（John Bernoulli ，1667—1748） 的儿子丹尼尔?伯努利 （Danid Bernoulli ，1700—1782）提出来的，大意如下：一个人写了 n 封不同的信及相应的n 个不同的信封，他把这n 封信都装错了信封。问全部装错了信封的装法有几种？ 2.错位排列和禁位排列 1）错位排列：n 个相异元素中()m m n ≤个元素1 2 ,,,m i i i a a a ???，其中 () 1,2,,k i a k m =???不在第()1,2,,k i k m =???个位置（一下简称其为k i a 的本 位），而其他n m -个元素中的任何一个都在原来的位置（本位）的排列。如果n 个元素都不在本位，称为全错位排列。

2）禁位排列（一个元素禁止排在一个位置）：n 个相异元素中()m m n ≤个元素1 2 ,,,m i i i a a a ???，其中()1,2,,k i a k m =???不能排在第 () 1,2,,k j k m =???个位置的排列。 3）两者的区别在于：错位排列中除这m 个元素之外的其他n m -个元素都在本位，即这m 个元素只能在m 个位置 12,,,m i i i ???中排列，且不出现()1,2,,k i a k m =???在k i 位的情况；而禁位 排列中只限制m 个元素不在本位，因此()1,2,,k i a k m =???可以排 在1,2,,n ???中除k i 之外的任何位置。 3.禁位排列与全错位排列的种数 1）禁位排列数： 求禁位排列数，只需从n 个元素的全排列中除去指定元素占本位的排列即可，其中有1个元素占本位的排列数是11 1 n m n C P --，有两个元素占本位的排列数是211 n m n C P --，……，n 个元素占本位的排列数是m n m m n m C P --. 记错位排列和禁位排列的排列数分别为,m m n n D E ，用n D 表示n 个元素全错位排列。则由容斥原理有： 【禁位排列公式】()()()()012121m m m n m m m m E C n C n C n C n m =--+--???+--！！！！ 【证明】①当0m =时，等式左边为0 n E ，表示n 个元素没有 限制，所以有n n P n =！ ， 等式右边本应该有1m +项，当0m =时，只有1项，就是00 C n n =！！. 等式成立； ②假设()01k i k i n i n k n i i E C P --==-∑； ③那么当1m k =+时，设第1k +个元素为a ，则前k 个元素不

全装错信问题即全错位排列问题及拓展

全装错信问题即全错位排列问题及拓展 ——龙城老欧全装错信问题又称全错位排列问题，最早由瑞士数学家伯努利提出，最后由伯努利与他的学生欧拉讨论解决，这个问题就是—— 我们将编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信都和信封的编号不同，即1不能装进1，2不能装进2，3不能装进3……问有多少种装法？ 看到这个问题时，我们的第一反应就是退到简单处入手研究，如果只有一封信，2封信，3封信，4封信，……，然后从中再思考，之间是否有共性，是否有关联，共性用归纳，关联构成递推，或者其他。 〖解法〗 容易知道：a[1]=0,a[2]=1，a[3]=2，a[4]=6; 依我们设a[i]为i封信的全错位排列数据递归推理那么有 a[i]=(a[i-1]+a[i-2])×(i-1)， (i>=3)。 为什么？为什么？为什么？大多数人看不明白。 不急，尽量先自己思考，不行的话，听我来解释： 思考1：对于插入第i个元素，只可能有两种情况： 第一种情况:插入第i个元素时，前i-1个已经错位排好，则选择其中任意一个与第i个互换一定满足要求,选择方法共i-1种，前i-1位错排f[i-1]种，记f[i-1]*(i-1),如下图： 第二种情况:插入第i个元素时，前i-1个中恰有一个元素恰好在自己的位置上，即恰好只有一个元素不满足错位排列，其他i-2个错位排好，则将i与j交换，j在i-2位中的插入共i-1种，前i-2位错排a[i-2]种，记f[i-2]*(i-1)，如下图： 以上两种情况求和可得: a[i]=(a[i-1]+a[i-2])×(i-1) (i>=3) 我们还可以这样思考： 思考2：有(i-1)个人已经都坐在在自己的板凳上了，现在第i个人张三带着自己的板凳来了，下面我们来对这i个人进行全错位排排坐， 方法1：前面(i-1)个人中的某一个带着板凳出来与第i个人张三互换板凳坐（有（i-1）种方法），其它(i-2)个人进行全错位排列（有a[i-2]种方法），这样就整体上都是全错位；

句子排序方法及习题附问题详解

句子排序方法及习题附答案 怎样排列顺序错乱的句子 把排列错乱的句子整理成一段通顺连贯的话，能训练对句子的理解能力、有条理表达能力和构段能力。这样的练习一般可按五步进行。 第一步，仔细阅读每句话或每组句子，理解它们的主要内容；第二步，综合各句的意思，想想这些话主要说的是什么内容；第三步，想想全段的内容按什么顺序排列好，即找出排列顺序的依据，如，是按事情发展顺序，还是时间顺序，或方位，还是“总分”等；第四步，按确定的排列依据排列顺序；第五步，按排好的顺序仔细读两遍，看排得对不对，如发现有的句子排得位置不对，就进行调整，直到这段话排得通顺连贯为止。把错乱的句子排列好，这是小学阶段语文练习中的一个重要形式，必须好好掌握。学会排列句子，不仅能提高我们的思维能力，还能提高我们的写作能力。那么，如何学会排列好句子呢？我们可以按下列方法进行。 一、按事情发展的顺序排列 有些错乱的句子，我们在排列时，应仔细分析句与句之间的联系。常见的错乱句子，往往叙述了一件完整的事，或者活动的具体过程。那么，我们就可以按事情发展的顺序来排列。 二、按时间先后顺序排列 对一些错乱的句子，我们可以找出表示时间概念的词语，如，早晨、上午、中午、下午等词，然后按时间先后顺序进行排列句子。 三、按先总述后分述的顺序排列 根据这段话的特点，找出这句话是个中心句，其他句子都是围绕着这句话来说的。显而易见，我们可按先总后分的顺序来排列句子。 四、按空间推移的顺序排列 所谓空间推移，就是由地点的转移，表达出不同的内容。排列时，要十分注意，不要与其他的方法相混淆。 对练习排列句子有帮助 把错乱的句子排列好，这是小学阶段语文练习中的一个重要形式，必须好好掌握。学会排列句子，不仅能提高我们的思维能力，还能提高我们的写作能力。那么，如何学会排列好句子呢？我们可以按下列方法进行。 一、按事情发展的顺序排列 有些错乱的句子，我们在排列时，应仔细分析句与句之间的联系。常见的错乱句子，往往

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

排列组合问题之全错位排列问题 （一个通项公式和两个递推关系） 一、问题引入： 问题1、4名同学各写一张贺卡，先集中起来，然后每人从中拿出一张别人写的贺卡，则四张贺卡的不同分配方式共有多少种？ 问题2、将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同，则共有多少种不同的放法？ 这两个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把这种限制条件的排列问题叫做全错位排列问题。 问题3、五位同学坐在一排，现让五位同学重新坐，至多有两位同学坐自己原来的位置，则不同的坐法有多少种？ 解析：可以分类解决：第一类，所有同学都不坐自己原来的位置； 第二类，恰有一位同学坐自己原来的位置； 第三类，恰有两位同学坐自己原来的位置。 对于第一类，就是全错位排列问题；对于第二、第三类有部分元素还占有原来的位置，其余元素可以归结为全错位排列问题，我们称这种排列问题为部分错位排列问题。 设n 个元素全错位排列的排列数为n T ，则对于问题3，第一类全错位排列的排列数为 5T ；第二类先确定一个排原来位置的同学有5种可能，其余四个同学全错位排列，所以第 二类的排列数为45T ；第三类先确定两个排原位的同学，有2 510C =种可能，其余三个同学 全错位排列，所以第三类的排列数为310T ，因此问题3的答案为：543510109T T T ++=。 由于生活中很多这样的问题，所以我们有必要探索一下关于全错位排列问题的解决方法。 二、全错位排列数的递推关系式之一： ()()121n n n T n T T --=-+ ()3n ≥ ①定义：一般地，设n 个编号为1、2、3、… 、i 、…、j 、…、n 的不同元素1a 、 2a 、3a 、…、i a 、…、j a 、…、n a ，排成一排，且每个元素均不排在与其编号相同的位 置，这样的全错位排列数为n T ，则 21T =；32T =；()()121n n n T n T T --=-+，()3n ≥。 ②递推关系的确立： 显然当1n =、2时，有10T =，21T =。 当3n ≥时，在n 个不同元素中任取一个元素i a 不排在与其编号相对应的i 位，必排在剩下1n -个位置之一，所以i a 有1n -种排法。 对i a 每一种排法，如i a 排在j 位，对应j 位的元素j a 的排位总有两种情况： 第一种情况：j a 恰好排在i 位上。此时，i a 排在j 位，j a 排在i 位，元素i a ，j a 排位已定。还剩2n -个元素，每个元素均有一个不能排的位置，它们的排位问题就转化为2n - 个元素全错位排列数，应有2n T -种。 第二种情况：j a 不排在i 位上。此时，i a 仍排在j 位，j a 不排在i 位，则j a 有1n -个位置可排。除i a 外，还有1n -个元素，每个元素均有一个不能排的位置，问题就转化为1n -n 个元素全错位排列数，应有1n T -种。 由乘法原理和加法原理可得：()()121n n n T n T T --=-+，()3n ≥。 利用此递推关系可以分别算出49T =，544T =。

排列组合错位重排

排列组合错位重排 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT

排列组合-错位重排 题型概述： 错位重排作为排列组合的一种模型，原理很复杂，但是应用上面很简答。 那我们就通过几个例题来学习下这种题型。 题型要点： 错位题型最直接的就是记住公式：一个元素错位重排的时候情况为0（因 为只有一个，不可能排错），两个元素错位重排情况为1，三个为2，四个为 9，五个为44，…………。从0,1,2,9,44可以看出后面的数为前面两数和的倍数， 那我们后面的情况也就不难推导出来。D n=（n-1）（D n-2+D n-1），（D1=0， D2=1，D3=2）。 如果从排列组合的角度展开，我们分别看下： 三个错排：三个全排列?三个序排?一个序排=A33?1?C31=2 四个错排：四个全排列?四个序排?两个序排?一个序排= 四个全排列?四个序排?两个错排?三个错排=A44?1?C42×1?C41×2=9 五个错排：五个全排列?五个序排?三个序排?两个序排?一个序排= 五个全排列?五个序排?两个错排?三个错排?四个错排= A55?1?C52×1?C52×2?C54×9=44………… ………… …………

例题： 1.四位厨师聚餐时各做了一道拿手菜，现在要求每个人去品尝一道菜，但不能尝自己做 的那道菜，问共有几种不同的尝法（11年浙江） 种种种种 2.五个瓶子都贴有标签，其中恰好贴错了三个，则贴错的可能情况有多少种（07年北 京） 3.要把A、B、C、D四包不同的商品放到货架上，但是，A不能放在第一层，B不能放在 第二层，C不能放在第三层，D不能放在第四层，那么，不同的放法共有（）种。 （09年云南）

全错位排列

一、问题导入 【引例1】唐僧、孙悟空、猪八戒、沙和尚4人在某公司不同岗位任职，现在需要调换岗位，要求每个人都不能在自己原来的岗位，则共有种不同的安排方法。 【引例2】有4名同学各写了一张贺卡，先全部收集起来，然后每人从中拿出一张贺卡，要求每个人都不拿自己的贺卡，则四张贺卡的不同分配方式共有种。 【引例3】将编号为1，2，3，4的四个小球分别放入编号为1，2，3，4的四个盒子中，要求每个盒子放一个小球，且小球的编号与盒子的编号不能相同(即1不放1，2不放2，3不放3，4不放4，也就是说4个全部放错)，则共有种不同的放法。 不难发现，以上三个引例都是同一类问题，答案是多少呢下面用枚举法给大家答案：假设原来顺序：A、B、C、D 枚举的时候注意按照一定规律进行，如果看成1、2、3、4号位置，那么第一步A可以放2、3、4号位置中的任意一个，第二步把B的位置确定，第三步确定C和D的位置：第1种错位排列：B、A、D、C(A在2位，B在1位，C、D位置就唯一确定了); 第2种错位排列：D、A、B、C(A在2位，B在3位，C、D位置就唯一确定了); 第3种错位排列：C、A、D、B(A在2位，B在4位，C、D位置就唯一确定了); 第4种错位排列：B、D、A、C(A在3位，B在1位，C、D位置就唯一确定了); 第5种错位排列：C、D、A、B(A在3位，B在4位，C、D位置可以是1、2); 第6种错位排列：D、C、A、B(A在3位，B在4位，C、D位置也可以是2、1); 第7种错位排列：B、C、D、A(A在4位，B在1位，C、D位置就唯一确定了); 第8种错位排列：C、D、B、A(A在4位，B在3位，C、D位置可以是1、2); 第9种错位排列：D、C、B、A(A在4位，B在3位，C、D位置也可以是2、1)。 可见，4个元素的错位排列一共有9种。即以上三道引例的答案都是9种。 二、理论推导 其实，上面引例涉及的三个问题的本质都是每个元素都不在自己编号的位置上的排列问题，我们把带这种限制条件的排列问题叫做全错位排列问题。 它是一个非常古老的数学问题，贝努利、欧拉等数学家都曾经研究过。这类问题虽然有难度，但我们解题是有快速破解的“窍门”的。且看下面详细解读： 我们将n个元素的全错位排列数记做Dn。 由于1个元素没有错位排列，因此D1=0。 2个元素时可以相互交换一下位置，即有1种错位排列，则D2=1。 当n≥3时，在n个不同元素中任取一个元素ai不排在与其编号相对应的i位，必排在剩下n-1个位置之一，所以ai有n-1种排法。 即第一步排ai，有n-1种。 第二步：排ai所占位置对应的元素。

全错位排列公式

全错位排列 先看下面例子： 例1． 5个人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法。 这个问题在高中很多参考书上都有，有几种解法，其中一种解法是用排除法： 先考虑5个全排列，有55A 种不同的排法，然后除去甲排在第一（有44A 种）与乙排第二（也有44A 种），但两种又有 重复部分，因此多减，必须加上多减部分，这样得到共有：543543278A A A -+=种。 现在考虑： 例2．5个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法。 仿上分析可得：543254323364A A A A -+-=种 这与全错位排列很相似。 全错位排列——即n 个元素全部都不在相应位置的排列。看下面的问题 例3．5个人站成一排，其中A 不站第一位，B 不站第二位，C 不站第三位，D 不站第四位，E 不站第五位，共有多少种不同的站法。 解析：上面例1，例2实际上可以看成n 个不同元素中有()m m n ≤不排在相应位置。 公式一：n 个不同元素排成一排，有m 个元素()m n ≤不排在相应位置的排列种数共有： ()1122121m n n n m n m n m n m n m n m A C A C A C A -------+++- 种 这个公式在n m =时亦成立，从而这个问题可能用上面的公式得出： 514233241505545352515044A C A C A C A C A C A -+-+-=种 （注意0000!1n C A ===） （1993年高考）同室四人各写一张贺年卡，先集中起来。然后每人从中拿一张别人送出的贺年卡。则四张贺年卡不同的分配方式有 (A)6种 (B)9种 (C)11种 (D)23种 解析：由上面公式得： 4132231404434241409A C A C A C A C A -+-+=种，∴选择B 答案 因此可得到全错位排列的公式： n 个不同元素排成一排，第一个元素不在第一位，第二个元素不在第二位，……，第n 个元素不在第n 位的排列数为： ()1122121n n n n n n n n n n n n n n n A C A C A C A -------+++- 这实际上是公式一的特殊情况。这个公式很有用，只要有特殊元素不站特殊位置的问题，都可以用这个公式很快得到解决，另一个计算公式：()111!111!2!3!!n n S n n ? ?=-+-++- ???

关于全错位问题的结论

关于“全错位问题”的一个重要结论 一般地，我们把“1”不放在第一位，“2”不放在第二位，“3”不放在第三位……。“n ”不放在第n 位，称为“全错位问题”。在全错位问题中，如果一共有n 个元素，我们用f(n)表示全错位问题的排法种数。则可得一个重要结论： f(n)=nf(n-1)+(-1)n ,(n ≧2) * 例如：n=1时，显然f(1)=0 n=2时 共1种情况 而f(2)=2f(1)+(-1)2=1 符合*式 n=3时 或 共2种情况 而f(3)=3f(2)+(-1)3 =3×1-1=2 符合*式 n=4时，举例：用1、2、3、4这四个数字组成无重复数字的四位

数，1不在个位，2不在十位，3不在百位，4不在千位，共有多少种排法？ 列举如下： 共9种排法 而f(4)=4f(3)+(-1)4=4×2+1=9符合*式 同理可验证： F(5)=5f(4)+(-1)5=44成立…… 下面给予一般性证明f(n)=nf(n-1)+(-1)n ,(n≧2) 1.当n=2时，f(3)=1，f(3)=3f(2)-1=2，等式成立， 当n=3时，f(3)=2，f(4)=4f(3)+1=9，等式成立； 2.假设n≤k （k≧3）等式成立，即k个元素a1、a2、a3……a k全错位排序的方法数的递推关系为f(k)=kf(k-1)+(-1)k， 则当n=k+1时，设全错位排序的元素为a1、a2、a3……a k、a k+1。在k个元素全错位排序的基础上，k+1个元素全错位排序后，它们全错位排序的方法分为两类，（1）a k+1与a i（i=1、2、……k）互调位置，其余元素全错位排列，方法数为kf(k-1)；（2）a k+1在a i的位置上，但a i （i=1、2、……k）不在a k+1的位置上，相当于a k+1将的每一个全错位排

排列组合错位重排图文稿

排列组合错位重排文件管理序列号：[K8UY-K9IO69-O6M243-OL889-F88688]

排列组合-错位重排 题型概述： 错位重排作为排列组合的一种模型，原理很复杂，但是应用上面很 简答。那我们就通过几个例题来学习下这种题型。 题型要点： 错位题型最直接的就是记住公式：一个元素错位重排的时候情况为0（因为只有一个，不可能排错），两个元素错位重排情况为1，三个为2，四个为9，五个为44，…………。从0,1,2,9,44可以看出后面的数为前面两数和的倍数，那我们后面的情况也就不难推导出来。D n =（n-1） （D n-2+D n-1），（D 1=0，D 2=1，D 3=2）。 如果从排列组合的角度展开，我们分别看下： 三个错排：三个全排列?三个序排?一个序排=A 33?1?A 31=2 四个错排：四个全排列?四个序排?两个序排?一个序排= 四个全排列?四个序排?两个错排?三个错排=A 44 ?1? A 42×1?A 41×2=9 五个错排：五个全排列?五个序排?三个序排?两个序排?一个序排= 五个全排列?五个序排?两个错排?三个错排?四个错排 = A 55?1?A 52×1?A 52×2?A 54×9=44 ………… …………

………… 例题： 1.四位厨师聚餐时各做了一道拿手菜，现在要求每个人去品尝一道菜， 但不能尝自己做的那道菜，问共有几种不同的尝法（11年浙江） A.6种 B.9种 C.12种 D.15种 2.五个瓶子都贴有标签，其中恰好贴错了三个，则贴错的可能情况有多 少种（07年北京） A.60 B.46 C.40 D.20 3.要把A、B、C、D四包不同的商品放到货架上，但是，A不能放在第一 层，B不能放在第二层，C不能放在第三层，D不能放在第四层，那么，不同的放法共有（）种。（09年云南） A.6 B.7 C.8 D.9

整理：全错位排列

作为排列组合试题的一种特殊类型，全错位排列在公考中也偶有出现。因为较之其他题型来说，全错位排列的原理需要结合举例子递推出来，故考生朋友们理解起来有一定的困难。在此京佳崔熙琳老师将考试中出现过的该类题型进行汇总，希望给各位考生提供一些帮助。 公考行测：数量关系之“全错位排列”经典真题剖析 一、全错位排列递推公式的推导 把编号从1到n的n个小球放到编号为从1到n的n个盒子里，假定每个盒子中的小球编号与盒子的编号不得一样(即：1号球不在1号盒，2号球不在2号盒，依次类推)，请问共有几种放法？ 用列举法进行公式的推导： 图1

通过图1可以发现，An与n存在如下的递推关系： An＝(An－2＋A n－1)×(n－1)(其中，n≥3，且A 1＝0，A 2＝1) 此递推公式可以产生一个全错位排列的结果数列： A1＝0； A2＝1； A3＝(A1＋A2)×(3－1)＝2； A4＝(A2＋A3)×(4－1)＝9； A5＝(A3＋A4)×(5－1)＝44； A6＝(A4＋A5)×(6－1)＝265..................。. 考生在遇到全错位排列试题时候只需要按照上述递推公式进行简单推导即可求出结果。 二、真题解析 例1：(2011年浙江省考真题55题) 四位厨师聚餐时各做了一道拿手菜。现在要求每个人去品尝一道菜，但不能尝自己做的那道菜。问共有几种不同的尝法？ A.6种 B.9种 C.12种 D.15种 【答案与解析】B。此题为全错位排列试题。根据全错位排列公式“An＝(An－2＋A n －1)×(n－1)(其中，n≥3，且A 1＝0，A 2＝1)”，可知，当n＝4时，共有9种尝法。 例2：(2010年某省考试真题) 五个瓶子都贴了标签，其中恰好贴错了三个，则错的可能情况共有多少种？ A.5 B. 10 C. 15 D. 20 【答案与解析】D。做此类题目时通常分为两步：第一步，从五个瓶子中选出三个，共有C(3，5)＝10种选法；第二步，将三个瓶子全部贴错，根据上表有2种贴法。则恰好贴错三个瓶子的情况有10×2＝20种。

错位排列和禁位排列

错位排列和禁位排列 1.问题提出 （1）某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？ （2）有5个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家后，他们的妻子都发现，他们戴了别人的帽子，问5个客人都不戴自己帽子的戴法有多少种？ 上述两个问题，实质上是同一种类型的问题，被著名数学家欧拉（LeonardEuler ，1707—1783）称为“组合数论”的一个妙题的“装错信封问题”的两个特例。“装错信封问题”是由当时最有名的数学家约翰?伯努利（JohnBernoulli ，1667—1748）的儿子丹尼尔?伯努利（DanidBernoulli ，1700—1782）提出来的，大意如下：一个人写了n 封不同的信及相应的n 个不同的信封，他把这n 封信都装错了信封。问全部装错了信封的装法有几种？ 2.错位排列和禁位排列 1）错位排列：n 个相异元素中()m m n ≤个元素12,,,m i i i a a a ???，其中()1,2,,k i a k m =???不在第 ()1,2,,k i k m =???个位置（一下简称其为k i a 的本位），而其他n m -个元素中的任何一个都在原来的位置（本 位）的排列。如果n 个元素都不在本位，称为全错位排列。 2）禁位排列（一个元素禁止排在一个位置）：n 个相异元素中()m m n ≤个元素12,,,m i i i a a a ???，其中 ()1,2,,k i a k m =???不能排在第()1,2,,k j k m =???个位置的排列。 3）两者的区别在于：错位排列中除这m 个元素之外的其他n m -个元素都在本位，即这m 个元素只能在m 个位置12,,,m i i i ???中排列，且不出现()1,2,,k i a k m =???在k i 位的情况；而禁位排列中只限制m 个元素不在本位，因此()1,2,,k i a k m =???可以排在1,2,,n ???中除k i 之外的任何位置。 3.禁位排列与全错位排列的种数 1）禁位排列数： 求禁位排列数，只需从n 个元素的全排列中除去指定元素占本位的排列即可，其中有1个元素占本位的排列数是1 1 1n m n C P --，有两个元素占本位的排列数是2 1 1n m n C P --，……，n 个元素占本位的排列数是m n m m n m C P --. 记错位排列和禁位排列的排列数分别为,m m n n D E ，用n D 表示n 个元素全错位排列。则由容斥原理有： 【禁位排列公式】()()()()0 1 2 121m m m n m m m m E C n C n C n C n m =--+--???+--！！！！ 【证明】①当0m =时，等式左边为0n E ，表示n 个元素没有限制，所以有n n P n =！， 等式右边本应该有1m +项，当0m =时，只有1项，就是0 0C n n =！！.等式成立； ②假设()0 1k i k i n i n k n i i E C P --== -∑；

排列组合公式巧解行测中比赛计数 错位排列问题

公务员考试《行政职业能力测验》考试中的数量关系部分经常会出现比赛计数问题，令许多考生头疼不已。其实，比赛计数问题是有一定技巧的，掌握了这些技巧，不仅可以节约时间，而且对正确解题有很大帮助。习题教研中心公务员考试辅导专家王永恒老师在文中通过实例介绍了“比赛计数”问题的快速解题方法，希望能给广大考生备考有所启发和帮助。 一、比赛计数问题 根据比赛规则，比赛计数问题主要分为四类，每类比赛都有对应的解题方法，如下所示： 注意：单循环赛，即任意两队打一场比赛，和顺序无关，所以是组合问题；双循环赛，即任意两个队打两场比赛，和顺序有关，所以是排列问题。 例1．100名男女运动员参加乒乓球单打淘汰赛，要产生男、女冠军各一名，则要安排单打赛多少场？（） A．90 B．95 C．98 D．100 【习题解析】设有男运动员a人，女运动员b人。因为是淘汰赛，则要产生男冠军需要a－1场比赛，产生女冠军需要b－1场比赛，总的比赛场次需要a+b－2场。 例2．足球世界杯决赛圈有32支球队参加，先平均分成八组，以单循环方式进行小组赛；每组前两名的球队再进行淘汰赛。直到产生冠、亚、季军，总共需要安排（）场比赛。 A．48 B．63 C．64 D．65 【习题解析】首先将32人平均分成八组，则每组有4支球队，每组球队要进行单循环赛，则每组有，则八组总共需要；又因为在小组赛中每组决出前两名，八组一共 决出16支队，也就是再对这16支队伍进行淘汰赛，直到产生冠、亚、季军，则有16场比赛。所以总比赛场次为48+16=64。 例3．8个甲级队应邀参加比赛，先平均分成两组，分别进行单循环赛，每组决出前两名，再由每组的第一名和另一组的第二名进行淘汰赛，获胜者角逐冠、亚军，败者角逐第3、4名，整个赛程的比赛场数是（） A．16 B．15 C．14 D．13 【习题解析】此题与例2的思路相同，不再赘述。 以上比赛计数问题的解题方法简单易懂，容易掌握，希望考生能举一反三，提高解题速度和答题的准确率。 二、错位排列问题 排列组合问题向来是考生备考行测数量关系的难点之一，而其中的错位排列问题更是让考生晕头转向。不过，虽然错位排列问题有难度，但是也有快速解决之道。为帮助考生攻克难关，习题公务员考试辅导专家王永恒老师总结多年教研心得，为考生们详细解析错位排列问题的答题方法。 错位排列问题是一个古老的问题，最先由贝努利（Bernoulli）提出，其通常提法是：n 个有序元素，全部改变其位置的排列数是多少？所以称之为“错位”问题。大数学家欧拉（Euler）等都有所研究。下面先给出一道错位排列题目，让广大考生有直观感觉。

高中数学完整讲义——排列与组合5.排列组合问题的常见模型1

1．基本计数原理 ⑴加法原理 分类计数原理：做一件事，完成它有n 类办法，在第一类办法中有1m 种不同的方法，在第二类办法中有2m 种方法，……，在第n 类办法中有n m 种不同的方法．那么完成这件事共有12n N m m m =+++种不同的方法．又称加法原理． ⑵乘法原理 分步计数原理：做一件事，完成它需要分成n 个子步骤，做第一个步骤有1m 种不同的方法，做第二个步骤有2m 种不同方法，……，做第n 个步骤有n m 种不同的方法．那么完成这件事共有12n N m m m =???种不同的方法．又称乘法原理． ⑶加法原理与乘法原理的综合运用 如果完成一件事的各种方法是相互独立的，那么计算完成这件事的方法数时，使用分类计数原理．如果完成一件事的各个步骤是相互联系的，即各个步骤都必须完成，这件事才告完成，那么计算完成这件事的方法数时，使用分步计数原理． 分类计数原理、分步计数原理是推导排列数、组合数公式的理论基础，也是求解排列、组合问题的基本思想方法，这两个原理十分重要必须认真学好，并正确地灵活加以应用． 2． 排列与组合 ⑴排列：一般地，从n 个不同的元素中任取()m m n ≤个元素，按照一定的顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列．（其中被取的对象叫做元素） 排列数：从n 个不同的元素中取出()m m n ≤个元素的所有排列的个数，叫做从n 个不同元素中取 出m 个元素的排列数，用符号A m n 表示． 排列数公式：A (1)(2) (1)m n n n n n m =---+，m n +∈N ，，并且m n ≤． 全排列：一般地，n 个不同元素全部取出的一个排列，叫做n 个不同元素的一个全排列． n 的阶乘：正整数由1到n 的连乘积，叫作n 的阶乘，用!n 表示．规定：0!1=． ⑵组合：一般地，从n 个不同元素中，任意取出m ()m n ≤个元素并成一组，叫做从n 个元素中任取m 个元素的一个组合． 组合数：从n 个不同元素中，任意取出m ()m n ≤个元素的所有组合的个数，叫做从n 个不同元素中，任意取出m 个元素的组合数，用符号C m n 表示． 组合数公式：(1)(2)(1)! C !!()! m n n n n n m n m m n m ---+==-，,m n +∈N ，并且m n ≤． 组合数的两个性质：性质1：C C m n m n n -=；性质2：1 1C C C m m m n n n -+=+．（规定0C 1n =） 知识内容 排列组合问题的常见模型1

附录一：排列组合中的基本解题方法之错位重排法(1)

排列组合中的基本解题方法之错位重排法 一、基础理论 错位重排法主要是排列组合中的公式法解题，所以大家先要了解什么是错位重排法和对应的公式是什么? (1)什么是错位重排。 如图1：A、B、C、D、E是五个人，①②③④⑤是五个座位。如下图所示就是对号入座。 如图2：五个人全都不去自己的位置，只能去别人的位置，即全部错位。 所以这里所说的错位重排即全部错位。 (2)错位重排的公式是什么?

这个图的意思是：如果只有1个人A，只有1个座位，而这个人还不去自己的位置上去，那么有0种排列方法。如果有两个人A、B，只有2个座位，而这两个人都不能去做自己的位置，那么只能交换位置，即1种排列方法。如果有三个人A、B、C，有三个位置每个人都不去自己的位置，那么只能A去2，B去3，C去①或A去③，B去①，C去②2种排列方法。那么如果是A、B、C、D四个人错位呢那么共有9种排法，如果五个人错位，共44种排法，如果六个人错位，共265种方法。 错位重排数字：0,1,2,9,44,265，… 注：一般国考和地方性公务员考试，只考到前五个错位重排，所以大家在记得时候只要记住前五个基本就可以了。 二、真题精析 例1、将袋子中的四个红球排成一排，若要求1号球不在第一个位置，2号球不在第二个位置，3号球不在第三个位置，4号球不在第四个位置，问有()种排列方法 A.6 B.9 C.32 D.44 【分析】题干中的四个红球，就类似的是4个人，每个人都不去自己对应的位置，所以完全符合错位重排公式。 【解析】4个错位重排。所以答案对应公式里面的9。答案为B项

例2、四位厨师聚餐时各做了一道拿手菜。现在要求每个人去品尝一道菜，但不能尝自己做的那到菜。问共有几种不同的尝法? A.6种 B.9种 C.12种 D.15种 【答案】B 【解析】此题为错位重排，根据错位重排公式可知，有9种尝法。 小结：满足错位重排公式直接应用公式法解题。 三、错位重排法的综合运用 例3、五个瓶子都贴了标签，其中恰好贴错了三个，贴错的可能情况共有多少种? A.6 B.10 C.12 D.20 【答案】D 【分析】此题也是错位重排但不是全部错位，我们可以部分应用错位重排来进行解题。 【解析】分步进行：第一步，选出三个瓶子，这三个瓶子恰好贴错了，有C(5,3)=10种;第二步，这三个瓶子满足错位重排，所以对应的公式数据应该是2。最后根据乘法原理，共有10×2=20种。 小结：所以错位重排公式的解题关键是能否准确的找到需要错位重排的数据。