装错信封问题

国家公务员：排列组合之错位排序排列组合的数量题目当中，有一些技巧我们常常会用到，今天我们就一起来看一下排列组合问题中常用的方法——错位排序。

我们来讨论一个问题：这是一个很经典的数学问题：有一个人写了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个科室各抽调了一名工作人员，交流到其他科室，如每个科室只能接收一个人的话，有多少种不同的人员安排方式？（）A.120种B.78种C.44种D.24种【解析】分析题干可知，本题考查5人的错位排序，根据错位排列个数关系D5=44。

装错信封问题即欧拉错排问题
中“信封装错问题”的数学模型及解法；
有人写了N封信，同时写了N个信封，然后任意把信放进信封里。

问:每个字母被错误地装入时有多少种情况？排列、组合和简单计数问题。

计算问题。

让我们假设n个字母是A，B，c。

第一个字母A 有(n-1)种子放置方法。

假设A被放置在对应于B的包络中，B具有(n-1)种子放置方法；通过类比，分析下列字母的位置，然后通过计算排列公式得到答案。

解决方法:如果N个字母是A，B，c…，那么第一个字母A有(N-1)放置方法，并且假设A被放置在对应于B的信封中，那么B有(N-1)放置方法；假设b被放置在对应于c的包络中，c具有(n-2)种子放置方法；假设C被放置在对应于D的包络中，D具有(n-3)种子放置方法；...等等，有一种方法可以释放字母n；还有(n-1) (n-1) (n-2) (n-3)...1 = (n-1) (n-1)！因此，每个字母都被错误地加载(n-1) (n-1)！备注:本主题检查逐步计数原则的应用，并注意使用假设方法解决问题。

