错排信封问题

装错信封问题即欧拉错排问题
中“信封装错问题”的数学模型及解法；
有人写了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]种方法），这样就整体上也都是全错位了。

关于错排问题的递推公式的一点分析作者：冯弋舟来源：《读与写·下旬刊》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。

“装错信封问题”的数学模型与求解某人写了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个不同元素的一个错排．故由公式可求得不同的干部调配方案数为-- 参考答案：瑞士数学家欧拉按一般情况给出了一个递推公式：用Ａ、Ｂ、Ｃ,,表示写着ｎ位友人名字的信封，ａ、ｂ、ｃ,,表示ｎ份相应的写好的信纸。

装错信封问题容斥原理I ∑∑≤<≤=⋂+-=⋂⋂⋂ni i i i ni in A AA A A A A 21211121||||||||∑≤<<<≤⋂⋂⋂-++⋂⋂⋂-++ni i i n n i i i kk k A A A A A A2121121.||)1(||)1(II 12121211||||||nn i i i i i i nA A A A A A =≤<≤⋃⋃⋃=-⋂∑∑∑≤<<<≤--⋂⋂⋂-++⋂⋂⋂-++ni i i n n i i i k k kA A A A A A 212112111.||)1(||)1(装错信封问题“装错信封问题”是由当时最有名的数学家约翰·伯努利（Johann Bernoulli ，1667—1748）的儿子丹尼尔·伯努利（Danid Bernoulli ，1700—1782）提出来的，大意如下：一个人写了n 封信都装错了信封，问都装错信封的装法有多少种？其他叙述方式(1) “拿错帽子问题” (2) “分发贺卡问题” (3) “更列问题”设n 封为n a a ,,1 ，n 个信封为n A A ,,1 ，装对的情形为i a 装入i A ),,2,1(n i =. 我们把都装错的情形数记为n .(1) 若不考虑是否装对信封，则有!n A nn =种.(2) 若至少有1封信装对信封，即i a 装入i A ，而其他1-n 封信的装法有-1-1(-1)!n n A n =.由于i a 装入i A 有1n C 种，所以，至少有1封信装对信封的装法有1-1-1n n n C A 种.(3) 若至少有2封信装对信封，即i a 装入i A ，j a 装入j A ，而其他2-n 封信的装法有-2-2(-2)!n n A n =，所以，至少有2封信装对信封的装法有2-2-2n n n C A 种. (4) 至少有3封信装对信封的装法有3-3-3n n n C A 种.(5) 一般地，其中至少有k 封装对的装法有k n kn n k C A --种.于是，由容斥原理，封信都装错的情形种数为.12!(1)!(2)!(1)()!(1)1k k n nn n n n C n C n C n k =-⋅-+⋅-++-⋅-++-⋅另证.设n 封为n a a ,,1 ，n 个信封为n A A ,,1 ，装对的情形为i a 装入i A ),,2,1(n i =.我们把都装错的情形数记为n .首先研究1a 装入2A 时，信封装错的种数.分两种情况.(1)1a 装入2A ,2a 装入1A . 此时，其余2-n 封信都装错的种数为2-n .(2)1a 装入2A ,2a 没有装入1A . 此时，其余1-n 封信都装错的种数为1-n .这样，当1a 装入2A 时，信封装错的种数为1+2n n --.同样，当1a 装入3A ，当1a 装入4A ，……，当1a 装入n A 时，信封装错的种数也为1+2n n --.从而，信封装错的所有种数为)21)(1(-+--=n n n n .2)1(11-⋅-+---⋅=n n n n n n .于是，有递推公式]2)1(1)[1(1-⋅----=-⋅-n n n n n n . 取,,,4,3,2n n =可得332(1)(221)-⋅=--⋅]2)1(1)[1(1-⋅----=-⋅-n n n n n n相乘得)122()1(12⋅--=-⋅--n n n n . 容易求出 .01,12==于是 .)1(1n n n n -=-⋅-从而 .!)1()!1(1!n n n n n n-=---取,,,4,3,2n n =可得!2)1(!11!222-=-.!)1()!1(1!n n n n n n -=---相加得.!)1(!51!41!31!21!11!n n n n-++-+-=- 化为1111(1)![].2!3!4!5!!nn n n -=⋅-+-++定理1 n 封信都装错了信封的种数为].!)1(!51!41!31!21[!n n n n-++-+-⋅= 或 ∑=--=ni in n i A n 0)1(或 ∑=-⋅-=ni ini i n C n 0)!()1(.有且只有k )(n k <封信装对信封等价于k n -封信装错信封. 于是有定理2 有且只有k 封信装对的种数为.k n C kn -⋅有且只有k 封信装错的种数为.k C k n ⋅定理3 至少有k 封信装对的种数为)!.(k n C A C kn k n k n k n -⋅=⋅--例1 由93,2,1，，组成的形如⨯⨯⨯⨯⨯1234的九位数，其中，万位不是5，千位不是6，百位不是7，十位不是8，各位不是9，这样的九位数有多少个？例2 证明!.00n n C C nn n =⋅++⋅例3 某一天的课表要排6门课程，每门课上且上一节，一天排6节课，体育课不在第一节，数学不在最后一节，问有多少种排法？例4 有一个n 位数的集合，且这n 位数是由k ,,2,1 组成的，若每个数字至少出现一次，那么这个集合元素共有多少个？例5 P 为集合},,2,1{n S n =的一个排列，一个元素n j S ∈，如果j j P =)(就称为P 的一个不动点. 令n f 为n S 的无不动点的排列的个数，n g 为n S 恰有一个不动点的排列的个数，证明：.1||=-n n g f例6 把写有数码6,5,4,3,2,1的6张卡片插入编号为6,5,4,3,2,1的6只袋子，每只袋子只插入1张卡片.(1) 求每一张卡片的号码与所在袋子的号码都不同的插法种数. (2) 求恰有3张卡片的号码与所在袋子的号码相同的插法种数.1. 设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为第一步，先选出三个被错排的元素，有35C 种. 第二步，对已选出的三个元素进行错排，有2种.所以，根据乘法原理可得投放方法总数为35C ·2=20种.2. 某省决定对所辖8个城市的常政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？解实质上本题即为8个不同元素的错排问题，一种干部调配方法对应于8个不同元素的一个错排.11111111-+-+-+-+=（种）8!(1)148331!2!3!4!5!6!7!8!3.同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四张贺年卡的不同分配方式有4. 有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家，回家后，他们的妻子都发现他们戴了别人的帽子.问5个客人都不戴自己帽子的戴法有多少种？5. 由5,4,3,2,1这五个数字组成没有重复数字的五位数，按从小到大的顺序排列，问32154是这个数列的第几项？6. 以长方体的8个顶点中的3点位顶点的三角形,锐角三角形的个数共有几个?7. 一副扑克牌去掉两张王后还有52张，将牌发给4个人，每人13张，则某人获得的13张牌中花色齐全的全部情况数为多少？第一、先从13张牌中选出一张，再给他选一个花色，则有13×4种选法第二，从剩余的12张牌中再选一张，给他选一个与第一张牌颜色不同的花色，则有12×3种选法第三、再从剩余的11张牌中选出一张，给他与前两张不同的花色，则有11×2种选法第四、再从剩余的10张牌中选出一张，给他最后的一种花色，则有10×1种选法那么一共有：13×4×12×3×11×2×10×1=411840种组合情况．8. 在年龄彼此不同的30人中选出两组人,第一组12人,第二组15人,若第一组中年龄最大的人比第二组中年龄最小的还要小,问有几种选择方式？40609. 从1-300中,任取3个不同的数,使它们的和为3的倍数,有多少种取法?10.从6名短跑运动员中选出4人参加4×100m接力赛,如果甲不跑第一棒，乙不跑最后一棒,那么不同的参赛方案有几种？11. 如果1个凸十边形没有三条对角线交于同一点,问在十边形内部由它们的交点可将对角线分割成多少条线段?凸n边形的任意3条对角线不相交于形内的一点,问:(1)这些对角线将凸边形分成了多少个区域?(2)这些对角线被交点分成了多少条线段?12. 从数字7,5,3,1,0中取出不同的三个作系数，可组成多少个不同的一元二次方程？其中有实数根的有几个？一共有多少个实数根？。

行测错位重排的精髓一、问题描述错位重排是一种比较难理解的复杂数学模型，是伯努利和欧拉在错装信封时发现的，因此又称伯努利-欧拉装错信封问题。

通常表述为：编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法?二、题目剖析1.编号为1的1封信，装入编号为1的1个信封，要求每封信和信封的编号不同，问有多少种装法?解析：编号为1的信不能放入编号为1的信封，因此无法实现，有0种装法。

2.编号为1、2的2封信，装入编号为1、2的2个信封，要求每封信和信封的编号不同，问有多少种装法?解析：编号为1的信不能放入编号为1的信封，因此只能是编号为1的信放入编号为2的信封，编号为2的信放入编号为1的信封，有1种装法。

3.编号为1、2、3的3封信，装入编号为1、2、3的3个信封，要求每封信和信封的编号不同，问有多少种装法?解析：编号为1的信不能放入编号为1的信封，因此只能是编号为1的信放入编号为2或3的信封。

若编号为1的信放入编号为2的信封，则编号为2的信只能放入编号为3的信封，编号为3的信放入编号为1的信封;若编号为1的信放入编号为3的信封，则编号为2的信只能放入编号为1的信封，编号为3的信放入编号为2的信封，因此，有2种装法。

4.编号为1、2、3、4的4封信，装入编号为1、2、3、4的4个信封，要求每封信和信封的编号不同，问有多少种装法?解析：编号为1的信不能放入编号为1的信封，因此只能是编号为1的信放入编号为2、3或4的信封。

若编号为1的信放入编号为2的信封，则编号为2的信能放入编号为1、3、4的信封，而当编号为2的信放好信封后，剩余编号为3、4的信只有一种放信封的装法，因此，有3×3=9种装法。

5.编号为1、2、3、4......n的n封信，装入编号为1、2、3、4......的n个信封，要求每封信和信封的编号不同，问有多少种装法?解析：编号为1的信不能放入编号为1的信封，因此只能是编号为1的信放入编号为2、3、4......的(n-1)个信封。

装错信封问题容斥原理I ∑∑≤<≤=⋂+-=⋂⋂⋂ni i i i ni in A AA A A A A 21211121||||||||∑≤<<<≤⋂⋂⋂-++⋂⋂⋂-++ni i i n n i i i kk k A A A A A A2121121.||)1(||)1(II 12121211||||||nn i i i i i i nA A A A A A =≤<≤⋃⋃⋃=-⋂∑∑∑≤<<<≤--⋂⋂⋂-++⋂⋂⋂-++ni i i n n i i i k k kA A A A A A 212112111.||)1(||)1(装错信封问题“装错信封问题”是由当时最有名的数学家约翰·伯努利（Johann Bernoulli ，1667—1748）的儿子丹尼尔·伯努利（Danid Bernoulli ，1700—1782）提出来的，大意如下：一个人写了n 封信都装错了信封，问都装错信封的装法有多少种？其他叙述方式(1) “拿错帽子问题” (2) “分发贺卡问题” (3) “更列问题”设n 封为n a a ,,1 ，n 个信封为n A A ,,1 ，装对的情形为i a 装入i A ),,2,1(n i =. 我们把都装错的情形数记为n .(1) 若不考虑是否装对信封，则有!n A nn =种.(2) 若至少有1封信装对信封，即i a 装入i A ，而其他1-n 封信的装法有-1-1(-1)!n n A n =.由于i a 装入i A 有1n C 种，所以，至少有1封信装对信封的装法有1-1-1n n n C A 种.(3) 若至少有2封信装对信封，即i a 装入i A ，j a 装入j A ，而其他2-n 封信的装法有-2-2(-2)!n n A n =，所以，至少有2封信装对信封的装法有2-2-2n n n C A 种. (4) 至少有3封信装对信封的装法有3-3-3n n n C A 种.(5) 一般地，其中至少有k 封装对的装法有k n kn n k C A --种.于是，由容斥原理，封信都装错的情形种数为.12!(1)!(2)!(1)()!(1)1k k n nn n n n C n C n C n k =-⋅-+⋅-++-⋅-++-⋅另证.设n 封为n a a ,,1 ，n 个信封为n A A ,,1 ，装对的情形为i a 装入i A ),,2,1(n i =.我们把都装错的情形数记为n .首先研究1a 装入2A 时，信封装错的种数.分两种情况.(1)1a 装入2A ,2a 装入1A . 此时，其余2-n 封信都装错的种数为2-n .(2)1a 装入2A ,2a 没有装入1A . 此时，其余1-n 封信都装错的种数为1-n .这样，当1a 装入2A 时，信封装错的种数为1+2n n --.同样，当1a 装入3A ，当1a 装入4A ，……，当1a 装入n A 时，信封装错的种数也为1+2n n --.从而，信封装错的所有种数为)21)(1(-+--=n n n n .2)1(11-⋅-+---⋅=n n n n n n .于是，有递推公式]2)1(1)[1(1-⋅----=-⋅-n n n n n n . 取,,,4,3,2n n =可得332(1)(221)-⋅=--⋅]2)1(1)[1(1-⋅----=-⋅-n n n n n n相乘得)122()1(12⋅--=-⋅--n n n n . 容易求出 .01,12==于是 .)1(1n n n n -=-⋅-从而 .!)1()!1(1!n n n n n n-=---取,,,4,3,2n n =可得!2)1(!11!222-=-.!)1()!1(1!n n n n n n -=---相加得.!)1(!51!41!31!21!11!n n n n-++-+-=- 化为1111(1)![].2!3!4!5!!nn n n -=⋅-+-++定理1 n 封信都装错了信封的种数为].!)1(!51!41!31!21[!n n n n-++-+-⋅= 或 ∑=--=ni in n i A n 0)1(或 ∑=-⋅-=ni ini i n C n 0)!()1(.有且只有k )(n k <封信装对信封等价于k n -封信装错信封. 于是有定理2 有且只有k 封信装对的种数为.k n C kn -⋅有且只有k 封信装错的种数为.k C k n ⋅定理3 至少有k 封信装对的种数为)!.(k n C A C kn k n k n k n -⋅=⋅--例1 由93,2,1，，组成的形如⨯⨯⨯⨯⨯1234的九位数，其中，万位不是5，千位不是6，百位不是7，十位不是8，各位不是9，这样的九位数有多少个？例2 证明!.00n n C C nn n =⋅++⋅例3 某一天的课表要排6门课程，每门课上且上一节，一天排6节课，体育课不在第一节，数学不在最后一节，问有多少种排法？例4 有一个n 位数的集合，且这n 位数是由k ,,2,1 组成的，若每个数字至少出现一次，那么这个集合元素共有多少个？例5 P 为集合},,2,1{n S n =的一个排列，一个元素n j S ∈，如果j j P =)(就称为P 的一个不动点. 令n f 为n S 的无不动点的排列的个数，n g 为n S 恰有一个不动点的排列的个数，证明：.1||=-n n g f例6 把写有数码6,5,4,3,2,1的6张卡片插入编号为6,5,4,3,2,1的6只袋子，每只袋子只插入1张卡片.(1) 求每一张卡片的号码与所在袋子的号码都不同的插法种数. (2) 求恰有3张卡片的号码与所在袋子的号码相同的插法种数.1. 设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，则这样的投放方法的总数为第一步，先选出三个被错排的元素，有35C 种. 第二步，对已选出的三个元素进行错排，有2种.所以，根据乘法原理可得投放方法总数为35C ·2=20种.2. 某省决定对所辖8个城市的常政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？解实质上本题即为8个不同元素的错排问题，一种干部调配方法对应于8个不同元素的一个错排.11111111-+-+-+-+=（种）8!(1)148331!2!3!4!5!6!7!8!3.同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，则四张贺年卡的不同分配方式有4. 有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家，回家后，他们的妻子都发现他们戴了别人的帽子.问5个客人都不戴自己帽子的戴法有多少种？5. 由5,4,3,2,1这五个数字组成没有重复数字的五位数，按从小到大的顺序排列，问32154是这个数列的第几项？6. 以长方体的8个顶点中的3点位顶点的三角形,锐角三角形的个数共有几个?7. 一副扑克牌去掉两张王后还有52张，将牌发给4个人，每人13张，则某人获得的13张牌中花色齐全的全部情况数为多少？第一、先从13张牌中选出一张，再给他选一个花色，则有13×4种选法第二，从剩余的12张牌中再选一张，给他选一个与第一张牌颜色不同的花色，则有12×3种选法第三、再从剩余的11张牌中选出一张，给他与前两张不同的花色，则有11×2种选法第四、再从剩余的10张牌中选出一张，给他最后的一种花色，则有10×1种选法那么一共有：13×4×12×3×11×2×10×1=411840种组合情况．8. 在年龄彼此不同的30人中选出两组人,第一组12人,第二组15人,若第一组中年龄最大的人比第二组中年龄最小的还要小,问有几种选择方式？40609. 从1-300中,任取3个不同的数,使它们的和为3的倍数,有多少种取法?10.从6名短跑运动员中选出4人参加4×100m接力赛,如果甲不跑第一棒，乙不跑最后一棒,那么不同的参赛方案有几种？11. 如果1个凸十边形没有三条对角线交于同一点,问在十边形内部由它们的交点可将对角线分割成多少条线段?凸n边形的任意3条对角线不相交于形内的一点,问:(1)这些对角线将凸边形分成了多少个区域?(2)这些对角线被交点分成了多少条线段?12. 从数字7,5,3,1,0中取出不同的三个作系数，可组成多少个不同的一元二次方程？其中有实数根的有几个？一共有多少个实数根？。

伯努利-欧拉错装信封问题设有变号为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 !.。

容斥定理解伯努利装错信封问题错排问题是组合数学中的问题之一。

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

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

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

错排问题最早被尼古拉·伯努利和欧拉研究，因此历史上也称为伯努利-欧拉的装错信封的问题：在写信时将n 封信装到n 个不同的信封里，有多少种全部装错信封的情况？有多少种至少有一封装入正确信封？解：固定n 个信封顺序，n 封信均装错信封,实际上相当于{1,2, …, n} 错位排列问题。

设Ai 为第i 封信装入正确信封的方法集合，则伯努利装错信封问题即为求n 个性质均不满足的方法的个数，即n A A A (21)①设A 为n 个封信任意装入n 个信封的方法集合，显然|A|=n! ②设Ai 为第i 封信装入正确信封的方法集合，显然| Ai |=(n-1)! ③第i1,i2,…,ik 这k 封信装入正确信封的方法集合，则 )!(...21k n A A A k i i i -=另外i1,i2,...,ik 这k 封信的选取有C(n,k)种方法 ④根据容斥原理，n 封信均没装入正确信封的方法数有 n A A A (21)=)!()1(...)!()1(...)!2(2)!1(1!n n n n k n k n n n n n n n k -⎪⎪⎭⎫ ⎝⎛-++-⎪⎪⎭⎫ ⎝⎛-+--⎪⎪⎭⎫ ⎝⎛+-⎪⎪⎭⎫⎝⎛- =⎪⎪⎭⎫ ⎝⎛-++-+-+-!)1(...!)1(...!21!111!n k n n k另外，n 封信中至少有一封装入正确信封 n A A A (21)=)!()1(...)!()1(...)!2(2)!1(1n n n n k n k n n n n n n k -⎪⎪⎭⎫ ⎝⎛-++-⎪⎪⎭⎫ ⎝⎛-++-⎪⎪⎭⎫ ⎝⎛--⎪⎪⎭⎫⎝⎛ =⎪⎭⎫ ⎝⎛-++-+--!1)1(...!41!31!21!11!1n n n。

装错信封问题华图教育邹维丽1．问题的提出1)小明给住在五个国家的五位小朋友分别写一封信，这些信都装错了信封的情况共有多少种？A．32种 B．44种 C．64种 D．120种2)有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家．回家后，他们的妻子都发现他们戴了别人的帽子．问5个客人都不戴自己帽子的戴法有多少种？上述两个问题，实质上是完全一样的．是被著名数学家欧拉(LeonhardEuler，1707－1783)称为“组合数论的一个妙题”的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名的数学家约翰·伯努利(JohannBernoulli，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个不同元素的全排列中，有多少种不同的错排？设I表示n个不同元素的全排列的集合A i (i=1，2，…，n)为元素i在原位的排列的集合．A i∩A j (1≤i＜j≤n)为元素i与j在原位的排列的集合．i j…………()12121k i i i k A A A i i i ≤<<≤为n 个元素的序排的集合．则它们的排列数(即各个集合中元素的个数)分别为|I|=n ！| A i |=(n －1)！i| A i ∩A j |=(n －2)！…… (1)2k i i i A A A =(n －k)！………… ()12!0!n A A A n n =-=、 因为集合A 1有1n C 种，A i ∩A j 有2n C 种，…，12k i i i A A A 有k n C 种，12n A A A 有n n C 种。

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

错排问题的模型解释及求解吴如光(江苏省南京航空航天大学附属高级中学　210000)摘　要:本文就排列组合问题中的一类经典模型———错位排列,给出了三种求解方法,有参考意义.关键词:错排问题;原理解释中图分类号:G632 文献标识码:A 文章编号:1008-0333(2019)03-0027-02收稿日期:2018-10-25作者简介:吴如光(1983.12-),男,安徽省滁州市全椒县人,研究生,中学一级教师,从事高中数学教学研究. 一、错排问题错排问题,又称更列问题,是组合数学中的经典问题之一.该问题有许多具体的形式,例如:①在写信时将n 封信装到n 个不同的信封里,有多少种全部装错信封的情况?②n 个人各写一张贺卡相互赠送,有多少种赠送方法?从中概括出其数学模型:一个有n 个元素的排列,若这个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排,n 个元素的错排数记为D n ,求D n 的通项公式.对于它的研究最早可以追溯到十八世纪,在历史上也被称为伯努利———欧拉的错装信封问题,虽然数学家欧拉利用容斥原理已经给出n 个元素错排数通项公式为D n =n !·1-11!+12!-13!+…+(-1)nn !,但本文从不同角度解释此数学模型,得到不同的递推关系并解出其通项公式,加深对错排问题认识. 二、容斥原理解释容斥原理:设A 1,A 2,…,A n 为有限集合,用A i 表示集合A i 中的元素个数,则有:|A 1∪A 2∪…A n |=∑ni =1A i -∑1≤i <j ≤n|A i ∩A j |+∑1≤i <j <k ≤n|A i ∩A j ∩A k |-…+(-1)n -1|A 1∩A 2∩…∩A n |.以装信封为例:记第i 封信装对的事件为A i (i =1,2…,n ).不难得出:|A i |=(n -1)!,|A i ∩A j |=(n -2)!,…,|A 1∩A 2∩…A n |=1.事件A 1∪A 2∪…A n 代表至少有一封信装对,所以由容斥原理得:|A 1∪A 2∪…A n |=∑ni =1(-1)i -1C i n ·(n -i )!=∑ni =1(-1)i -1n !i !.故n 封信全装错的方法数为:D n =n !-∑ni =1(-1)i -1n !i !=n !·1-11!+12!-13!+…+(-1)nn !.三、按分步计数原理解释第1步:将1号信错放,有n -1种放法,不妨假设放在2号信封里;第2步:将2号信错放,有两类放法:①:2号信放入1号信封里,则其余n -2封信与信封将错放,有D n -2种放法.②:若2号信不放在1号信封里,此时相当于n -1封信(除1号信)放入n -1个信封(除2号信封),每封信都有一个禁止放的信封,因此有D n -1种放法.由此可得递推关系:D 1=0,D 2=1,D n =(n -1)·(D n -1+D n -2),n ≥3.∴D n -n ·D n -1=-[D n -1-(n -1)·D n -2],∴D n -n ·D n -1=(-1)n,(n ≥2),∴D n n !-D n -1(n -1)!=(-1)n n !,累加得:D n n !=D 11!+12!-13!+…+(-1)nn !.∴D n =n !·1-11!+12!-13!+…+(-1)nn !.—72—四、按分类计数原理解释将n 封信全排列共有n !种,按照装错信封的个数进行分类,装错i 封的种类有C i n·D i 种,i =0,1,…,n ,D 0代表信全都装对,所以D 0=1.由此可得递推关系:n !=∑ni =0C in ·D i .我们将利用一个引理解出D n .引理:若{a n },{b n }是两个数列,对任意n ∈N ∗,a n =∑ni =0C i n ·b i ,则有b n =∑ni =0(-1)n -i C i n ·a i ,n ∈N ∗.证明:若n ∈N ∗,a n =∑ni =0C in ·b i ,则有:∑ni =0(-1)n -i ·C i n ·a i =∑ni =0(-1)n -i ·C i n ·∑ij =0C j i ·b j=∑n i =0∑ij =0(-1)n -i·C i n·C j i·b j =∑n i =0∑ij =0(-1)n -i·C j n·Cn -i n -j·b j =∑nj =0∑ni =j (-1)n -i·C jn ·C n -in -j ·b j=∑nj =0C j n ·b j ·∑ni =j(-1)n -i ·C n -in -j ,这里∑ni =j(-1)n -i ·C n -i n -j =0,j ≠n ;1,j =n.因此∑n j =0C j n ·b j ·∑n i =j (-1)n -i ·C n -in -j =b n .所以b n =∑ni =0(-1)n -iC in·a i ,n ∈N ∗.引理得证.只需令引理中的a n =n !,b n =D n .由引理可得:D n =∑n i =0(-1)n -i·C in ·i !=∑ni =0(-1)n -i·n !(n -i )!=n !·1-11!+12!-13!+…+(-1)nn !.以上对错排问题的几种不同看法,得到了不同的递推关系,但是殊途同归,加深了对错排问题的理解,其结论的形式优美,让我们再次感受到数学的美妙. 参考文献:[1]张仁海.解决“错位排列”问题的一般方法[J ].数学学习与研究,2017(01):114+117.[责任编辑:杨惠民]高中数学解题中思维开拓性的培养方法楚絮影(江苏省阜宁中学高三13班　224000)摘　要:同学们在学习时,必须应用多种方法培养开拓展思维,提高解题水平.本文对此进行了分析研究.关键词:高中;数学;解题;思维;开拓性;培养中图分类号:G632 文献标识码:A 文章编号:1008-0333(2019)03-0028-02收稿日期:2018-10-25作者简介:楚絮影(2002.3-),女,江苏省阜宁人,在校学生. 开拓性的思维,是指从多个角度来分析问题的特征、多渠道的分析问题的性质、多元化的思考解决问题的策略.只有具备这样的思维,同学们才能灵活地解决各种数学问题. 一、学会全方位地观察问题,找到准确的解题方向 部分同学在分析数学问题时,只能一味地套用现有的数学问题的公式来解决问题,而不能灵活地观察问题,根据数学问题的特征来分析问题.同学们在解决数学问题时,第一,要学会分析问题的特征;第二,要学会根据问题的特征灵活地转换问题.例1　已知a ,b ,c ,d 都是实数,求证:a 2+b 2+c 2+d 2≥(a -c )2+(b -d )2.很多同学一看到这道题,就觉得这个问题很复杂,他们或者应用平方法,或者尝试应用整体换元法,都很难解决问题.同学们要看到,a 2+b 2+c 2+d 2≥(a -c )2+(b -d )2的结构很像三角形的三边性质的问题.设A (a ,b ),B (c ,d ),那么可得AB=(a -c )2+(b -d )2,|OA |=a 2+b 2,|OB |=c 2+d 2,其中O 为平面直角座标系中的原点.根据三角—82—。

全错排序范例全错排序典型例子：一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？1.枚举法对于情况较少的排列，可以使用枚举法。

(1)当n=1时，全排列只有一种，不是错排，D1= 0。

(2)当n=2时，全排列有两种，即1、2和2、1，后者是错排，D2= 1。

(3)当n=3时，全排列有六种，即1、2、3；1、3、2；2、1、3；2、3、1；3、1、2；3、2、1，其中只有有3、1、2和2、3、1是错排，D3=2。

用同样的方法可以知道D4=9。

考试速记数字：D1= 0，D2= 1，D3=2，D4= 9，D5= 44，D6= 265，D7= 1854.2.递推数列法对于排列数较多的情况，难以采用枚举法。

这时可以用递归思想推导错排数的递回关系式。

问题：一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？Proof:显然：D1= 0，D2= 1当n>2时，不妨设n排在了第k位，其中k≠n，即k=1,2,3,…,n-1,共n-1种情况。

那么考虑第n位的情况:(1)当k排在第n位时，除了n和k以外还有n-2个数，其错排数为D n−2。

(2)当k不排在第n位时。

此时我们将第n位，重新命名位New k。

那么问题“一个人写了n-1封不同的信及相应的n-1个不同的信封，他把这n-1封信都装错了信封，问都装错信封的装法有多少种？”，其排位数为D n−1。

综上所述：D n=（n-1）(D n−1+D n−2)通过数学归纳法，可以得到D n=n!(12!−13!+⋯+(−1)nn!)3.例题【3.1】4位厨师聚餐时各做了一道拿手菜，现在要求每人各品尝一道菜，但不能尝自己做的那道菜，问共有几种不同的尝法？（B）A．6种B．9种C．12种D．15种【3.2】相邻的4个车位中停放了4辆不同的车，现将所有车开出后再重新停入这4个车位，要求所有车都不得停在原来的车位中，则一共有多少种不同的停放方式？（A）A．9 B．12 C．14 D．16【3.3】某单位从下属的5个科室各抽调了一名工作人员，交流到其他科室，如每个科室只能接收一个人的话，有多少种不同的人员安排方式？（C）A．120 B .78 C.44 D.24【3.4】某集团企业5个分公司分别派出1人去集团总部参加培训，培训后再将5人随机分配到这5个分公司，每个分公司只分配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、4、5逐个推算就能解答蒙摩的问题。

f(1)=0 f(2)=1 f(3)=2 f(4)=9 f(5)=44
答案是44种。