線性代數(shù)排列及其逆序數(shù)學(xué)習(xí)教案

1、線性代數(shù)線性代數(shù)(xin xn di sh) 排列及其逆排列及其逆序數(shù)序數(shù)第一頁，共13頁。第1頁/共13頁第二頁，共13頁。定定義義(dngy)排列排列(pili)的逆序數(shù)的逆序數(shù) 在一個(gè)排列在一個(gè)排列 中，若中，若數(shù)數(shù) 則稱這兩個(gè)數(shù)組成一個(gè)逆序則稱這兩個(gè)數(shù)組成一個(gè)逆序. nstiiiii21stii 例如例如(lr) 排列排列32514 中，中， 我們規(guī)定各元素之間有一個(gè)標(biāo)準(zhǔn)次序我們規(guī)定各元素之間有一個(gè)標(biāo)準(zhǔn)次序, n 個(gè)不同個(gè)不同的自然數(shù)，規(guī)定由小到大為的自然數(shù)，規(guī)定由小到大為標(biāo)準(zhǔn)次序標(biāo)準(zhǔn)次序.3 2 5 1 4逆序逆序逆序逆序逆序逆序二、排列的逆序數(shù)第2頁/共13頁第三頁，共13頁。定義

2、定義 一個(gè)排列中所有逆序的總數(shù)一個(gè)排列中所有逆序的總數(shù)(zngsh)稱稱為此排列為此排列 的逆序數(shù)的逆序數(shù).例如例如(lr) 排列排列32514 中，中， 3 2 5 1 4逆序數(shù)逆序數(shù)(xsh)為為31010故此排列的故此排列的逆序數(shù)為逆序數(shù)為3+1+0+1+0=5.第3頁/共13頁第四頁，共13頁。1 1、用多種方法、用多種方法(fngf)(fngf)求排列求排列1635248716352487的逆序的逆序數(shù)數(shù). .2 2、的取值范圍？、的取值范圍？3 3、求、求n(n-1) 21n(n-1) 21的逆序數(shù)。的逆序數(shù)。4 4、若求、若求)(21nii it1 2()ni iit 2 1()

3、nii i 第4頁/共13頁第五頁，共13頁。逆序數(shù)為奇數(shù)逆序數(shù)為奇數(shù)(j sh)的排列稱為奇排列的排列稱為奇排列;逆序數(shù)為偶數(shù)逆序數(shù)為偶數(shù)(u sh)的排列稱為偶排列的排列稱為偶排列.排列排列(pili)的奇偶性的奇偶性第5頁/共13頁第六頁，共13頁。定義定義(dngy)在排列中，將任意兩個(gè)元素在排列中，將任意兩個(gè)元素(yun s)對(duì)調(diào)，對(duì)調(diào)，其余元素其余元素(yun s)不動(dòng)，這種作出新排列不動(dòng)，這種作出新排列的手續(xù)叫做對(duì)換的手續(xù)叫做對(duì)換將相鄰兩個(gè)元素對(duì)調(diào)，叫做將相鄰兩個(gè)元素對(duì)調(diào)，叫做相鄰對(duì)換相鄰對(duì)換mlbbbaaa11例如例如bamlbbabaa11abnmlccbbbaaa111nm

4、lccabbbaa111baab第6頁/共13頁第七頁，共13頁。定理定理1 1一個(gè)排列一個(gè)排列(pili)(pili)中的任意兩個(gè)元素對(duì)中的任意兩個(gè)元素對(duì)換，排列換，排列(pili)(pili)改變奇偶性改變奇偶性證明證明(zhngmng)設(shè)排列為設(shè)排列為mlbbabaa11對(duì)換對(duì)換 與與abmlbbbaaa11除除 外，其它元素的逆序數(shù)不改變外，其它元素的逆序數(shù)不改變.b,aabba第7頁/共13頁第八頁，共13頁。當(dāng)當(dāng) 時(shí)，時(shí)，ba ab的逆序數(shù)不變的逆序數(shù)不變;經(jīng)對(duì)換后經(jīng)對(duì)換后 的逆序數(shù)增加的逆序數(shù)增加1 ,經(jīng)對(duì)換后經(jīng)對(duì)換后 的逆序數(shù)不變的逆序數(shù)不變 ， 的逆序數(shù)減少的逆序數(shù)減少1.a

5、b因此對(duì)換因此對(duì)換(du hun)相鄰兩個(gè)元素，排列改變奇偶性相鄰兩個(gè)元素，排列改變奇偶性.設(shè)排列設(shè)排列(pili)為為nmlcbcbabaa111當(dāng)當(dāng) 時(shí)，時(shí)，ba 現(xiàn)來對(duì)換現(xiàn)來對(duì)換 與與a.b第8頁/共13頁第九頁，共13頁。次相鄰對(duì)換次相鄰對(duì)換mnmlccbbabaa111次相鄰對(duì)換次相鄰對(duì)換1 mnmlccabbbaa111,111nmlcbcbabaa次相鄰對(duì)換次相鄰對(duì)換12 m,111nmlcacbbbaa所以一個(gè)排列中的任意兩個(gè)元素對(duì)換所以一個(gè)排列中的任意兩個(gè)元素對(duì)換(du hun)，排列改變，排列改變奇偶性奇偶性.abnmlccbbbaaa111abab第9頁/共13頁第十頁，共13頁。推論推論(tuln)奇排列調(diào)成標(biāo)準(zhǔn)排列的對(duì)換次數(shù)奇排列調(diào)成標(biāo)準(zhǔn)排列的對(duì)換次數(shù)(csh)(csh)為奇數(shù)，為奇數(shù)，偶排列調(diào)成標(biāo)準(zhǔn)排列的對(duì)換次數(shù)偶排列調(diào)成標(biāo)準(zhǔn)排列的對(duì)換次數(shù)(csh)(csh)為偶數(shù)為偶數(shù). .定理定理2 2 在全部在全部 階排列階排列(pili)(pili)中中 , ,奇偶排奇偶排列列(pili)(pili)各各 占一半占一半. . n 2 n第10頁/共13頁第十一頁，共13頁。2 2 排列排列(pili)(pili)具有奇偶性具有奇偶性. .3 計(jì)算排列計(jì)算排列(pili)逆序數(shù)常用的方法有多種逆序數(shù)常用的方法有多種.1 1