著名数学家莱昂哈德·欧拉(1707-1783)将“错放包络问题”的两个特例称为“组合数论中的一个奇n*1/n！)证明:
设置总排列t1，t2，...，TN = 1，2，...，n为I，并将ti=i设置为Ai(1。

利用错排公式求解装错信封问题【问题背景】18世纪数学家约翰·伯努利(Johann Bernoulli ，1667—1748)的儿子丹尼尔·伯努利(Danid Bernoulli ，1700—1782)提出来这样一个问题：一个人写了n 封信，并且写了n 个对应的信封，这个人随机将这n 封信分别装入这n 个信封，问：都装错的情况有多少种?后来著名数学家欧拉对此产生浓厚兴趣，并称之为“组合理论的一个妙题”，并且给出了“装错信封问题”的一劳永逸的答案：设n 个信封都装错的情况数为n D ，那么11111(1)(1)!0!1!2!3!(1)!!n n n D n n n −⎡⎤−−=⋅−+−+⋅⋅⋅++⎢⎥−⎣⎦. 特别说明，以上公式是通过数列递推得来，为了简化约分运算，我们可以将上式化简为2311(1)(1)n n n n n n n n D A A A −−−=−+⋅⋅⋅+−+−.在这里，我们可以记忆一些常见的结果：123450,1,2,9,44D D D D D =====.【经典例题】重新排列1，2，3，4，5，6，7，8.（1）使得偶数在原来的位置上，而奇数不在原来的位置上，有多少种不同的排法？（2）使得偶数在奇数的位置上，而奇数在偶数的位置上，有多少种不同的排法？（3）使得偶数在偶数位置上，但都不在原来的位置上，奇数在奇数的位置上，但也都不在原来的位置上，有多少种不同的排法？（4）如果要有数在原来的位置上，有多少种不同的排法？（5）如果只有4个数在原来的位置上，有多少种不同的排法？（6）如果至少有4个数在原来的位置上，有多少种不同的排法？（7）使得偶数在偶数的位置上，但恰有两个数不在原来的位置上，奇数在奇数的位置上，但恰有两个数不在原来位置上，有多少种不同的排法？（8）使得偶数在偶数的位置上，且至少有两个数不在原来的位置上；奇数在奇数的位置上，也至少有两个数不在原来的位置上，有多少种不同的排法？解析：（1）本题实质上是“装错信封问题”，49D =.（2）偶数在奇数位置上44A ，奇数在偶数位置上44A ，4444576A A ⋅=.（3）4481D D ⋅=.（4）正难则反，对8个数进行全排列88A ，减去没有数在原来的位置上8D ，88825487A D −=.（5）先从8个数中选择4个数在原来的位置上，剩余4个数不在原来的位置上，用分步乘法计数原理：484630C D ⋅=.（6）分类求解：45688483828771C D C D C D C ⋅+⋅+⋅+=.（7）224242()()36C D C D ⋅⋅⋅=.（8）22424424()()225C D D C D D ⋅+⋅⋅+=.上式中至少有2个数不在原来的位置上，包括恰有2个数不在原来的位置上和4个数都不在原来的位置上两种情况.【小结】“问题是数学的心脏.”思考问题，解决问题，才能促进数学素养的形成.。

“装错信封问题”的数学模型与求解某人写了n封信，同时写了n个信封，然后将信任意装入信封，问：每封信都装错的情况有多少种？排列、组合及简单计数问题．计算题．设这n封信依次为a、b、c…，第1封信a有（n﹣1）种放法，假设a放到了b对应的信封里，则b有（n﹣1）种放法；依此类推，分析随后的几封信的放法，进而由排列数公式计算可得答案．解：设这n封信依次为a、b、c…，则第1封信a有（n﹣1）种放法，假设a放到了b对应的信封里，则b有（n﹣1）种放法；假设b放到了c对应的信封里，则c有（n﹣2）种放法；假设c放到了d对应的信封里，则d有（n﹣3）种放法；…依此类推，第n封信有1种放法；则共有（n﹣1）（n﹣1）（n﹣2）（n﹣3）…1=（n﹣1）（n﹣1）!，故每封信都装错的情况有（n﹣1）（n﹣1）!种．点评：本题考查分步计数原理的运用，解题中注意用假设的方法．被著名数学家欧拉(Leonhard Euler，1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli，1700－1782)提出来的，大意如下：一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？公式证明n个相异的元素排成一排a1,a2,...,an,且ai(i=1,2,...,n)不在第i位的排列数为n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!)证明：设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)同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡．则四张贺年卡的不同分配方式有A．6种B．9种C．11种D．23种(1993年全国高考题理科17题)2)有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？上述两个问题，实质上是完全一样的．是被著名数学家欧拉(Leonhard Euler，1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli，1700－1782)提出来的，大意如下：一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？2建立数学模型“装错信封问题”及两个特例，其实就是n个不同元素的一类特殊排列问题，本文试就给出这类问题的数学模型及求解公式．为方便，我们先把n个不同的元素及相应的位置都编上序号1，2，…，n，并且约定：在n个不同元素的排列中1°若编号为i(i=1，2，…，n)的元素排在第i个位置，则称元素i在原位；否则称元素i不在原位．2°若所有的元素都不在原位，则称这种排列为n个不同元素的一个错排(若每个元素都在原位则称为序排)．按照上面约定，“装错信封问题”即为n个不同元素的错排问题，则可构建“装错信封问题”的数学模型为在n个不同元素的全排列中，有多少种不同的错排？3 模型求解应用集合中的容斥原理，我们就可得到“装错信封问题”的数学模型的求解公式．设I表示n个不同元素的全排列的集合A i(i=1，2，…，n)为元素i在原位的排列的集合．A i∩A j(1≤i＜j≤n)为元素i与j在原位的排列的集合．…………A1∩A2∩…∩A n为n个元素的序排的集合．则它们的排列数(即各个集合中元素的个数)分别为|I|=n！|A i|=(n－1)！|A i∩A j|=(n－2)！…………|A1∩A2∩…∩A n|=(n－n)！=0！所以，根据容斥原理即得“装错信封问题”的数学模型的求解公式(即n个不同元素的错排数)为4 应用举例一个元素的错排数显然为0，二个不同元素的错排数为1，三个不同元素的错排数为2，均可由公式验证，由公式还可求得四个不同元素的错排数为五个不同元素的错排数为则本文开头的问题1)共有9种不同的分配方式，故选(B)．问题2)共有44种不同的戴法，下面再举几例说明公式的应用．例1 (1991年上海高考题)设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为[ ] A．20种B．30种C．60种D．120种解本题实质上是三个元素的错排问题，但由于题中未指明是哪三个元素进行的错排，故本题可分两步求解．第二步，对已选出的三个元素进行错排，有2种．例2某省决定对所辖8个城市的党政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务．问共有多少种不同的干部调配方案？解实质上本题即为8个不同元素的错排问题，一种干部调配方法对应于8个不同元素的一个错排．故由公式可求得不同的干部调配方案数为-- 参考答案：瑞士数学家欧拉按一般情况给出了一个递推公式：用Ａ、Ｂ、Ｃ……表示写着ｎ位友人名字的信封，ａ、ｂ、ｃ……表示ｎ份相应的写好的信纸。

