线性代数排列及其逆序数学习教案

1、线性代数线性代数(xin xn di sh) 排列及其逆排列及其逆序数序数第一页，共13页。第1页/共13页第二页，共13页。定定义义(dngy)排列排列(pili)的逆序数的逆序数 在一个排列在一个排列 中，若中，若数数 则称这两个数组成一个逆序则称这两个数组成一个逆序. nstiiiii21stii 例如例如(lr) 排列排列32514 中，中， 我们规定各元素之间有一个标准次序我们规定各元素之间有一个标准次序, n 个不同个不同的自然数，规定由小到大为的自然数，规定由小到大为标准次序标准次序.3 2 5 1 4逆序逆序逆序逆序逆序逆序二、排列的逆序数第2页/共13页第三页，共13页。定义

2、定义 一个排列中所有逆序的总数一个排列中所有逆序的总数(zngsh)称称为此排列为此排列 的逆序数的逆序数.例如例如(lr) 排列排列32514 中，中， 3 2 5 1 4逆序数逆序数(xsh)为为31010故此排列的故此排列的逆序数为逆序数为3+1+0+1+0=5.第3页/共13页第四页，共13页。1 1、用多种方法、用多种方法(fngf)(fngf)求排列求排列1635248716352487的逆序的逆序数数. .2 2、的取值范围？、的取值范围？3 3、求、求n(n-1) 21n(n-1) 21的逆序数。的逆序数。4 4、若求、若求)(21nii it1 2()ni iit 2 1()

3、nii i 第4页/共13页第五页，共13页。逆序数为奇数逆序数为奇数(j sh)的排列称为奇排列的排列称为奇排列;逆序数为偶数逆序数为偶数(u sh)的排列称为偶排列的排列称为偶排列.排列排列(pili)的奇偶性的奇偶性第5页/共13页第六页，共13页。定义定义(dngy)在排列中，将任意两个元素在排列中，将任意两个元素(yun s)对调，对调，其余元素其余元素(yun s)不动，这种作出新排列不动，这种作出新排列的手续叫做对换的手续叫做对换将相邻两个元素对调，叫做将相邻两个元素对调，叫做相邻对换相邻对换mlbbbaaa11例如例如bamlbbabaa11abnmlccbbbaaa111nm

4、lccabbbaa111baab第6页/共13页第七页，共13页。定理定理1 1一个排列一个排列(pili)(pili)中的任意两个元素对中的任意两个元素对换，排列换，排列(pili)(pili)改变奇偶性改变奇偶性证明证明(zhngmng)设排列为设排列为mlbbabaa11对换对换 与与abmlbbbaaa11除除 外，其它元素的逆序数不改变外，其它元素的逆序数不改变.b,aabba第7页/共13页第八页，共13页。当当 时，时，ba ab的逆序数不变的逆序数不变;经对换后经对换后 的逆序数增加的逆序数增加1 ,经对换后经对换后 的逆序数不变的逆序数不变 ， 的逆序数减少的逆序数减少1.a

5、b因此对换因此对换(du hun)相邻两个元素，排列改变奇偶性相邻两个元素，排列改变奇偶性.设排列设排列(pili)为为nmlcbcbabaa111当当 时，时，ba 现来对换现来对换 与与a.b第8页/共13页第九页，共13页。次相邻对换次相邻对换mnmlccbbabaa111次相邻对换次相邻对换1 mnmlccabbbaa111,111nmlcbcbabaa次相邻对换次相邻对换12 m,111nmlcacbbbaa所以一个排列中的任意两个元素对换所以一个排列中的任意两个元素对换(du hun)，排列改变，排列改变奇偶性奇偶性.abnmlccbbbaaa111abab第9页/共13页第十页，共13页。推论推论(tuln)奇排列调成标准排列的对换次数奇排列调成标准排列的对换次数(csh)(csh)为奇数，为奇数，偶排列调成标准排列的对换次数偶排列调成标准排列的对换次数(csh)(csh)为偶数为偶数. .定理定理2 2 在全部在全部 阶排列阶排列(pili)(pili)中中 , ,奇偶排奇偶排列列(pili)(pili)各各 占一半占一半. . n 2 n第10页/共13页第十一页，共13页。2 2 排列排列(pili)(pili)具有奇偶性具有奇偶性. .3 计算排列计算排列(pili)逆序数常用的方法有多种逆序数常用的方法有多种.1 1