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

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

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

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

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

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

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