全装错信问题即全错位排列问题及拓展——龙城老欧全装错信问题又称全错位排列问题，最早由瑞士数学家伯努利提出，最后由伯努利与他的学生欧拉讨论解决，这个问题就是——我们将编号是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]种方法），这样就整体上也都是全错位了。

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

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

错位重排问题也叫装错信封问题，比如编号为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。

关于错排问题的递推公式的一点分析作者：冯弋舟来源：《读与写·下旬刊》2018年第01期中图分类号：G633.6文献标识码：B文章编号：1672-1578（2018）01-0166-011.背景排列组合里有一道题，叫错排问题（staggered formula）。

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

这个问题如下：写了n封信，装到n个不同的信封，每封信和信封都不匹配，问全部装错的可能性有多少种。

错排问题的标准定义是：集合{1，2，…，n}的一个排列i1i2，…in }，满足条件i j≠j（1≤ j≤ n），即没一个数字在它自然顺序位置的全排列。

问这样的排列有多少个。

n个自然数的全部错排数用Dn表示。

2.问题的提出习题解答上在给出Dn的递推公式时，这样的：假设i1的位置放置2（还有 3.4..n 等n-1种可能），剩下1，3，4，…n往i2，i3..in位置上放，这时错排数设为An，那么Dn=（n-1）An。

An的计算又分为两种情况：（1） 1不放在第2个位置i2上，剩下n-1个数的错排数为Dn-1。

（2）1放在第2个位置i2上，剩下的n-2个数的进行错排，错排数为Dn-2。

所以An=Dn-1+Dn-2，所以最后总Dn=（n-1）（Dn-1+Dn-2）。

很多刚学习错排的同学会误以为Dn-1包括Dn-2，为什么还要加Dn-2呢？本文将分析这个问题。

3.问题分析下面以n=4（数字小好分析）为例子分析：2放1位置时错排列为 2143、2341、2413，放1位置的还有3和4 ，所有共有3*3=9种错排。

那么2放1位置后的剩下3个数的全错排数（图1），是否包含 2放1位置和1放2位置后的错排数（图2）呢？把2放1位置后全错排D3，是把数字1、3、4排到第2、3、4三个位置上的错排，那么数字1、3、4 排到第2、3、4位置的错排怎么排呢？现在把数字1、3、4改为数字"2"、3、4 在第2、3、4位置上错排，"2"（其实是1）不许排在位置2上，错排数为D3。

欧拉装错信封问题“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli ，1667－1748)的儿子丹尼尔·伯努利(DanidBernoulli ，1700－1782)提出来的，大意如下： 一个人写了n 封不同的信及相应的n 个不同的信封，他把这n 封信都装错了信封，问都装错信封的装法有多少种？1. 一个人写了4封不同的信及相应的4个不同的信封，他把这4封信都装错了信封，问都装错信封的装法有多少种？ 【解析】分为两步（1）首先让A 信选信封，有3种选择，假设A 选择了b 信封（2）接着让B 信选信封，选择情况可分为两大类○1B 信选择了a 信封（A 信与B 信相互选择对方的信封）剩下了C 信、D 信去选择c 信封、d 信封，相当于是2封不同的信装入对应的2个不同的信封，有2A 种装法。

○2B 信不选择a 信封 dD 信封信cbaC B A dD 信封信cbaC B A相当于3封信装入对应的3个不同的信封（因为B 信不选择a 信封，所以可以将a 信封看成b 信封），有3A 种装法。

