装错信封问题即欧拉错排问题

有一道经典的数学问题：A和B每人持一门花色的牌（各13张），背面向上，并打乱。

然后每人出一张牌比较大小，共出13轮，试求这13轮中点数均不一样的概率。

这个问题看起来很简单，实则不容易。

为了解决这个问题，我们先看另外一个小问题——1，2，3，4四个数字，从左到右，第i个数不能放i（i=1,2,3,4），有几种放法？解析答案是9种：那么如果将4个数改成5个，6个……甚至n个，又应该怎么做呢？如果还是像刚才这样一个个的列出来，你会发现当数字增大时，情况会变得异常复杂，这种做法不再具备可行性，因此我们需要更加简便的方式——比如寻找递推公式。

对于n个元素的错排数，我们用D(n)表示。

第一步，把第1个元素放在其他某个位置（比如第k个），一共有n-1种放法；第二步，如果第k个元素放在第1个位置，那么有D(n-2)种放法；否则，有D(n-1)种放法。

综上，D(n) = (n-1) [D(n-2) + D(n-1)]。

特殊地，D(1) = 0，D(2) = 1。

然后，利用这个递推公式，可以得到n个元素的错排公式（具体推导过程略）：当n取2，3，4，5，6…的时候，D(n)的值分别为：1，2，9，44，265…错排公式可以进一步简化成：D(n) = [n!/e+0.5]，其中e是自然对数的底数，[ ]是向下取整符号。

这个问题叫做错排问题。

最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题。

利用上述简化公式，本文开头的问题可以轻松解决了。

所求概率为：P=[n!/e+0.5]/n！=[13!/e+0.5]/13！=0.36787944116…已经非常接近1/e（=0.36787944117…）。

接下来很自然的想到一个问题，P是否以其为极限呢？我们看到，从n=2起，随着n的增大，P似乎总是越来越接近1/e的：从直觉上也是这样——随着n的增大，+0.5与取整符号的作用越来越不明显，整个式子便越来越接近(n!/e)/n！=1/e。

[转载]伯努利装错信封问题原⽂地址：伯努利装错信封问题作者：NINO今天是我⼀次写博客，之所以开这个博客也是受学长的启发，希望借这个博客好好整理⼀下，以后这⾥会有⼀些我认为有帮助的题⽬，有⽔题也有难题（可能对我来说），废话不说，直接说今天这道题。

这道题本质上就是全错排，我想很久都没有头绪，肯能是受装苹果问题的印象，⼀开始我就认为这是⽤递归做，这题⼤概下⼀篇博⽂我就很整理⼀下，受其影响，我认为也应该会是先确定⼀位，再⼀次往下推；后来在群⾥听⼀些盆友的分析，知道了应该全排列，然后排除⼀些特殊的，怎么全牌呢？有两种思路，⼀个⼤概是放⼀个数组，这个数组表⽰⼀个数字，然后按数字的递增来表⽰全排列，另⼀种就是所谓的算法，显然我⼊了这个坑，，，虽然输出顺序有错，但细细想这个算法还是很赞的，事先声明，回溯法对此题并不受⽤，，，后来⾼中同学给了我⼀个代码，在他的指点下，我写了这个代码#includeint count=0;void print(int *,int);void fun(int *,int,int);int main(){int arry[7];int n;scanf("%d",&n);fun(arry,0,n-1);if(count%5==0)printf("s=%dn",count);elseprintf("ns=%dn",count);return 0;}//打印兼排除void print(int *a,int n){int i,j,flag=1;//排除⾮错位的for(i=0;i<=n;i++)if(*(a+i)==i+1){flag = 0;break;}//排除重复的for(i=0;i<=n;i++)for(j=i+1;j<=n;j++)if(*(a+i)==*(a+j)){flag = 0;break;}if(flag){count++;if(count%5!=0){for(i=0;iprintf("%d",*(a+i));printf("%d ",*(a+i));}else{for(i=0;iprintf("%d",*(a+i));printf("%dn",*(a+i));}}}void fun(int *a,int index,int n){if(index==n+1)print(a,n);else{for(*(a+index)=1;*(a+index)<=n+1;(*(a+index))++)fun(a,index+1,n);}}后来，⽼师给我⼀个算法，这个算法竟然不⽤递归，简直极好的，#includeint fun(int i,int n){int a[10],j,k;for(j=n-1;j>=0;j--){a[j]=i;i/=10;}for(j=0;j{if(a[j]==j+1) break;if(a[j]>n||a[j]==0) break;for(k=j+1;kif(a[j]==a[k]) break;if(k!=n) break;}if(j==n) return 1;else return 0;}int main(){int n,i,s=0,a=1;double b;scanf("%d",&n);b = n + n*0.1;for(i=0;ia*=10;b*=10;}for(i=a;iif(fun(i,n)==1){s++;if(s%5==0) printf("%dn",i);else printf("%d ",i);}if(s%5!=0) printf("n");printf("s=%dn",s);return 0;}其实百度知道也有这个代码，它的⽅法也和第⼀个异曲同⼯，可以说是加强版的；第⼆个思路很赞，但只能说是技巧，#include#includeint printed;void draw(int* a,int k){int i;for(i=0;i{printf("%d",a[i]);}printf("n");}void Settle(int*a,int iStep,int k){int i;for(i=0;iif(a[iStep-1]==a[i]) return;if(iStep==k){draw(a,k);printed++;}for(i=1;i<=k;i++){if(i==iStep+1) continue;a[iStep]=i;Settle(a,iStep+1,k);}}void main(){int* a;int k;scanf("%d",&k);a=(int*)calloc(k,sizeof(int));Settle(a,0,k);printf("s=%dn",printed);}总结：这种递归格式很值得推崇，代码的模块化显然也是这⼏个代码的共同的优势所在，。

