全错位排列递推公式的简易推导(齐麟-晋级)

关于“全错位问题”的一个重要结论一般地，我们把“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将的每一个全错位排列的元素置换一遍，由假设知a1、a2、a3……a k全错位排序的方法数为f(k)，得该类全错位排序的方法数为k f(k).故f(k+1)=k f(k)+kf(k-1),由假设f(k)=kf(k-1)+(-1)k，∴f(k+1)=k f(k)+kf(k-1)=k f(k)+f(k)-(-1)k=（k+1）f(k)+(-1)k+1.即当n=k+1时，等式也成立.所以，n个元素全错位排列的方法数的递推关系为f(n)=nf(n-1)+(-1)n (n≧2).下面举例说明*式的应用例1.同室4人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送出的贺卡,则4张贺卡不同的分配方式有______种?[解]此题属于4个元素的全错位问题由f(n)=nf(n-1)+（-1）3得f(4)=9故分配方式有9种例2．设编号为1、2、3、4、5的五个球及编号为1、2、3、4、5的五个盒子，一盒内放一球，恰有两个球的编号与盒子编号相同，则投放总数有多少？[解]“恰有两个球的编号与盒子编号相同”，等价于“恰有三个球的编号与盒子编号不同”。

公考行测：数量关系之“全错位排列”真题剖析作为排列组合试题的一种特殊类型，全错位排列在公考中也偶有出现。

因为较之其他题型来说，全错位排列的原理需要结合举例子递推出来，故考生朋友们理解起来有一定的困难。

在此京佳崔熙琳老师将考试中出现过的该类题型进行汇总，希望给各位考生提供一些帮助。

公考行测：数量关系之“全错位排列”经典真题剖析一、全错位排列递推公式的推导把编号从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.5B. 10C. 15D. 20【答案与解析】D。

做此类题目时通常分为两步：第一步，从五个瓶子中选出三个，共有C(3，5)＝10种选法；第二步，将三个瓶子全部贴错，根据上表有2种贴法。

全错位排列先看下面例子：例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 ≤不排在相应位置的排列种数共有：()1122121mn 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 位的排列数为： ()1122121nn n n n n n n n n n n n n n A C A C A C A -------+++- 这实际上是公式一的特殊情况。

关于“全错位问题”的一个重要结论一般地，我们把“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将的每一个全错位排列的元素置换一遍，由假设知a1、a2、a3……a k全错位排序的方法数为f(k)，得该类全错位排序的方法数为k f(k).故f(k+1)=k f(k)+kf(k-1),由假设f(k)=kf(k-1)+(-1)k，∴f(k+1)=k f(k)+kf(k-1)=k f(k)+f(k)-(-1)k=（k+1）f(k)+(-1)k+1.即当n=k+1时，等式也成立.所以，n个元素全错位排列的方法数的递推关系为f(n)=nf(n-1)+(-1)n (n≧2).下面举例说明*式的应用例1.同室4人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送出的贺卡,则4张贺卡不同的分配方式有______种?[解]此题属于4个元素的全错位问题由f(n)=nf(n-1)+（-1）3得f(4)=9故分配方式有9种例2．设编号为1、2、3、4、5的五个球及编号为1、2、3、4、5的五个盒子，一盒内放一球，恰有两个球的编号与盒子编号相同，则投放总数有多少？[解]“恰有两个球的编号与盒子编号相同”，等价于“恰有三个球的编号与盒子编号不同”。

组合数学-全错位排序公式不容易系列之⼀Problem Description⼤家常常感慨，要做好⼀件事情真的不容易，确实，失败⽐成功容易多了！做好“⼀件”事情尚且不易，若想永远成功⽽总从不失败，那更是难上加难了，就像花钱总是⽐挣钱容易的道理⼀样。

话虽这样说，我还是要告诉⼤家，要想失败到⼀定程度也是不容易的。

⽐如，我⾼中的时候，就有⼀个神奇的⼥⽣，在英语考试的时候，竟然把40个单项选择题全部做错了！⼤家都学过概率论，应该知道出现这种情况的概率，所以⾄今我都觉得这是⼀件神奇的事情。

如果套⽤⼀句经典的评语，我们可以这样总结：⼀个⼈做错⼀道选择题并不难，难的是全部做错，⼀个不对。

