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>) |
|||
==错排公式== |
|||
2012年2月11日 (六) 13:28的版本
考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。研究一个排列错排个数的问题，叫做错排问题或称为更列问题。我们把n个元素的错排数记为Dn。如，四人各写一张贺年卡互相赠送，有多少种赠送方法？此题中自己写的贺年卡不能送给自己，所以是典型的错排问题。此时D4=9。
研究错排问题的方法
枚举法
对于情况较少的排列，我们可以使用枚举法。[1]
- 当n=1时，全排列只有一种，不是错排，D1=0。
- 当n=2时，全排列有两种，即1、2和2、1，后者是错排，D2=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是错排，D3=2。我们用同样的方法可以知道D4=9。
递推数列法
显然D1=0，D2=1。当n≥3时我们不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑第n位的情况。
- 当k排在第n位时，除了n和k以外还有n-2个数，其错排数为Dn-2。
- 当k不排在第n位时，那么将包括k在内的剩下n-1个数错排，其错排数为Dn-1。
所以当n排在第k位时共有Dn-2+Dn-1种错排方法，又k有从1到（n-1）共（n-1）种取法，我们可以得到： Dn=(n-1)(Dn-1+Dn-2)
错排公式
- ^ 卢开澄、卢华明. 《组合数学》. 清华大学出版社. ISBN 730213961X （简体中文）.