扬州大学线性代数§11 排列与逆序

1、12 线性代数线性代数是数学的一个分支，它的研究对象是向量向量、向量空间向量空间、线性变换线性变换和有限维的线性方程组有限维的线性方程组求解求解。而向量空间是现代数学的一个重要课题，线性代数被广泛地应用于抽象代数和泛函分析中，线性代数的理论已被泛化为算子理论。 另外，对于科学研究中的非线性模型，在一定条件下通常可以被近似为线性模型，这使得线性代数在处理实际问题(物理、生命、化学、社科)时也被广泛采用。 3第二章第二章 矩阵矩阵21 矩阵的概念22 矩阵的运算23 几种特殊的矩阵24 分块矩阵25 逆矩阵26 矩阵的初等变换4第三章第三章 消元法消元法31 消元法解线性方程组32 n维向量33

2、向量组的秩34 矩阵的秩35 线性方程组解的一般理论第四章第四章 向量空间、矩阵的特征值与特征向量向量空间、矩阵的特征值与特征向量41 向量空间42 向量的内积43 正交矩阵44 矩阵的特征值和特征向量5第五章第五章 二次型二次型5.1 二次型的矩阵表示5.2 标准型5.3 二次型规范型5.4 正定二次型611 排列与逆序12 n阶行列式的定义13 行列式的性质14 行列式按行(列)展开15 Cramer法则7例、用1、2、3三个数字，可以组成多少个没有重复数字 的三位数？解：123 132 213 231 312 321总数=6 (个) =3！(个)三级排列排列：排列：由连续自然数1、2、3

3、、4、n组成的一个有序有序 数组数组称为一个n级排列，简称为排列。自然排列自然排列：n级排列123n 称为自然排列。821413243 1314不是排列不是排列不是排列n级排列的三要素：(2) n个数中不能有重复数; (3) 不能有大于n的数。543215级排列31424级排列(1)由n个自然数组成;n级排列的总数级排列的总数 =n!个11111nnC CC例：9124313421324解：4级排列的总数4!=24 个例、由1、2、3、4这四个数可构成四级排列。12341423142310排列的表示：排列的表示：j1 j2 j3 jn 所有n级排列的集合例如： j1 j2 j3 表示所有3级排

4、列当j1=3、j2=1、j3=2时，j1 j2 j3代表三级排列312当j1=2、j2=3、j3=1时，j1 j2 j3代表三级排列231j1 j2 j3 jn 表示一个n级排列11逆序：逆序：在一个排列中，如果两个数的前后位置与它们的大小顺序相反(即排在前面的数大于排在后面的数)，则称这两个数构成排列的一个逆序。即：对n级排列 j1 j2 ji jk jn,若jijk，则称ji与 jk构成一个逆序，记为 ji jk。例：在三级排列312中, 逆序：31 、32；在四级排列4231中， 逆序：42、21、3112【例1】写出下列排列的逆序。（1）3241逆序：32、31、 21、 41（2）5

5、2341逆序：52、53、54、51、21、31、41（3）1234567逆序：无13逆序数逆序数:一个排列中逆序的个数称为这个排列的逆序数 ,记 为: (j1, j2 , jn)例如:（3）1234567 逆序:无 （1）3241 逆序：32、31、21、41,（2）52341逆序：52、53、54、51、21、31、4143241 75234101234567逆序数的计算方法逆序数的计算方法( (穷举法穷举法) ): (j1, j2 , jn) = j1后面比j1小的数的个数 + j2后面比j2小 的数的个数 + + jn-1后面比jn-1小的数的个数。14排列排列奇排列奇排列偶排列偶排列

6、逆序数为奇数的排列称为奇排列逆序数为偶数的排列称为偶排列利用逆序数的性质可以对排列进行分类：利用逆序数的性质可以对排列进行分类：【例2】 求排列 的逆序数(123 2 1)n nn 123 2 1n nn 解:(1)(2)2 1nn(1)/ 2n n15当k=4n时， = 2n(4n-1)为偶数当k=4n+1时， =2n(4n+1)为偶数当k=4n+2时， =(2n+1)(4n+1)为奇数当k=4n+3时， =(2n+1)(4n+3)为奇数135(21)246(2 )kk【例3】判断排列135（2k-1）246（2k）的奇偶性解:因此因此:当k=4n或k=4n+1时，该排列为偶排列； 当k=4

7、n+2或k=4n+3时，该排列为奇排列。123(1)k (1)/ 2k k16而相邻两个数的对换称为相邻对换。相邻对换。（3,5）例如: 23154 25134 （3,1） 23154 21354 相邻对换对换操作对换操作：在一个n级排列j1 j2 ji jkjn 中，若仅将其中两个数ji、 jk对调，其余不动，可得一个新的排列j1 j2 jk jijn ，对排列所施行的这样一次对调对调称为一个对换对换，记为( ji, jk)。17定理定理1 1：一次对换改变排列的奇偶性：一次对换改变排列的奇偶性即：奇偶性不同奇偶性不同则:nkijjjjj21与nikjjjjj21nkijjjjj21若 ki

8、jj,nikjjjjj21nkkiijjjjjjj1121设若:ljjjjjjjnkkii112111121ljjjjjjjnkiki若:jijk，证明：证明：先证ji、 jk为相邻相邻两个数时结论成立设: kijj ,nkikijjjjjjj112111121ljjjjjjjnkikiji jk,18nkkiijjjjjjj1121与nkikijjjjjjj1121奇偶性不同奇偶性不同显然：再证ji、jk为任两个数时结论成立设：,1 21111 2111ikj jiiii mkknikii m iknj jjj jjj jjj jjj jjj jj 先将ji依次与ji+1、 ji+2、 ji

9、+m做相邻对换，得排列:j1 j2ji1 ji+1ji+m ji jk jk+1 jn再将jk依次与ji、 ji+m ji+1做相邻对换,得排列:j1 j2 ji1 jk ji+1 ji+m ji jk+1 jn共做了m+(m+1)=2m+1次相邻对换。 由于一次相邻对换改变排列的奇偶性，而2m+1相邻对换为奇数次，故改变了排列的奇偶性。19（3,5）例如, 2315425134231543奇排列251344偶排列【定理【定理2】：】：在所有的n级排列中（n1）,奇排列与偶排列的个数相等，各为 个。2!n证明：证明：设在n!个n级排列中(n1),奇排列共有p个,偶排列共有 q个，则: p+q=

10、 n! 现对每一个奇排列施行一次对换奇排列施行一次对换，即:(偶排列),1 21 2i kj jiknkinj jjjjj jjjj (奇排列)20由此可得p p个偶排列个偶排列，由于偶排列的个数共有q个，所以:qp 同理，对q个偶排列各做一次对换，可得q个奇排列，而奇排列共有p个，故有:qp 所以:p=q.又：p+q=n! 故：p = q = 2!n21对n级排列 j1j2 jijkjn,若ji jk，则称ji与 jk构成一个逆序，记为： jijk2、 逆序：1、n级排列： 由自然数1、2、3、4、n组成的一个有序数组称为一 个n级排列，简称为排列，记为： j1 j2 j3jn 223、逆序数: 一个排列中逆序的个数称为这个排列的逆序数 。 njjj21记为4、排列奇排列偶排列逆序数为奇数的排列称为奇排列逆序数为偶数的排列