不幸的是，这种⼩概率事件⼜发⽣了，⽽且就在我们⾝边：事情是这样的——HDU有个⽹名叫做8006的男性同学，结交⽹友⽆数，最近该同学玩起了浪漫，同时给n个⽹友每⼈写了⼀封信，这都没什么，要命的是，他竟然把所有的信都装错了信封！注意了，是全部装错哟！现在的问题是：请⼤家帮可怜的8006同学计算⼀下，⼀共有多少种可能的错误⽅式呢？Input输⼊数据包含多个多个测试实例，每个测试实例占⽤⼀⾏，每⾏包含⼀个正整数n（1<n<=20），n表⽰8006的⽹友的⼈数。

Output对于每⾏输⼊请输出可能的错误⽅式的数量，每个实例的输出占⽤⼀⾏。

Sample Input2 3Sample Output1 2AuthorlcyMean:略analyse:就是错排公式的简单运⽤。

下⾯来了解⼀下错排公式。

所谓错排就是全错位排序公式，即被著名数学家欧拉(Leonhard Euler，1707－1783)称为组合数论的⼀个妙题的“装错信封问题”，他求解这样的问题:⼀个⼈写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？递推公式：f(n)=(n-1) * {f(n-1)+f(n-2)}Time complexity：O(n)Source code：// Memory Time// 1347K 0MS// by : Snarl_jsb// 2014-09-15-21.27#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<map>#include<string>#include<climits>#include<cmath>#define N 1000010#define LL long longusing namespace std;long long a[N];void cuopai(long long n) //// Formula : f(n)=(n-1)*{f(n-1)+f(n-2)} ;{a[1]=0,a[2]=1;for(long long i=3;i<=n;i++){a[i]=(i-1)*(a[i-1]+a[i-2]);}}int main(){// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout); cuopai(30);int n;while(cin>>n){cout<<a[n]<<endl;}return 0;}。

全错位排列先看下面例子：例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 ≤不排在相应位置的排列种数共有：()1122121mn 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 位的排列数为： ()1122121nn n n n n n n n n n n n n n A C A C A C A -------+++- 这实际上是公式一的特殊情况。

全错位排列 先看下面例子：例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 这实际上是公式一的特殊情况。

全错位排列dn的公式全文共四篇示例，供读者参考第一篇示例：全错位排列是排列组合中的一种特殊情况，它是指将一组元素进行重新排列，使得每个元素都位于原始位置以外。

全错位排列也称为dn排列，其中n表示元素的个数。

在全错位排列中，没有任何元素位于原始位置上，这使得全错位排列在排列组合中具有独特的特性。

在数学中，全错位排列的计算方法可以用一个公式来表示，这个公式可以帮助我们计算任意元素个数的全错位排列数量。

下面我们就来详细介绍全错位排列的公式及其推导过程。

假设有n个元素需要进行全错位排列，首先我们可以计算出n个元素的所有排列数量，这个数量可以用n!来表示，表示的是n的阶乘。

然后我们来计算n个元素的全错位排列数量。

假设第一个元素A有n-1种错误排列方法(把n-1个数安均在一起得到n个数的错位排列数)，那么就有n-1种排法。

假设元素A固定在第一个位置，那么剩下的元素就剩下n-1个元素。

这n-1个元素就要错位排列(错位排列其实就是将元素A与其他元素进行交换得到不同的排列)。

由于有n种情况可以选择元素A在第一个位置，所以总共就有n*(n-1)种情况。

现在我们来考虑其他的元素B，如何计算B在排列中的错位情况呢？实际上第一个元素A和其他元素B、C……之间的错位情况是相互独立的。

即当A的错位情况确定时，B的错位情况是无法受到A的影响的。

B在错位情况上有(n-1)*(n-2)种可能。

同样的道理，对于C，C有(n-2)*(n-3)种可能，以此类推，最后一个元素有1*0种可能。

根据乘法原理，n个元素的全错位排列总数为：(n-1)! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^(n-1)/n!)这个公式表示了n个元素的全错位排列数量，其中n!表示n的阶乘，(n-1)!表示n-1的阶乘，以此类推。

而其中的每一项都是错位排列的一部分，通过不断累加可以得到n个元素的全错位排列数量。

通过这个公式，我们可以计算出任意元素个数的全错位排列数量，这对于解决一些排列组合问题具有重要的意义。

全错位排列计算错位全排列问题什么是错位全排列问题？其实很简单，在生活中可能都会遇到：“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(Danid Bernoulli，1700－1782)提出来的，大意如下：一个人写了n 封不同的信及相应的n 个不同的信封，他把这n 封信都装错了信封，问都装错信封的装法有多少种？为了解决这个看似简单的问题，我们从数学的角度出发，尝试几个常用的方法。

记装错n 封信的种类为D_n ，并且有n 封信a_1,a_2,...,a_n（1）枚举法（Enumeration method）计算种数当n 的值较小时，可以利用枚举法：n=1 时，不可能装错信，则D_1=0 ；n=2 时，显然装错信时，只可能为两者调换位置，则D_2=1 ；n=3 时，有(a_2,a_3,a_1) ，(a_3,a_1,a_2) 两种装法，则D_3=2 ；n=4 时，装法如下：(a_2,a_1,a_4,a_3) ，(a_2,a_3,a_4,a_1) ，(a_2,a_4,a_1,a_3) ，(a_3,a_1,a_4,a_2) ，(a_3,a_4,a_1,a_2) ，(a_3,a_4,a_2,a_1) ，(a_4,a_1,a_2,a_3) ，(a_4,a_3,a_2,a_1) ，(a_4,a_3,a_1,a_2) ，则D_4=9 。

当n 的值越来越大时，枚举会变得异常复杂。

可以考虑用排列数（Permutation）和组合数（Combination），来得到错位全排列的计算公式。

（2）排列组合计算种数显然，n 封信的组合方式共有A_n^n=n! 种装法，接下来我们要做的就是扣掉其中重复的种类，保证计数“不重不漏”。

假设第一封信装对，即为剩下的n-1 个元素的一个全排列（All permutation），则有A_{n-1}^{n-1}=(n-1)! 种装法；并且当第二封信装对时，也有A_{n-1}^{n-1}=(n-1)! ，以此类推，每一封信装对时，都有(n-1)! 种装法。

公务员之路从华图起步全错位排列递推公式的简易证明华图教育 齐麟错位排列作为排列组合中的一类典型题目，自身难度较高，考生往往只是知其然而不知其所以然，即只了解全错位排列的递推公式，而不能理解其含义以及灵活的运用。

本文结合图示的方法，对全错位排列公式进行简易的证明。

首先，我们先来认识错位排列： 1.部分错位排列：【例】5个人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法。

用排除法：先考虑5个人的全排列，有55A 种不同的排法，然后除去甲排第一（有44A 种）与乙排第二（也有44A 种），但两种情况又有重复部分，因此多减了一部分，必须加上多减部分，这样得到共有：55A －244A ＋33A ＝78种。

2.全错位排列：【例】5个人站成一排，其中A 不站第一位，B 不站第二位，C 不站第三位，D 不站第四位，E 不站第五位，共有多少种不同的站法。

【分析】仿照以上解法，我们有51423324150555453525150D A C A C A C A C A C A 44=-⨯+⨯-⨯+⨯-⨯=故5人的全错位排列方式共有44种。

因此我们可以由容斥原理得到n 个元素的全错位排列公式： 错误！未找到引用源。

=n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!) 错位排列的递推公式简单计算后我们有：1D 0=；错误！未找到引用源。

；3D 2=。

计算四元素全错位排列时我们可以这样考虑：假定元素为A 、B 、C 、D ；对应的位置为a 、b 、c 、d 。

对于元素A ，我们可将其放在b 、c 、d 三个位置，容易看出，这三个位置对于元素A 来说是等价的；假定A 现在放在了b 位置。

ABCDb ac d公务员之路从华图起步此时，元素B 有两种选择：①放在a 位置；②不放在a 位置；当元素B 放在a 位置时，我们会发现，之后的情形与2D 相同；而当B 不放在a 位置时，情况与3D 相同（因为B 不放在a 位置，我们可以认为a 位置就是b 位置）。

数学错位排列公式错位排列，也称错位组合，是组合数学中的一种特殊排列形式。

在错位排列中，元素按照一定的规定重新排列，使得每个元素都不在其原始位置上。

