線性代數(shù)排列與逆序2023/4/231第1頁，共20頁，2023年，2月20日，星期六一、概念的引入引例用1、2、3三個數(shù)字，可以組成多少個沒有重復(fù)數(shù)字的三位數(shù)？解123123百位3種放法十位1231個位1232種放法1種放法種放法.共有2023/4/232第2頁，共20頁，2023年，2月20日，星期六二、全排列及其逆序數(shù)問題把n個不同的元素排成一列，共有幾種不同的排法？2023/4/233第3頁，共20頁，2023年，2月20日，星期六定義1.1把個不同的元素排成一列，叫做這個元素的全排列（或排列）.通常用表示.

個不同的元素的所有排列的種數(shù)，由引例同理2023/4/234第4頁，共20頁，2023年，2月20日，星期六

我們規(guī)定各元素之間有一個標(biāo)準(zhǔn)次序,n個不同的自然數(shù)，規(guī)定由小到大為標(biāo)準(zhǔn)次序.排列的逆序數(shù)2023/4/235第5頁，共20頁，2023年，2月20日，星期六

在一個排列中，若數(shù),則稱這兩個數(shù)組成一個逆序.例如排列32514中，定義1.232514逆序逆序逆序2023/4/236第6頁，共20頁，2023年，2月20日，星期六一個排列中所有逆序的總數(shù)稱為此排列的逆序數(shù).例如排列32514中，

32514逆序數(shù)為31故此排列的逆序數(shù)為3+1+0+1+0=5.定義1.3

2023/4/237第7頁，共20頁，2023年，2月20日，星期六逆序數(shù)為奇數(shù)的排列稱為奇排列;逆序數(shù)為偶數(shù)的排列稱為偶排列.排列的奇偶性2023/4/238第8頁，共20頁，2023年，2月20日，星期六分別計算出排在前面比它大的數(shù)碼之和即分別算出這個元素的逆序數(shù)，這些元素的逆序數(shù)的總和即為所求排列的逆序數(shù).方法1三、計算排列逆序數(shù)的方法2023/4/239第9頁，共20頁，2023年，2月20日，星期六分別計算出排列中每個元素前面比它大的數(shù)碼個數(shù)之和，即算出排列中每個元素的逆序數(shù)，這些元素的逆序數(shù)之總和即為所求排列的逆序數(shù).方法22023/4/2310第10頁，共20頁，2023年，2月20日，星期六分別計算出排列中每個元素后面比它小的數(shù)碼個數(shù)之和，即算出排列中每個元素的逆序數(shù)，這些元素的逆序數(shù)之總和即為所求排列的逆序數(shù).方法32023/4/2311第11頁，共20頁，2023年，2月20日，星期六例求排列32514的逆序數(shù).解在排列32514中,3排在首位,逆序數(shù)為0;2的前面比2大的數(shù)只有一個3,故逆序數(shù)為1;2023/4/2312第12頁，共20頁，2023年，2月20日，星期六32514于是排列32514的逆序數(shù)為5的前面沒有比5大的數(shù),其逆序數(shù)為0;1的前面比1大的數(shù)有3個,故逆序數(shù)為3;4的前面比4大的數(shù)有1個,故逆序數(shù)為1;2023/4/2313第13頁，共20頁，2023年，2月20日，星期六

計算下列排列的逆序數(shù)，并討論它們的奇偶性.解此排列為偶排列.例2023/4/2314第14頁，共20頁，2023年，2月20日，星期六解當(dāng)時為偶排列；當(dāng)時為奇排列.2023/4/2315第15頁，共20頁，2023年，2月20日，星期六解當(dāng)為偶數(shù)時，排列為偶排列，當(dāng)為奇數(shù)時，排列為奇排列.2023/4/2316第16頁，共20頁，2023年，2月20日，星期六練習(xí)求i，j使25i4j1為偶排列。解6元排列使i、j只能取3或6；由于所以，i=6,j=3。奇排列偶排列（偶數(shù)）2023/4/2317第17頁，共20頁，2023年，2月20日，星期六2排列具有奇偶性.3計算排列逆序數(shù)常用的方法有2種.1個不同的元素的所有排列種數(shù)為四、小結(jié)與思考2023/4/2318第18頁，共20頁，2023年，2月20日，星期六思考題分別用兩種方法求排列16352487的逆序數(shù).2023/4/2319第19頁，共20頁，2023年，2