可以秒杀的排列组合题型根据国考分数的统计分析可知数学运算得分率非常的低，大部分考生认为数学运算考试范围太广，难度大，甚至直接蒙。

数量关系考点看似杂乱，做题花的时间也很长，其实对于数学运算的每种题型都有解题技巧，甚至部分题型有相应的秒杀技巧。

在这里，向广大学员分享2017年国家公务员考试排列组合问题中秒杀题型，供广大考生复习参考。

对于排列组合问题，首先我们要认真审题，抓住问题的本质特征，再用对应的技巧解题．排列组合题型有以下2种题型可以秒杀！题型一：错位重排错位重排问题是一种比较难理解的复杂的数学模型问题，是伯努利和欧拉在错装信封时发现的，因此又叫做伯努利-欧拉装错信封问题。

表述为：编号是1、2、…、n 的n 封信，装入编号为1、2、…、n 的n 个信封，要求是每封信和信封的编号不同，问共有多少种方法? 答案：D(n)=[D(n-1)+D(n-2)]×(n-1)，其中D(1)=0，D(2)=1，根据递推公式算出D(n)。

【例】相邻的4个车位中停放了4辆不同的车，现将所有车开出后再重新停入这4个车位，要求所有车都不得停在原来的车位中，则一共有多少种不同的停放方式？A.9B.12C.14D.16【解析】方法一：根据错位排列的公式，直接得到4个车位的错位排列为种。

因此，本题选择A 选项。

方法二：假设A 、B 、C 、D 四辆车，停在一、二、三、四十个车位，最开始的排列为ABCD ，则A 车错位后有三种选择，假设A 车停在第二个车位，则B 车有三种选择，B 车选择后，C 、D 两车的停车方法只有一种，故总的方法数为3×3×1＝9种。

因此，本题选择A 选项。

备注：方法二比较复杂，如果记住方法和技巧就可以直接秒杀咯。

题型二：插空法特例题目特征：n 个相同的物品分给m 个人，每人至少分得1个物品，则共有多少种分配方法呢？49D我们的答案是：--11m n c备注：对于题型特征各位考生需要注意的有2点：相同的物品和每人至少分1个物品。

错排公式先来看⼀个问题：⼀个秘书打好4个封信和相应的四个信封，现在秘书将这四封信随机装⼊四个信封当中(每个信封装⼀封信)，问每个信封都被装⼊原来和⾃⼰不对应的信封的装法⼀共有多少种？答案是9种。

