📄 2_9.htm

📁 组合数学清华大学研究生课程课件呵呵
💻 HTM
字号:
<head><title>组合数学</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><h1>§2.9  排错问题&nbsp;</h1><p>&nbsp;&nbsp;&nbsp; n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素在原来的位置上，则称这个排列为错排；有的叫重排。</p><p>&nbsp;&nbsp;&nbsp; 以1，2，3，4四个数的错排为例，分析其结构，找出规律性的东西来。&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 1 2的错排是唯一的，即2 1。&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 1 2 3的错排有3 1 2，2 3 1。这二者可以看作是1 2错排，3分别与1，2换位而得的。&nbsp;</p><p> 即            ((()))&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 1 2 3 4的错排有&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 4 3 2 1，4 1 2 3，4 3 1 2，&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 3 4 1 2，3 4 2 1，2 4 1 3，&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2 1 4 3，3 1 4 2，2 3 4 1。&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 第一列是4分别与1，2，3互换位置，其余两个元素错排，由此生成的。&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 第2列是4分别与3，1，2（123的一个错排）的每一个数互换而得到的。</p><p>即   ((()))&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 第三列则是由另一个错排231和4换位而得到，</p><p>即   ((()))&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 上面的分析结果，实际上是给出一种产生错排的结果。&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 设n个数1，2，…，n错排的数目为D<sub>n</sub> ，任取其中一数i，数i分别与其他的n-1个数之一互换，其余n-2个数进行错排，共得 (n-1)D<sub>n-2</sub>个错排。另一部分位数i以外的n-1个数进行错排，然后i与其中每个数互换得(n-1)D<sub>n-1</sub>个错排。&nbsp;</p><p>&nbsp;&nbsp;&nbsp; 综合以上分析结果得递推关系&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_9.pic/image008.gif" width="265" height="72"></p><p>（2-9-1）是一非常系数的递推关系，下面提供一种解法。&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_9.pic/image010.gif" width="253" height="75"></p><p>&nbsp;&nbsp;&nbsp; 由于D<sub>1</sub>=0,D<sub>0</sub>=1 故得关于D<sub>n</sub>得递推关系&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_9.pic/image015.gif" width="249" height="25"></p><p>令&nbsp;</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_9.pic/image017.gif" width="245" height="41"></p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_9.pic/image019.gif" width="132" height="99"></p><p>可得</p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_9.pic/image021.gif" width="136" height="25"></p><p>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img border="0" src="2_9.pic/image023.gif" width="252" height="88"></p>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -