线性代数全排列与逆序数学习教案

1、线性代数线性代数(xin xn di sh)全排列与逆序全排列与逆序数数第一页，共11页。.个元素的（全）排列个元素的（全）排列这这做做不同元素排成一列，叫不同元素排成一列，叫个个把把象，叫做元素象，叫做元素在数学中，把考察的对在数学中，把考察的对nn。元排列为记npppn21列）组成的排列称为自然排定由小到大为标准次序规个不同的自然数（如次序各元素之间有一个标准个不同的元素，先规定对于,nn.时，就说有一个逆序次序于标准次序不同后当某两个元素的先个元素的任意排列中，于是在这n.序数总和叫做这个排列的逆一个排列中所有逆序的的逆序数记为元排列npppn21)(21nppp第1页/共11页第二页，

2、共11页。例例1求排列求排列(pili)32514的逆序的逆序数数.解解在排列在排列(pili)32514中，中，3排在首位排在首位(shu wi)，逆序数为，逆序数为 0；2前面比前面比2大的数有一个（大的数有一个（3），故逆序数为），故逆序数为1；5是最大数，逆序数为是最大数，逆序数为 0；1前面比前面比1大的数有三个（大的数有三个（3、2、5）,故逆序数为故逆序数为3；4前面比前面比4大的数有一个（大的数有一个（5），故逆序数为），故逆序数为1；于是这个排列的逆序数为于是这个排列的逆序数为. 513010)32514(.偶排列序数为偶数的排列叫做逆做奇排列，逆序数为奇数的排列叫.表示的种

3、数，通常用个不同元素的所有排列nPn!123) 1(nnnPn第2页/共11页第三页，共11页。:法法计算排列的逆序数的方计算排列的逆序数的方., 121即是这个排列的逆序数即是这个排列的逆序数之和之和全体元素的逆序数全体元素的逆序数 niinttttt个自然数的一个排列，为设npppn21个，个，前面的元素有前面的元素有大的且排在大的且排在如果比如果比iiitpp.iitp这个元素的逆序数为这个元素的逆序数为就是说就是说，、考虑元素考虑元素)21(nipi 第3页/共11页第四页，共11页。例例2 2 计算下列计算下列(xili)(xili)排列的逆序数，并讨排列的逆序数，并讨论它们的奇偶性

4、论它们的奇偶性. .;217986354)1(解解453689712544310010)217986354(t18 此排列此排列(pili)(pili)为偶排列为偶排列(pili).(pili).54 0100134 第4页/共11页第五页，共11页。;321)2)(1()2( nnn解解12 ,2)1( nn时为偶排列，时为偶排列，当当14,4 kkn)1( nt)2( n321)2)(1( nnn1 n 2 n.34, 24时为奇排列时为奇排列当当 kkn第5页/共11页第六页，共11页。.)1()32(3)22(2)12( 1 )2()3(kkkkkk 解解0 t kkk 2)1)(11

5、(2,2k 当当k为偶数为偶数(u sh)时时, 排列为偶排排列为偶排列，列，当当k为奇数为奇数(j sh)时时, 排列为奇排列排列为奇排列.1 1 2 kkk )1()1(2kkkkkk)1()32(3)22(2)12(1)2( 0 1 1 2 2 k第6页/共11页第七页，共11页。.对换对换个元素对换，叫做相邻个元素对换，叫做相邻将相邻两将相邻两的手续叫做对换的手续叫做对换不动，这种作出新排列不动，这种作出新排列元素对调，其余的元素元素对调，其余的元素在排列中，将任意两个在排列中，将任意两个对换对换(du hun)的定义的定义对对 换换第7页/共11页第八页，共11页。定理定理(dngl

6、)1.变奇偶性变奇偶性元素对换，排列改元素对换，排列改一个排列中的任意两个一个排列中的任意两个证证.先证相邻对换的情形先证相邻对换的情形，这排列为这排列为mlbabbaa11对换并不改变，这些元素的逆序数经过，；，显然，mlbbaa11.11mlbbabaaba，变为，变为与与对换对换：两元素的逆序数改变为两元素的逆序数改变为，而而ba的逆序数不变；的逆序数不变；而而的逆序数增加的逆序数增加时，经对换后时，经对换后当当baba, 1 . 1,的逆序数减少的逆序数减少的逆序数不变的逆序数不变时，经对换后时，经对换后当当baba 1)()(原新即1)()(新原即第8页/共11页第九页，共11页。.

7、1111的奇偶性不同的奇偶性不同与排列与排列所以排列所以排列mlmlbbabaababbaa.再证一般对换的情形再证一般对换的情形，设排列为设排列为nmlcbcbabaa111，次相邻对换，变成次相邻对换，变成把它作把它作nmlccbabbaam111.1111nmlcacbbbaam次相邻对换，变成次相邻对换，变成再作再作 ，变成排列变成排列次相邻对换，排列次相邻对换，排列总之，经总之，经nmlnmlcacbbbaacbcbabaam11111112 .性相反性相反所以这两个排列的奇偶所以这两个排列的奇偶第9页/共11页第十页，共11页。. 数对换次数为偶偶排列变成标准排列的对换次数为奇数，奇排列变成标准排列的推论推论(tuln)1：的奇偶性，知每次对换都改变排列由定理1证：证：.)0(，因此知推论成立逆序数为排列偶而标准排列是推论推论2 2：n n元排列元