線性代數(shù)全排列與逆序數(shù)PPT課件

1、.個元素的（全）排列個元素的（全）排列這這做做不同元素排成一列，叫不同元素排成一列，叫個個把把象，叫做元素象，叫做元素在數(shù)學(xué)中，把考察的對在數(shù)學(xué)中，把考察的對nn。元排列為記npppn21列）組成的排列稱為自然排定由小到大為標準次序規(guī)個不同的自然數(shù)（如次序各元素之間有一個標準個不同的元素，先規(guī)定對于,nn.時，就說有一個逆序次序于標準次序不同后當(dāng)某兩個元素的先個元素的任意排列中，于是在這n.序數(shù)總和叫做這個排列的逆一個排列中所有逆序的的逆序數(shù)記為元排列npppn21)(21nppp第1頁/共11頁例例1求排列求排列32514的逆序數(shù)的逆序數(shù).解解在排列在排列32514中，中，3排在首位，逆序數(shù)

2、為排在首位，逆序數(shù)為 0；2前面比前面比2大的數(shù)有一個（大的數(shù)有一個（3），故逆序數(shù)為），故逆序數(shù)為1；5是最大數(shù)，逆序數(shù)為是最大數(shù)，逆序數(shù)為 0；1前面比前面比1大的數(shù)有三個（大的數(shù)有三個（3、2、5）,故逆序數(shù)為故逆序數(shù)為3；4前面比前面比4大的數(shù)有一個（大的數(shù)有一個（5），故逆序數(shù)為），故逆序數(shù)為1；于是這個排列的逆序數(shù)為于是這個排列的逆序數(shù)為. 513010)32514(.偶排列序數(shù)為偶數(shù)的排列叫做逆做奇排列，逆序數(shù)為奇數(shù)的排列叫.表示的種數(shù)，通常用個不同元素的所有排列nPn!123) 1(nnnPn第2頁/共11頁:法法計算排列的逆序數(shù)的方計算排列的逆序數(shù)的方., 121即是這個排列

3、的逆序數(shù)即是這個排列的逆序數(shù)之和之和全體元素的逆序數(shù)全體元素的逆序數(shù) niinttttt個自然數(shù)的一個排列，為設(shè)npppn21個，個，前面的元素有前面的元素有大的且排在大的且排在如果比如果比iiitpp.iitp 這個元素的逆序數(shù)為這個元素的逆序數(shù)為就是說就是說，、考慮元素考慮元素)21(nipi 第3頁/共11頁例例2 2 計算下列排列的逆序數(shù)，并討論它們的計算下列排列的逆序數(shù)，并討論它們的奇偶性奇偶性. .;217986354)1(解解453689712544310010)217986354(t18 此排列為偶排列此排列為偶排列. .54 0100134 第4頁/共11頁;321)2)(1

4、()2( nnn解解12 ,2)1( nn時為偶排列，時為偶排列，當(dāng)當(dāng)14,4 kkn)1( nt)2( n321)2)(1( nnn1 n 2 n.34, 24時為奇排列時為奇排列當(dāng)當(dāng) kkn第5頁/共11頁.)1()32(3)22(2)12( 1 )2()3(kkkkkk 解解0 t kkk 2)1)(11(2,2k 當(dāng)k為偶數(shù)時, 排列為偶排列，當(dāng)k為奇數(shù)時, 排列為奇排列.1 1 2 kkk )1()1(2kkkkkk)1()32(3)22(2)12(1)2( 0 1 1 2 2 k第6頁/共11頁.對換對換個元素對換，叫做相鄰個元素對換，叫做相鄰將相鄰兩將相鄰兩的手續(xù)叫做對換的手續(xù)叫

5、做對換不動，這種作出新排列不動，這種作出新排列元素對調(diào)，其余的元素元素對調(diào)，其余的元素在排列中，將任意兩個在排列中，將任意兩個對換對換的定義的定義對對 換換第7頁/共11頁定理定理1.變奇偶性變奇偶性元素對換，排列改元素對換，排列改一個排列中的任意兩個一個排列中的任意兩個證證.先證相鄰對換的情形先證相鄰對換的情形，這排列為這排列為mlbabbaa11對換并不改變，這些元素的逆序數(shù)經(jīng)過，；，顯然，mlbbaa11.11mlbbabaaba，變?yōu)椋優(yōu)榕c與對換對換：兩元素的逆序數(shù)改變?yōu)閮稍氐哪嫘驍?shù)改變?yōu)?，而而ba的逆序數(shù)不變；的逆序數(shù)不變；而而的逆序數(shù)增加的逆序數(shù)增加時，經(jīng)對換后時，經(jīng)對換后當(dāng)當(dāng)

6、baba, 1 . 1,的逆序數(shù)減少的逆序數(shù)減少的逆序數(shù)不變的逆序數(shù)不變時，經(jīng)對換后時，經(jīng)對換后當(dāng)當(dāng)baba 1)()(原新即1)()(新原即第8頁/共11頁.1111的奇偶性不同的奇偶性不同與排列與排列所以排列所以排列mlmlbbabaababbaa.再證一般對換的情形再證一般對換的情形，設(shè)排列為設(shè)排列為nmlcbcbabaa111，次相鄰對換，變成次相鄰對換，變成把它作把它作nmlccbabbaam111.1111nmlcacbbbaam次相鄰對換，變成次相鄰對換，變成再作再作 ，變成排列變成排列次相鄰對換，排列次相鄰對換，排列總之，經(jīng)總之，經(jīng)nmlnmlcacbbbaacbcbabaam11111112 .性相反性相反所以這兩個排列的奇偶所以這兩個排列的奇偶第9頁/共11頁. 數(shù)對換次數(shù)為偶偶排列變成標準排列的對換次數(shù)為奇數(shù)，奇排列變成標準排列的推論推論1：的奇偶性，知每次對換都改變排列由定理1證：證：.)0(，因此知推論成