错位排列在实际问题中有着广泛的应用，包括密码学、密码破解、数据加密等领域。

本文将介绍错位排列的概念、性质和计算公式。

一、错位排列的概念错位排列是指从n个元素中取出k个元素进行排列，使得每个元素都不在其原始位置上的排列方式。

具体而言，错位排列要求任意一个元素都不能出现在它原本应有的位置上。

二、错位排列的计算公式设记号D(n)表示n个元素的错位排列的个数。

1. 当n = 0，D(0) = 1；2. 当n = 1，D(1) = 0；3. 当n = 2，D(2) = 1；4. 当n > 2，D(n) = (n-1)(D(n-1) + D(n-2))。

根据上述公式，我们可以计算任意数量元素的错位排列。

三、错位排列的性质1. 错位排列的个数D(n)满足递推关系 D(n) = n*D(n-1) - (-1)^n。

2. 错位排列的个数D(n)可以通过康托展开公式求得。

康托展开是将一个排列转化为一个正整数的方法，该整数可以唯一地表示该排列。

具体而言，对于错位排列而言，康托展开公式为：D = (n-1)!x1 + (n-2)!x2 + ... + 2!x(n-2) + 1!x(n-1)，其中x1, x2, ..., x(n-1)分别表示每个元素与它原本应有位置的距离。

3. 错位排列具有唯一性，不存在重复的排列。

四、错位排列的应用错位排列在实际问题中有着广泛的应用。

1. 密码学：错位排列可以用于数据的加密与解密过程中，保障数据的安全性。

2. 信息传输：通过错位排列可以实现信息的加密和解密，保护隐私和安全。

3. 排队理论：错位排列可以用于描述某个系统中的排队顺序，研究系统中的平衡和稳定性。

4. 公平分配：错位排列可以用于公平地分配资源，确保每个人都有机会获得公正的权益。