综上，由乘法原理可得：()()()432=4-13219A A A +=⨯+=（种）装法。

同理我们可以总结出递推公式：()()12=-1n n n A n A A --+（拓展：装错信封求解公式()111!1-11!2!!nn A n n ⎛⎫=-+++⋅⎪⎝⎭）2. 同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡．则四张贺年卡的不同分配方式有 _____种 (1993年全国高考题理科17题)3. 有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？××dD 信封信cb a(b )C B A。

全错位排列以前接触过这样的题⽬，但是现在稍微系统点⾸先看⼀下百度百科对全错位排列的解释：基本简介全错位排列：即被著名数学家(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)种错装法。

伯努利信封问题解法题目：探寻伯努利信封问题的解法导言：伯努利信封问题是20世纪50年代流行起来的一个有趣的数学难题，让我们一起来探索这个问题的解法。

在这篇文章中，我们将从简单的示例开始，逐步深入研究，最终得出一个高质量的解决方案。

希望通过本文的阅读，您能对伯努利信封问题有更全面、深入和灵活的理解。

1. 什么是伯努利信封问题？伯努利信封问题源于瑞士数学家尼古拉斯·伯努利于1728年提出的一个问题。

问题是：假设有若干封信放在不同大小的信封中，每封信只能放在一个信封中。

如果我们随机地将信装入信封，那么平均来说，有多大的可能性每个信封都被错误地装入？2. 简单的解法和思考在最简单的情况下，假设只有两个信封和两封信，我们可以尝试所有可能的组合：将A信装在A信封中，将B信装在B信封中以及将A信装在B信封中，将B信装在A信封中。

显然，只有一种情况是正确的，即将A信装在A信封中，所以在这种情况下，有1/2的可能性每个信封都被错误地装入。

3. 更复杂的情况和概率计算当信封数量和信件数量增多时，情况变得更加复杂。

此时，我们可以采用概率论的方法来计算每个信封装入错误的概率。

假设有N个信封和N封信，我们可以推导出以下等式来计算错误概率P：P = 1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n * 1/n!其中，n为信件数量，n!表示n的阶乘。

该等式被称为泰勒级数展开，并且逐渐趋近于一个非常接近1/e的值，其中e是自然对数的底数。

4. 高阶解法和数学证明除了通过概率计算来得出近似解的方法，数学家们还为伯努利信封问题提供了一种高阶解法。

他们通过使用Stirling公式，对泰勒级数展开进行了近似。

这种解法不仅提供了近似的答案，还能给出更精确的数值结果。

5. 个人观点和总结通过对伯努利信封问题的探索，我们可以看到数学在解决实际问题中的重要性。

无论是通过简单的思考还是复杂的数学推导，我们能够逐步深入地理解问题，并得出一些有趣的结论。

【数资】排列组合-隔板法、错位重排与环形排列（讲义）【例 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 人。

"装错信封问题"是一个经典的组合数学问题，也可以通过递归或者动态规划来解决。

在C语言中，我们可以使用循环和条件判断来实现这个问题的解决方案。

假设有n个信封和n个信件，每个信件都装入与其编号相同的信封中，现在要将第i个信件放入第i个信封中（i=1,2,...,n），但由于某种原因，第i个信件被放入了第i+1个信封中（i=1,2,...,n-1），我们需要找出一种方法，将所有信件都放回正确的信封中。

我们可以用一个长度为n的数组来记录每个信件被放入哪个信封中，例如，arr[i] = j表示第i个信件被放入第j个信封中。

我们可以使用一个循环来遍历所有信件，对于每个信件，我们检查它被放入哪个信封中，如果该信件被放入了下一个信封中，我们就将它交换回正确的信封中，直到所有信件都被正确地放回了它们原来的信封中。

以下是C语言代码实现：c#include <stdio.h>int main() {int n, i, j, count = 0;printf("请输入信封数量：");scanf("%d", &n);int *arr = (int *)malloc(n * sizeof(int));printf("请输入每个信件被放入哪个信封中（1~%d）：", n);for (i = 0; i < n; i++) {scanf("%d", &arr[i]);}for (i = 0; i < n; i++) {if (arr[i] == i + 1) {continue;}for (j = i + 1; j < n; j++) {if (arr[j] == i + 1) {count++;arr[i] = arr[j];arr[j] = i + 1;break;}}}printf("需要交换%d次才能将所有信件放回正确的信封中。

