User:Avit4799/沙盒3：修订间差异
删除的内容 添加的内容
无编辑摘要 |
←清空全部内容 |
||
| 第1行： | 第1行： | ||
考虑一个有n个元素的[[排列]]，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个'''错排'''。研究一个排列错排个数的问题，叫做'''错排问题'''或称为'''更列问题'''。我们把n个元素的错排数记为D<sub>n</sub>。如，四人各写一张贺年卡互相赠送，有多少种赠送方法？此题中自己写的贺年卡不能送给自己，所以是典型的错排问题。此时D<sub>4</sub>=9。 |
|||
==研究错排问题的方法== |
|||
===枚举法=== |
|||
对于情况较少的排列，我们可以使用[[枚举法]]。<ref>{{Cite book | author =卢开澄、卢华明 | title =《组合数学》 | publisher = 清华大学出版社 |ISBN =730213961X | language= 简体中文 }}</ref> |
|||
*当n=1时，全排列只有一种，不是错排，D<sub>1</sub>=0。 |
|||
*当n=2时，全排列有两种，即1、2和2、1，后者是错排，D<sub>2</sub>=1。 |
|||
*当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是错排，D<sub>3</sub>=2。我们用同样的方法可以知道D<sub>4</sub>=9。 |
|||
===递推数列法=== |
|||
对于排列数较多的情况，难以采用枚举法，我们可以推导出错排数的[[递推公式]]。 |
|||
显然D<sub>1</sub>=0，D<sub>2</sub>=1。当n≥3时我们不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑第n位的情况。 |
|||
*当k排在第n位时，除了n和k以外还有n-2个数，其错排数为D<sub>n-2</sub>。 |
|||
*当k不排在第n位时，那么将包括k在内的剩下n-1个数错排，其错排数为D<sub>n-1</sub>。 |
|||
所以当n排在第k位时共有D<sub>n-2</sub>+D<sub>n-1</sub>种错排方法，又k有从1到（n-1）共（n-1）种取法，我们可以得到： |
|||
D<sub>n</sub>=(n-1)(D<sub>n-1</sub>+D<sub>n-2</sub>) |
|||
==错排公式== |
|||
在上面我们得到D<sub>n</sub>=(n-1)(D<sub>n-1</sub>+D<sub>n-2</sub>) |
|||
从这个公式中我们可以推出D<sub>n</sub>的通项公式，方法如下<ref>http://wenku.baidu.com/view/2f395e4de518964bcf847cde.html?from=rec&pos=1&weight=9&lastweight=5&count=5</ref>： |
|||
为书写方便，我们记D<sub>n</sub>=n!M<sub>n</sub> |
|||
则M<sub>1</sub>=0,M<sub>2</sub>=<math>\frac{1}{2}</math> |
|||
当n大于等于3时，由D<sub>n</sub>=(n-1)(D<sub>n-1</sub>+D<sub>n-2</sub>)，即n!M<sub>n</sub>=(n-1)(n-1)!M<sub>n-1</sub>+(n-1)(n-2)!M<sub>n-2</sub>=(n-1)(n-1)!M<sub>n-1</sub>+(n-1)!M<sub>n-2</sub> |
|||
所以，nM<sub>n</sub>=(n-1)M<sub>n-1</sub>+M<sub>n-2</sub> |
|||
于是有:<math>M_n - M_{n-1}=-\frac{1}{n}(M_{n-1}-M_{n-2})=...=(-\frac{1}{n})(-\frac{1}{n-1})...(-\frac{1}{3})(M_2-M_1)=(-1)^n\frac{1}{n!}</math> |
|||
所以<math>M_{n-1}-M_{n-2}=(-1)^{n-1}\frac{1}{(n-1)!}</math> |
|||
<math>M_2-M_1=(-1)^2\frac{1}{2!}</math> |
|||
累加，得<math>M_n=(-1)^2\frac{1}{2!}+(-1)^3\frac{1}{3!}...+(-1)^{n}\frac{1}{n!}</math> |
|||
因此，我们得到<math>D_n=n!M_n=n!(\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!})</math> |
|||
===简化公式=== |
|||
我们在这里提供一个求错排数的简化公式，证明略。 |
|||
<math>D_n=[\frac{n!}{e}+0.5]</math>，其中的[x]为[[高斯函数]]。 |
|||
==参考资料== |
|||
{{reflist}} |
|||
[[Category:组合数学]] |
|||