全错位排列数公式的推导与化简一、提出问题装错信封问题：一个人写了n封不同的信及相应的n个不同的信封，若他把这n封信都装错了信封，那么装错信封的装法共有多少种？这是被著名数学家欧拉称为“组合数论的一个妙题”.把n个编号元素放在n个编号位置，元素编号与位置编号各不对应的排列方法称为错位排列法.将编号分别为1，2，3，…，n的n个不同元素a1，a2，a3，…，an，安排在这n个位置作全排列，若某个排列中每个元素都错位，则把这个全排列称为这n个不同元素的一个全错位排列.n个不同元素所有的全错位排列的个数称为全错位排列数，记为Dn，易得D1=0，D2=1，D3=2.二、递推关系式对于n=4，D4推导如下：按分步乘法计数原理考虑，第一步，先安排好第一个位置，有C13=3种排法.1234a3a1第二步，当安排好第一个位置后，假设安排的是a3，此时应考虑a1的位置，包括两种情况.若a1安排在第三个位置，则a2和a4排法是D2=1；若a1不安排在第三个位置，而a2不排在第二个位置，a4不排在第4个位置，对应的排法是D3=2.因此，当第一个位置安排的是a3时，对应的排法共有D2+D3=3，而第一个位置安排的各种情况地位相当，所以D4=C13（D2+D3）=9.对于Dn，推导如下：按分步乘法计数原理考虑，第一步，先安排好第一个位置，有C1n-1=n-1种排法.12…m…nama1第二步，当安排好第一个位置后，假设安排的是am，此时应考虑a1所放的位置，包括两种情况.若a1安排在第m个位置，则对应的排法是Dn-2；若a1不安排在第m个位置，由于a2不排在第二个位置，…，an不排在第n个位置，对应的排法是Dn-1.因此，当第一个位置安排的是an时，对应的排法共有Dn-1+Dn-2.而第一个位置安排的各种情况地位相当，所以Dn=C1n-1（Dn-1+Dn-2）. （1）整理Dn-nDn-1=-[Dn-1-（n-1）Dn-2].这表明，{Dn-nDn-1}是以D2-2D1=1为首项，公比为-1的等比数列，于是Dn-nDn-1=（-1）n-2，故Dn=nDn-1+（-1）n，其中n≥2，n ∈N+. （2）对于（1）式还有一种方法：设满足题意的放法有Dn种，当加入第n+1个元素和编号时，对于Dn的每一种放法，都可以把第i（i=1，2，3，…，n）个元素与第n+1个元素互换，把第i个元素放入第n+1个位置，有nDn种放法；也可先把第n+1个元素放入第i个位置，还余下n个位置，而把第i 个元素不放入第n+1个位置，其它元素也不放在对应的位置，则此时有nDn-1种放法，所以Dn+1=nDn+nDn-1，n≥2.三、全错位排列数公式利用递推关系式Dn-nDn-1=（-1）n，各项同除以n！，得Dnn！-Dn-1（n-1）！=（-1）nn！，构造数列bn=Dnn！，并利用数列恒等式bn=b1+（b2-b1）+（b3-b2）+…+（bn-bn-1）有Dnn！=01！+（-1）22！+（-1）33！+…+（-1）nn！，所以Dn=n！[12！-13！+…+（-1）n1n！].下面根据Dn=nDn-1+（-1）n利用分步迭代法推导Dn.D2=2D1+（-1）2，D3=3D2+（-1）3=3×2D1+3（-1）2+（-1）3.由于D1=0，则D4=4D3+（-1）4=4×3（-1）2+4（-1）3+（-1）4，D5=5D4+（-1）5=5×4×3（-1）2+5×4（-1）3+5（-1）4+（-1）5=5！2！（-1）2+5！3！（-1）3+5！4！（-1）4+5！5！（-1）5，…，所以Dn=n！[12！-13！+…+（-1）n1n！].还有一种方法：利用递推关系式Dn=C1n-1（Dn-1+Dn-2），设Dk=k！pk，k=1、2、3、…、n，则p1=0，p2=12.当n≥3时，由Dn=（n-1）（Dn-1+Dn-2）得n！pn=（n-1）（n-1）！pn-1+（n-1）（n-2）！pn-2，即n（n-1）！pn=（n-1）（n-1）！pn-1+（n-1）！pn-2，可知npn=（n-1）pn-1+pn-2，即npn=npn-1-pn-1+pn-2，则pn-pn-1=-pn-1-pn-2n，pn-1-pn-2=-pn-2-pn-3n-1，……，因此有pn-pn-1=（-1n）（-1n-1）（-1n-2）…（p2-p1）=（-1）n1n！，pn-1-pn-2=（-）n-11（n-1）！，…，p2-p1=（-1）212！.各式两边相加得pn=12！-13！+…+（-1）n1n！.所以Dn=n！pn=n！[1-11！+12！-13！+…+（-1）n1n！].四、化简公式由于e-1=1-11！+12！-13！+…+（-1）n1n！+…，e=2.71828.即e-1=pn+（-1）n+11（n+1）！+（-1）n+21（n+2）！+…余项为Rn=（-1）n+11（n+1）！+（-1）n+21（n+2）！+…=（-1）n+11（n+1）！（1-1n+2）+…那么该余项取值范围如何呢？由泰勒中值定理可知，在含有x0的某个开区间（a，b）内，函数f（x）可表示为（x-x0）的一个n次多项式pn（x）与一个余项Rn（x）之和，此和是关于（x-x0）的幂级数即泰勒级数，其中pn（x）=f（x0）+f ′（x0）（x-x0）+f ″（x0）2！（x-x0）2+…+f （n）（x0）n！（x-x0）n，余项为Rn（x）=f （n+1）（ξ）（n+1）！（x-x0）n+1.ξ在x与x0之间.若将函数f（x）=ex展开成x的幂级数即麦克劳林级数，由于x0=0，f （n+1）（x）=ex，则ex=1+x+x22！+x33！+…+xnn！+….对于任何有限的x、ξ（ξ在0与x之间），余项为Rn （x）=eξ（n+1）！xn+1.而函数f（x）=ex展开成x的幂级数中含有xn+1的项为f （n+1）（ξ）（n+1）！xn+1=ex（n+1）！xn+1，可见二者形式相似.由于x=-1，因此e-1的幂级数的余项为Rn（-1）=（-1）n+1eξ（n+1）！，且ξ∈（-1，0）.因此Dn=n！e-1-（-1）n+1eξn+1.设λ=|n！Rn|=|（-1）n+1eξn+1|=eξn+1，由于eξ∈（1e，1），当n=1时，λ。