⾸先我们将这个⽂件进⾏进⼀步简化，假设1封信，1个信封：0种(不可能放错)2封信，2个信封：1种(交换)3封信，3个信封：2种(假设三个字母为ABC，则完全错排的组合为BCA和CAB)则可以对该题进⾏分类讨论，分别讨论4个信封中1,2,4个信封放对的情形1个信封放对: (41)∗2=8 （从4个信封中挑1个，其他3个错排）2个信封放对：(42)∗1=6 (从4个信封中挑2个，其他2个错排)4个信封放对：1总的排列为24种(4!),则剩下的排列数(24-8-6-1=9)就是答案现在我们将这个问题进⼀步推⼴，问，有n个信封和n封信，装法不变,仍然要求第i封信不能装到第i个信封当中(i = 1,2……,n)，问共有多少种装法？这个问题的原理，可以追溯到错排问题和错排公式。

错排问题，是组合数学中的问题之⼀。

考虑⼀个有n个元素的排列，若⼀个排列中所有的元素都不在⾃⼰原来的位置上，那么这样的排列就称为原排列的⼀个错排。

n个元素的错排数记为D(n)。

研究⼀个排列错排个数的问题，叫做错排问题或称为更列问题。

错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题。

这个问题有许多具体的版本，如在写信时将n封信装到n个不同的信封⾥，有多少种全部装错信封的情况?⼜⽐如四⼈各写⼀张贺年卡互相赠送，有多少种赠送⽅法?⾃⼰写的贺年卡不能送给⾃⼰，所以也是典型的错排问题。

解决⽅法1.利⽤递推公式解决我们记n个元素的错排数为D(n)，将数和数的位置的对应关系表⽰如下位置123...n数从n个数中任意挑⼀个数m，将m放在位置l上分两种情况讨论l放在m的位置上在这种情况下，数和位置的关系变为位置123...l...m...n数m ll，m的位置关系确定了，剩下1,2,3，……，l-1，l+1,……，m-1，m+1共n-2个数进⾏错排。

【数资】排列组合-隔板法、错位重排与环形排列（讲义）【例 1】（2014 四川）将 7 个大小相同的桔子分给 4 个小朋友，要求每个小朋友至少得到 1 个桔子，一共有几种分配方法（ ）？A.14B.18C.20D.22【例 2】（2019 湖北武汉事业单位）小明要将 30 个一模一样的玩具球放入 3 个不同颜色的桶里面，每个桶至少放 9 个玩具球，问一共有多少种不同的放法？ （ ）A.12B.11C.10D.9【例 3】（2013 年陕西）某领导要把 20 项任务分配给三个下属，每个下属至少要分得 3 项任务，则共有（ ）种不同的分配方式。

A.28B.36C.54D.78【例 4】（2014 广州）某办公室接到 15 份公文的处理任务，分配给甲、乙、 丙三名工作人员处理。

假如每名工作人员处理的公文份数不得少于 3 份，也不得多于 10 份，则共有多少种分配方式（ ）？A.15B.18C.21D.28【例 5】（2015 黑龙江）某单位共有 10 个进修的名额分到下属科室，每个科 室至少一个名额，若有 36 种不同分配方案，问该单位最多有多少个科室？A.7B.8C.9D.10【例 6】（2011 浙江）四位厨师聚餐时各做了一道拿手菜。

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

问共有几种不同的尝法（）？A.6 种B.9 种C.12 种D.15 种【例 7】（2014 北京）相邻的 4 个车位中停放了 4 辆不同的车，现将所有车开出后再重新停入这 4 个车位，要求所有车都不得停在原来的车位中，则一共有多少种不同的停放方式（）A.9B.12C.14D.16【例 8】（2015 山东）某单位从下属的 5 个科室各抽调了一名工作人员，交流到其他科室，如每个科室只能接收一个人的话，有多少种不同的人员安排方式？A.120B.78C.44D.24【例 9】（2017 年国考）某集团企业 5 个分公司分别派出 1 人去集团总部参加培训，培训后再将 5 人随机分配到这 5 个分公司，每个分公司只分配 1 人。