伯努利-欧拉错装信封问题设有变号为1~n 个不同的信封和编号为1~n 封不同的信，现将n 封信装入n 个信封内，则全部装错的有多少种情况？（信封的编号与信的编号不同）假设n 封信全装错的不同情况有a n 种，则a 1=0，a 2=1，a 3=2；首先装第1封信，有n －1种方法，不妨设第1封信装入第k 号信封，第二步，装第k 封信，分以下两种情况：当第k 封信恰装入第1号信封，则剩下n －2个信封和n －2封信错装，不同的方法有a n －2种，当第k 封信没有装入第1号信封时，不妨将第1号信封视作第k 个信封，则问题转化为n －1封信错装，不同的错装方式为a n －1.因此a n =(n －1)(a n －1+a n －2)，n ≥3接下来只要求出通项公式即可.令b n =a n n !，则a n =n !b n ，则n !b n =(n －1)(n －1)!b n －1＋(n －1)(n －2)!b n －2 即n !b n =(n －1)b n －1＋b n －2，整理得n (b n －b n －1)=－(b n －1－b n －2)令c n =b n －b n －1，则c n c n －1＝－1n ，c 2=b 2－b 1=12， 由累乘法，求得c n c 2＝(－1)n ·13·4·5·…·n，∴c n =(－1)n ·1n !， 即b n －b n －1=(－1)n ·1n !，由累加法，得b n －b 1=12!－13!＋14!＋…＋(－1)n ·1n !， 又因为b 1=a 1=0，所以b n =12!－13!＋14!＋…＋(－1)n ·1n !， 即a n n !=12!－13!＋14!＋…＋(－1)n ·1n !， a n =n !⎝ ⎛⎭⎪⎫1－11!＋12!－13!＋…＋(－1)n ·1n !.。

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

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

错位重排问题也叫装错信封问题，比如编号为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。

考试难点攻克之错位重排随着我们备考的逐渐深入，很多考生对于数量关系这部分的内容还是感觉难以下手，那么面对这种情况，就需要我们的考生对于我们数量中一些常考的有明显题型特征且解题思路清晰明了的一些题型进行重点攻克。

比如我们今天要给大家讲到的排列组合问题中常见的错位重拍问题。

一、题型特征错位重排问题是一种比较复杂的数学模型，其实就是著名的伯努利一欧拉的装错信封问题，我们可以形象地叙述如下:“某人写了n封信,并在n个信封上写下了对应的地址和收信人姓名,把所有的信笺装错信封的情况共有多少种。

”为了便于理解题目，我们不妨先假设n=3，并且将三个信封分别用大写字母ABC来代替，将三封信用小写字面abc来代替，题目的要求其实就是将信封和信件两两配对，但是A-a，B-b，C-c不能配对，这样的题目就叫做错位重排问题。

二、解题要点错位重排作为排列组合的一种模型，原理很复杂，但是应用上面很简单。

解决此类问题最直接的就是记住公式：一个元素错位重排的时候情况数为0（因为只有一个，不可能排错），两个元素错位重排情况为1，三个为2，四个为9，五个为44…从这里不难看出从第四项开始为前面两数和的倍数，也就是说，若将错位重排数记为D n，则：D n=（n-1）（D n-2+D n-1），（D1=0，D2=1，D3=2）三、重点题型掌握了错位重排的公式，我们一起来看几道题目看看在实战中错位重排问题如何解决。

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

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

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

解析：4位厨师的错位重排数为D4=9，即有9种不同的尝法。

除了此类直接应用公式的题型之外，错位重排问题还包括一类不完全错位重排问题，比如下面这道例题：例2.五个装药用的瓶子都贴有标签,其中恰好贴错了三个,那么贴错的可能情况有多少种?A.9种B.12种C.18种D.20种【答案】D。

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

考虑⼀个有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%。