全错位排列公式什么是错位全排列问题？其实很简单，在生活中可能都会遇到：“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(Danid Bernoulli，1700－1782)提出来的，大意如下：一个人写了 n 封不同的信及相应的n 个不同的信封，他把这 n 封信都装错了信封，问都装错信封的装法有多少种？为了解决这个看似简单的问题，我们从数学的角度出发，尝试几个常用的方法。

记装错 n 封信的种类为 D_n ，并且有 n 封信a_1,a_2,...,a_n（1）枚举法（Enumeration method）计算种数当 n 的值较小时，可以利用枚举法：n=1 时，不可能装错信，则 D_1=0 ；n=2 时，显然装错信时，只可能为两者调换位置，则D_2=1 ；n=3 时，有 (a_2,a_3,a_1) ， (a_3,a_1,a_2) 两种装法，则D_3=2 ；n=4 时，装法如下：(a_2,a_1,a_4,a_3) ， (a_2,a_3,a_4,a_1) ，(a_2,a_4,a_1,a_3) ，(a_3,a_1,a_4,a_2) ，(a_3,a_4,a_1,a_2) ， (a_3,a_4,a_2,a_1) ，(a_4,a_1,a_2,a_3) ， (a_4,a_3,a_2,a_1) ，(a_4,a_3,a_1,a_2) ，则 D_4=9 。

当 n 的值越来越大时，枚举会变得异常复杂。

可以考虑用排列数（Permutation）和组合数（Combination），来得到错位全排列的计算公式。

（2）排列组合计算种数显然， n 封信的组合方式共有 A_n^n=n! 种装法，接下来我们要做的就是扣掉其中重复的种类，保证计数“不重不漏”。

假设第一封信装对，即为剩下的 n-1 个元素的一个全排列（All permutation），则有 A_{n-1}^{n-1}=(n-1)! 种装法；并且当第二封信装对时，也有 A_{n-1}^{n-1}=(n-1)! ，以此类推，每一封信装对时，都有 (n-1)! 种装法。

数学错位排列公式(一)数学错位排列公式什么是错位排列？错位排列指的是从一个集合中，取出n个元素进行排列，使得每个元素都不在其原来的位置上的排列方式。

具体来说，给定n个元素的集合S，错位排列是指将集合S中的元素重新排列，使得对于任意1 ≤ i ≤ n，都有第i个元素不在原来的位置上。

公式表达错位排列的个数n！乘上错位因子：!Dn其中，错位因子!Dn的计算公式如下：!Dn = (n-1) * (!(n-1) + !(n-2))公式解释!Dn = (n-1) * (!(n-1) + !(n-2))中的!表示阶乘。

•(n-1)表示从n个元素中选取一个元素，将其放置在排列的最后一个位置上。

•!(n-1)表示从剩下的(n-1)个元素中得到错位排列的可能数。

•!(n-2)表示从剩下的(n-2)个元素中得到错位排列的可能数，其中(n-1)个元素已经放置在最后一个位置上。

因此，错位因子的计算是在选定了最后一个元素的情况下，对剩下的元素进行错位排列的个数的计算。

实际例子例子1：n=3给定一个集合S={A, B, C}，计算错位排列的个数。

根据公式，我们有： !D3 = (3-1) * (!(3-1) + !(3-2)) = 2 * (!(2) + !(1)) = 2 * (2 + 1) = 2 * 3 = 6因此，集合S={A, B, C}的错位排列个数为6。

例子2：n=4给定一个集合S={A, B, C, D}，计算错位排列的个数。

根据公式，我们有： !D4 = (4-1) * (!(4-1) + !(4-2)) = 3 * (!(3) + !(2)) = 3 * (2 + 1) = 3 * 3 = 9因此，集合S={A, B, C, D}的错位排列个数为9。

总结错位排列是一种特殊的排列方式，其中每个元素都不在原来的位置上。

错位排列的个数可以通过错位因子来计算，公式为!Dn = (n-1) * (!(n-1) + !(n-2))。

全错位排列递推公式全错位排列是指一个序列中的每个元素都不在其原始位置上的排列方式。

在数学中，我们可以使用递推公式来计算全错位排列的数量。

本文将介绍全错位排列的概念，并给出相应的递推公式。