至少有一封信装对的概率基本事件数为n至少有一封装对的对立事件是没有一封信装对即n的全错位排列,也就是n!(1-1\/1!1\/2!1\/3!(-1)^n\/n!故P(至少有一封装对)=1-[n!(1-1\/1!1\/2!1\/3!(-1)^n\/n!n1\/1!1\/2!1\/3!(-1)^(n+1)\/n!我写了十封信，也写了十个信封，我随意把十张信纸装入十个信封，至少有一封装对的可能性有多大63.2%可以转化为著名的信封问题（错位排列）一共A(10,10)中排法只需求出没有1对装对的排法就是标准的错位排列了这是著名的信封问题,很多著名的数学家都研究过瑞士数学家欧拉按一般情况给出了一个递推公式：用A、B、C…表示写着n位友人名字的信封，a、b、c…表示n份相应的写好的信纸。

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

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

（2）b装入A、B之外的一个信封，这时的装信工作实际是把（除a之外的）份信纸b、c…装入（除B以外的）n－1个信封A、C…，显然这时装错的方法有f(n-1)种。

总之在a装入B的错误之下，共有错装法f(n-2)+f(n-1)种。

a装入C，装入D…的n－2种错误之下，同样都有f(n-2)+f(n-1)种错装法，因此:f(n)=(n-1){f(n-1)+f(n-2)}这是递推公式，令n＝1、2、3、.10f(1)=0 f(2)=1 f(3)=2 f(4)=9 f(5)=44 f(6)=265 f(7)=854f(8)=14833 f(9)=133496 f(10)=1334961所以概率=1-f(10)\/A(10,10)=63.2%另外一种算法就是用容斥原理直接算用A1,A2,…,An表示以下事件：Ak表示第k封信放在本来的信封上。

求出A1∪A2∪…∪An的概率然后用1减去它就是所需答案了那么，根据容斥原理，有：P(A1∪A2∪…∪An)＝P(A1)+P(A2)+…+P(An)-(P(A1∩A2)+P(A1∩A3)+…+P(A(n-1)∩An))(注意：求和取遍所有不同的Ai∩Aj)+(P(A1∩A2∩A3)+P(A1∩A2∩A4)+…+P(A(n-2)∩P(A(n-1))∩P(An)))(注意：求和取遍所有不同的Ai∩Aj∩Ak)＋…+(-1)^(n-1)P(A1∩A2∩…∩An)(n-1)!n\/n!(n-2)!n!C_n^2+(n-3)!n!C_n^3+…+(-1)^(n-1)\/n!1-1\/21\/3(-1)^(n-1)\/n即至少有一对装对的概率就是1-1\/21\/3(-1)^(n-1)\/n这里取n=10 故概率=63.2%参考资料http:\/\/\/question\/6099980.htmlhttp:\/\/\/question\/30469010.html?si=4 概率题。

错排问题
错排问题是组合数学中的问题之⼀。

考虑⼀个有n个元素的排列，若⼀个排列中所有的元素都不在⾃⼰原来的位置上，那么这样的排列就称为原排列的⼀个错排。

n个元素的错排数记为D n。

研究⼀个排列错排个数的问题，叫做错排问题或称为更列问题。

最早研究错排问题的是尼古拉·伯努利和欧拉，因此历史上也称为伯努利-欧拉的装错信封的问题。

这个问题有许多具体的版本，如在写信时将n封信装到n个不同的信封⾥，有多少种全部装错信封的情况？⼜⽐如四⼈各写⼀张贺年卡互相赠送，有多少种赠送⽅法？⾃⼰写的贺年卡不能送给⾃⼰，所以也是典型的错排问题。

对于D n，第⼀个元素不能在第⼀个位置上故有n−1种类情况。

假设第⼀个元素在k的位置上，有两种情况
第k个元素在第⼀个上⾯，则此时的情况为n−2个元素的错排
第k个元素不在第⼀个上⾯，则此时的情况为剩下的n−1个元素的错排
所以我们得到了⼀个递推公式，D n=(n−1)×(D n−1+D n−2),(n>2)
常见的⼏个值
D0=0D6=265
D1=0D7=1854
D2=1D8=14833
D3=2D9=133496
D4=9D10=1334961
D5=44D11=14684570
Processing math: 100%。

在事业单位考试中，排列组合是一个常考题型。

一般情况下我省事业单位考察形式比较多样，出题基础但不失创意。

环形排列、隔板模型、错位重排等都是排列组合题型中的经典模型，出题可能极大，咱们同学如果考前没有接触过，在考场才研究这些模型特点是很浪费时间的，但如果大家提前了解了这些题型所涉及的原理及其结论，在考试时能准确的区分题型，那对于这一类题目，就是简单地得分了。

接下来就给大家介绍一下错位重排的结论。

什么是错位重排?所谓的错位重排是指一种比较难理解的复杂数学模型，是伯努利和欧拉在错装信封时发现的，因此又称装错信封问题。

它的基本表述为：编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法?如：3个信封装三封信，都装错了的方法有多少种?假设三个信封为A、B、C，三封信为a、b、c，则根据枚举法，都装错的方法有：信封A B C信b c a、c a b共计有2种方法。

再如：4个信封装三封信，都装错的方法有多少种?假设四个信封为A、B、C、D，四封信为a、b、c、d，则根据枚举法，都装错的方法有：信封A B C D信b c d ab d a cb a d cc ad bc d a bc d b ad a b cd c b ad c a b共计有9种方法。

对这类问题有个固定的递推公式，记n封信的错位重排数为Dn，则D1=0，D2=1，Dn=(n-1)(Dn-2+Dn-1) (n>2)我们只需记住Dn的前几项:D1=0，D2=1，D3=2，D4=9，D5=44。

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

错位重排的题干特征还是非常明显的，比如四个大厨烧了四道菜，每个大厨都不吃自己菜的方式有多少种，这就是4个元素的错位重排;再比如有5对夫妻去跳舞，相互交换舞伴，舞伴不是自己配偶的方式有多少种，就是5个元素的错位重排。

考试中常见的就是3—5个元素的错位重排，大家把这些结论记忆清楚，可以快速解题。

排列组合特殊题型之错位重排中公教育研究与辅导专家于岩错位重排问题是排列组合中的一种特殊题型，如果不知道错位重排的关系，在遇到这类型的题目时就会很头疼，无从下手。

今天中公教育研究与辅导专家为大家带来了解决错位重排问题方法，我们一起来看一下。

错位重排问题也叫装错信封问题，比如编号为1、2、……、n的n封信，装入编号为1、2、……、n的n个信封，要求每封信和信封的编号不同，有多少种装法？对于这种问题，有一个固定的递推公式，记n封信的错位重排数为Dn：Dn =(n-1)×(Dn-2 +Dn-1)，其中D1=0，D2=1。

简单阐述下公式的推导过程，先让编号为1的信封去装信，不能选编号1的信，只能从剩下的n-1封信中去选，假设信封1选了编号为2的信，下面让编号为2的信封再去选择的话，如果编号为2的信封不选编号1的信，那么加上其他的信封，可以理解为是n-1个信封的错位重排，记作Dn-1，如果编号为2的信封选择了编号为1的信，那么剩下的就是n-2个信封的错位重排，记作Dn-2，故为上面所列式子。

具体把错位重排的关系应用到解题时，我们需要记清楚一些小元素对应的错位重排数，比如D2=1，D3=2，D4=9，D5=44，D6=265等，如果记不清楚，也可以根据刚才所给的公式推导出来。

例1.某校心理健康日，为拉近同学们彼此心灵之间的距离，设置了“抱抱团”游戏。

该游戏要求10人面对面而站，相对而站的两人彼此是朋友。

然后要求其中一排的人去拥抱对面的人，但不能拥抱自己的朋友，也不能出现拥抱同一个人，则共有多少种不同的拥抱方法？A.60B.54C.38D.44【中公解析】选D，题目可以理解为把两排的人在同一方向按顺序编号 1、2、3、4、5，其中一排的人去拥抱另一排的一个人，但不能拥抱与自己序号相同的人，且不能拥抱同一人，则共有多少种不同的拥抱方法？就是找5个元素对应的错位重排数的，由错位重排前面给的公式可得，D5=44，故选D。

发表于浙江师大《中学教研∙数学》2011（07）从竞赛到高考班的装错信笺题及变式题探究●甘大旺（北仑明港中学浙江宁波315806）瑞士数学家尼•伯努利(Danil Bemoulli ，1700~1782)提出了装错信笺问题——某人写了n （∈N +）封不同的信，并在n 个信封上写下对应的地址，问把所有信笺全部装错的方法共有多少种？后来，瑞士数学家欧拉(Euler ，1707~1783)认为此题是“组合理论的一个妙题”，并运用递推数列{}n x 独立地解决了这道妙题，求出的方法种数用阶乘表示为11111(1)(1)!0!1!2!3!(1)!!n n n x n n n -⎡⎤--=⋅-+-+++⎢⎥-⎣⎦ ．(#)欧拉解法的关键是找出递推数列的递推式))(1(12n n n x x n x +-=++、难点是后续的求出通项．下面另辟蹊径，运用容斥原理来验证(#)式．证明：当正整数2n ≥时，将这n 封信笺任意装入这n 个信封，不管装对装错，笼统有!n 种方法．其中，至少有1封信笺恰好正确装入信封的任意装法有)!1(1-⋅n n C 种，至少有2封信笺恰好正确装入信封的任意装法有)!2(2-⋅n nC 种，至少有3封信笺恰好正确装入信封的任意装法共有)!3(3-⋅n nC 种，┅，至少有1-n 封信笺恰好正确装入信封的装法共有!11⋅-n n C 种，所有n 封信笺都正确装入信封的装法共有n nC 种．根据容斥原理知，符合题意的投放信笺方法共有123!(1)!(2)!(3)!n x n C n C n C n nn n=-⋅-+⋅--⋅-n n C n n n C n )1(!111)1(-+⋅---++!!)1()!1(!)1(!3!!2!!1!!1n n n n n n n n nn -+--++-+-=- ⎥⎥⎦⎤⎢⎢⎣⎡-+--++-+-⋅=-!)1()!1()1(!31!21!11!01!1n n n n n 种．当1n =时，11100!1!x ==-适合上式.。

全错位排列计算错位全排列问题什么是错位全排列问题？其实很简单，在生活中可能都会遇到：“装错信封问题”是由当时最有名的数学家约翰·伯努利(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)! 种装法。

数学知识--错排公式错排公式核⼼递推公式：D(n) = (n-1) [D(n-2) + D(n-1)]特殊地，D(1) = 0, D(2) = 1.问题: ⼗本不同的书放在书架上。

现重新摆放，使每本书都不在原来放的位置。

有⼏种摆法?这个问题推⼴⼀下，就是错排问题，是组合数学中的问题之⼀。

考虑⼀个有n个元素的排列，若⼀个排列中所有的元素都不在⾃⼰原来的位置上，那么这样的排列就称为原排列的⼀个错排。

n个元素的错排数记为D(n)。

研究⼀个排列错排个数的问题，叫做错排问题或称为更列问题。

错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题。

这个问题有许多具体的版本，如在写信时将n 封信装到n个不同的信封⾥，有多少种全部装错信封的情况?⼜⽐如四⼈各写⼀张贺年卡互相赠送，有多少种赠送⽅法?⾃⼰写的贺年卡不能送给⾃⼰，所以也是典型的错排问题。

问题: ⼗本不同的书放在书架上。

现重新摆放，使每本书都不在原来放的位置。

有⼏种摆法?这个问题推⼴⼀下，就是错排问题，是组合数学中的问题之⼀。

考虑⼀个有n个元素的排列，若⼀个排列中所有的元素都不在⾃⼰原来的位置上，那么这样的排列就称为原排列的⼀个错排。

n个元素的错排数记为D(n)。

研究⼀个排列错排个数的问题，叫做错排问题或称为更列问题。

错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题。

这个问题有许多具体的版本，如在写信时将n 封信装到n个不同的信封⾥，有多少种全部装错信封的情况?⼜⽐如四⼈各写⼀张贺年卡互相赠送，有多少种赠送⽅法?⾃⼰写的贺年卡不能送给⾃⼰，所以也是典型的错排问题。

递推的推导错排公式当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的⽅法数⽤D(n)表⽰，那么D(n-1)就表⽰n-1个编号元素放在n-1个编号位置，各不对应的⽅法数，其它类推.第⼀步，把第n个元素放在⼀个位置，⽐如位置k，⼀共有n-1种⽅法;第⼆步，放编号为k的元素，这时有两种情况:⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种⽅法;⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种⽅法;综上得到D(n) = (n-1) [D(n-2) + D(n-1)]特殊地，D(1) = 0, D(2) = 1.下⾯通过这个递推关系推导:为⽅便起见，设D(k) = k! N(k), k = 1, 2, …, n,则N(1) = 0, N(2) = 1/2.n ≥ 3时，n! N(n) = (n-1) (n-1)! N(n-1) + (n-1)! N(n-2)即 nN(n) = (n-1) N(n-1) + N(n-2)于是有N(n) - N(n-1) = - [N(n-1) - N(n-2)] / n = (-1/n) [-1/(n-1)] [-1/(n-2)]…(-1/3) [N(2) - N(1)] = (-1)^n / n!.因此N(n-1) - N(n-2) = (-1)^(n-1) / (n-1)!,N(2) - N(1) = (-1)^2 / 2!.相加，可得N(n) = (-1)^2/2! + … + (-1)^(n-1) / (n-1)! + (-1)^n/n!因此D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].此即错排公式。

带空位的错排问题孙礼滨2015.12.09 先看以下问题：m个座位有n个人就坐（m≥n＞0为自然数，或有空座位），现换位置，要求任何人不能留在原来座位。

问共有多少种换法？本问题看似简单，实则难解。

咋一看，是排列组合问题，但用乘法原理和加法原理都无从入手。

先别急，先看m=n的情况，此时该问题被欧拉称为装错信封的问题：n封信发往n个不同地方，问全装错信的可能数目。

同时也被称为错排问题。

这问题自然难不倒数论大师，他自己得到了一个简洁的递推公式。

这里记错装数为F（n，n），括号里第一个n为座位数，第一个n为人数。

现从这种角度来解决该问题。

先从简单的m=n情况考虑起。

此时无论怎么换，总得先由某一个人（设为甲）让出位子，并去挤占他人（设为乙）的一个位子。

这样就出现了两种情况：甲乙对调位子和没对调位子。

对调位子的换法总数为（n-1）F（n-2,n-2），没对调位子的换法总数为（n-1）F（n-1,n-1）。

对调位子的算法易于理解。

可这样来理解没对调位子的情况：甲与乙对调位子共有（n-1）种换法；这时乙已坐到甲的位子上；然后除去甲不考虑，把包括乙在内的（n-1）个人和位子互换座位，互换完成后乙又离开了原来甲的座位，也即乙没有和甲对换座位。

据此，得出简捷的迭代解如下：（1）F（1，1）＝0，F（2，2）＝1（2）F（n，n）＝（n-1）（F（n-1,n-1）+ F（n-2,n-2））此公式正是欧拉得到的递推公式。

把F（1，1）至F（n，n）列出n个等式，并不断地连乘错位化简后的结果与用容斥原理得到的结果相同。

本处直接引用他人成果：F（n，n）=n！（1-1/1！+1/2！-1/3！+…+（-1）n+1/n！）。

依据斯特林公式（Stirling's approximation）：，并逆用超越数e的幂级数展开式，可以得到非常精确的近似速算公式：F（n，n）=[n!/e+0.5] ，其中e是自然对数的底，[x]为x的整数部分。

伯努利—欧拉关于装错信封问题的另一种解法
高世杰
【期刊名称】《数学教学通讯：教师阅读》
【年(卷),期】1996(000)006
【摘要】问题是这样的:某人写了 n 封信,并且在 n个信封上写下了对应的地址,把所有的信笺装错信封的情况,共有多少种?这个问题可以这样概括理解:求 n 个元素的排列,要求在排列中没有一个元素处于它应当占有的位置.N.伯努力利和欧拉解法巧妙,格外引人入胜.
【总页数】2页(P22-23)
【作者】高世杰
【作者单位】扎兰屯师范学校 162650
【正文语种】中文
【相关文献】
1.欧拉—伯努利梁在移动载荷作用下的等效方法 [J], 汪宏斌;王志浩
2.欧拉-伯努利梁单元刚度矩阵推导 [J], 张军锋;尹会娜;李杰;陈淮
3.基于欧拉·伯努利梁的自动控制原理案例教学探索与实践 [J], 钟佳岐;蔡林沁
4.基于模态应变能与频率融合方法的功能梯度欧拉伯努利梁损伤识别研究 [J], 梁福安;黄君;黄立新
5.基于模态应变能与频率融合方法的功能梯度欧拉伯努利梁损伤识别研究 [J], 梁福安;黄君;黄立新
因版权原因，仅展示原文概要，查看原文内容请购买。