一、全错位排列的定义全错位排列是指一个序列中的每个元素都不在其原始位置上的排列方式。

换句话说，对于一个长度为n的序列，全错位排列的每个元素i必须满足pi ≠ i，其中pi表示元素i的位置。

例如，对于长度为3的序列{1, 2, 3}，其全错位排列可以是{2, 3, 1}或者{3, 1, 2}等，但不能是{1, 2, 3}，因为其中元素1在其原始位置上。

二、全错位排列的数量为了计算全错位排列的数量，可以使用递推公式。

假设Dn表示长度为n的序列的全错位排列数量，则有以下递推公式：Dn = (n-1)(Dn-1 + Dn-2)其中D1 = 0，D2 = 1。

根据递推公式，我们可以通过计算Dn来得到长度为n的序列的全错位排列数量。

下面是具体的计算过程：D1 = 0D2 = 1D3 = (3-1)(D2 + D1) = 2(1 + 0) = 2D4 = (4-1)(D3 + D2) = 3(2 + 1) = 9D5 = (5-1)(D4 + D3) = 4(9 + 2) = 44依此类推，我们可以得到长度为n的序列的全错位排列数量。

三、应用举例全错位排列的概念和递推公式在实际问题中有着广泛的应用。

下面举例说明两个应用情景。

1. 座位安排问题：假设有n个人参加一个会议，会议的座位是按照1到n的顺序排列的。

为了增加交流和合作，组织者希望每个人坐在与其原始位置不同的位置上。

那么，可以使用全错位排列的递推公式来计算有多少种座位安排方式。

2. 文件排序问题：假设有一组文件需要根据一定的顺序进行排序，但不能按照文件原始顺序进行排序。

可以使用全错位排列的递推公式来计算有多少种文件排序的可能性。

通过以上两个应用举例，我们可以看到全错位排列的概念和递推公式在实际问题中起到了重要的作用，帮助我们解决座位安排和文件排序等问题。

错位相减法公式推导过程
嘿，咱今天来聊聊错位相减法公式的推导过程呀！这可是个超有趣的玩意儿呢！
咱先拿一个等比数列和一个等差数列来举例吧。

比如等比数列 an = a1 × q^(n-1) ，等差数列 bn = b1 + (n - 1)d 。

然后呢，我们把它们乘起来，得到一个新的数列cn = an × bn 。

那怎么推导错位相减法公式呢？这就好像搭积木一样，一层一层来。

我们先把这个新数列 cn 的前 n 项和写出来，设为 Sn 。

然后呢，我们把 q 乘到 Sn 上，得到 qSn 。

这时候，你看呀，原来的 Sn 和 qSn 之间是不是有很多可以相互抵消的部分呀？这就像是找到了一把钥匙，能打开推导的大门呢！
把它们相减，经过一系列神奇的运算，就能慢慢推导出错位相减法公式啦！
你说这神奇不神奇？就像变魔术一样！这其中的巧妙之处，真的让人惊叹不已呀！难道不是吗？
通过这样的推导过程，我们能更加深刻地理解数列的奥秘，能看到数学世界里那些隐藏的宝藏。

这就是错位相减法公式的推导过程呀，它就像一座神秘的城堡，等待着我们去探索，去发现其中的美妙和精彩！它真的是数学中的一颗璀璨明珠呀！。

关于排列组合问题之全错位排列递推公式的推导
这个推导是偷军团—云淡的，不是我的独创（转载请注明作者：军团—云淡）
把编号1-------------n的小球放到编号1------n的盒子里，全错位排列（1号球不在1号盒，2号球不在2号盒，依次类推），共有几种情况？
设n个球全放错的情况有s（n）种
1号盒子可以选[2,n] 共（n-1）种选择，设1号盒选择某号球后对应的错排次数是 a
（n-1）个选择对应的错排次数是相同的，则s（n）=（n-1）a
不妨设1号盒选择2号球
1：2号盒选择1号球，剩下（n-2）个球去错排，有s（n-2）种情况
2：2号盒不选择1号球，则后面总有一个盒子选择1号球，我们可以把1号球换成2号球，
对问题没有影响，此时就相当于对（n-1）个球去错排，有s（n-1）种情况
于是a= s（n-1)+s(n-2)
s(n)=(n-1) [ s（n-1）+s（n-2）]
s(2)=1,s(3)=2
s(4)=3*(1+2)=9
s(5)=4*(2+9)=44
.........
例题1.5个信封都写有1-5编号，现在放进5个有编号1-5的邮箱，问信封和邮箱都不相同的情况有多少种？。

错排的递推公式及推导错排递推公式：f(n)=(n-1)*(f(n-2)+f(n-1));颜书先生《“装错信封问题”的数学模型与求解》一文（见《数学通报》 2000 年第 6 期p.35 ），给出了该经典问题的一个模型和求解公式：编号为 1 ， 2 ，……， n 的 n个元素排成一列，若每个元素所处位置的序号都与它的编号不同，则称这个排列为 n个不同元素的一个错排。

记 n 个不同元素的错排总数为 f(n) ，则f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!]（ 1 ）本文从另一角度对这个问题进行一点讨论。

1. 一个简单的递推公式n 个不同元素的一个错排可由下述两个步骤完成：第一步，“错排” 1 号元素（将 1 号元素排在第 2 至第 n 个位置之一），有 n - 1种方法。

第二步，“错排”其余 n - 1 个元素，按如下顺序进行。

视第一步的结果，若 1号元素落在第 k 个位置，第二步就先把 k 号元素“错排”好， k 号元素的不同排法将导致两类不同的情况发生：（ 1 ） k 号元素排在第 1个位置，留下的n - 2 个元素在与它们的编号集相等的位置集上“错排”，有 f(n -2)种方法；（ 2 ） k 号元素不排第 1 个位置，这时可将第 1 个位置“看成”第 k个位置，于是形成（包括k 号元素在内的）n - 1 个元素的“错排”，有 f(n - 1)种方法。

据加法原理，完成第二步共有 f(n - 2)+f(n - 1) 种方法。

根据乘法原理， n 个不同元素的错排种数f(n) = (n-1)[f(n-2)+f(n-1)] (n>2) 。

（ 2 ）。

《全错位排列》研究一得理科实验班黄回銮徐博强刘益佳指导教师史立莉一、问题的引入课余，我们看排列组合问题时，常遇到受限元素，受限位置的简单问题。

如5个学生站成一排，甲不站在排头，乙不站在排尾有多少种不同排法，或上午5节课，数学、体育、政治、语文、化学。

体育不排在第一节，数学不排在最后一节，有多少种不同排法。

对这类问题的解决，我们已很熟练。

甲、乙或体育、数学是受限元素，排头、排尾或第一节，第五节是受限位置，用排除法较简明，只须不考虑受限元素，受限位置时，5个人站成一排有P55种不同排法。

要除去甲在排头的P44种不同排法，此时已含乙站在排尾的P33种排法，然后再排除乙站在排尾的P44种不同排法。

再加上重复排除的P33种不同排法，故可得出结论：不同的排法有 P55-2P44+P33=78种二、课题的提出5个元素有2个元素受限，有2个位置受限，我们考虑若将此题深化，若5个元素都受限，都分别受限在不同的位置上。

即5个编号分别为1、2、3、4、5的学生排成一排，1不站在1号位，2不站在2号位… 5不站在5号位，即每人均不站在与其编号相对应的位置上，我们称符合这样限制条件的排列为全错位排列，那这样的全错位排列有多少种？如果有n个受限元素，又该如何解呢？我们用排除法去解，很难得出正确结论，重复的情况很复杂，很难理出头绪，我们三人决心研究《全错位排列》排列数计算问题。

带着这个问题我们请教了指导老师史立莉。

三、课题研究史老师指导我们学习排列、组合数学归纳法及数列有关知识，鼓励我们大胆探究。

课余我们在一块探讨研究，用不完全归纳法试图找出规律，经推理演绎，初步得出一个不成熟的结论，供大家探讨，以期抛砖引玉。

四、构建命题命题：设n个编号为1、2、3、… i… j…n的不同元素a1、a2、a3…a i…a j…a n，站在一排，且每个元素均不站在与其编号相对应的位置，这样的全错位排列数为T n。

则 T n= (n-1) ( T n-1+T n-2)说明：T n-1, T n-2分别表示n-1个或n-2个不同元素全错位排列数。