全排列及其逆序數(shù)

1、2 全全排列及其逆序數(shù)排列及其逆序數(shù)一、概念的引入一、概念的引入二、全二、全排列排列四、小結(jié)四、小結(jié)三、三、排列逆序數(shù)排列逆序數(shù)一、概念的引入一、概念的引入引例引例用用1、2、3三個數(shù)字，可以組成多少個沒三個數(shù)字，可以組成多少個沒有重復數(shù)字的三位數(shù)？有重復數(shù)字的三位數(shù)？解解1 2 3123百位百位十位十位1231個位個位12 3種放法種放法.共有共有6123 二、全二、全排列排列問題問題同的排法？同的排法？，共有幾種不，共有幾種不個不同的元素排成一列個不同的元素排成一列把把 n定義定義把把 個不同的元素排成一列，叫做這個不同的元素排成一列，叫做這 個個元素的全排列（或排列）元素的全排列（或排列

2、）.nn 個不同的元素的所有排列的種數(shù)，通常個不同的元素的所有排列的種數(shù)，通常用用 表示表示.nnP由引例由引例1233 P. 6 nPn )1( n)2( n123 !.n 同理同理1. 由由1,2,n-1,n（n個數(shù)）組成的一個全排列稱個數(shù)）組成的一個全排列稱 為一個為一個n級排列級排列。如：如：1234512345，5432154321，4351243512均為均為5 5級排列級排列2. 2. 123(123(n-1)-1)n( (具有自然順序的排列為具有自然順序的排列為) )標準排列標準排列。 在一個排列在一個排列 中，若數(shù)中，若數(shù) 則稱這兩個數(shù)組成一個逆序則稱這兩個數(shù)組成一個逆序.

3、nstiiiii21stii 例如例如 排列排列32514 中，中， 1. 定義定義 我們規(guī)定各元素之間有一個標準次序我們規(guī)定各元素之間有一個標準次序, n 個個不同的自然數(shù)，規(guī)定由小到大為不同的自然數(shù)，規(guī)定由小到大為標準次序標準次序.3 2 5 1 4逆序逆序逆序逆序逆序逆序( (即：大的數(shù)在小的數(shù)左邊，則這兩數(shù)構(gòu)成一個逆序）即：大的數(shù)在小的數(shù)左邊，則這兩數(shù)構(gòu)成一個逆序）三、排列的逆序數(shù)三、排列的逆序數(shù)例如例如 排列排列32514 中，中， 在一個排列在一個排列 中中, 若數(shù)若數(shù) 則稱這兩個數(shù)組成一個逆序則稱這兩個數(shù)組成一個逆序.nstppppp21,stpp 1. 定義定義 我們規(guī)定各元素

4、之間有一個標準次序我們規(guī)定各元素之間有一個標準次序, n 個個不同的自然數(shù)，規(guī)定由小到大為不同的自然數(shù)，規(guī)定由小到大為標準次序標準次序.3 2 5 1 4逆序逆序逆序逆序逆序逆序( (即：大的數(shù)在小的數(shù)左邊，則這兩數(shù)構(gòu)成一個逆序）即：大的數(shù)在小的數(shù)左邊，則這兩數(shù)構(gòu)成一個逆序）2. 定義定義 一個排列中所有逆序的總數(shù)稱為此排一個排列中所有逆序的總數(shù)稱為此排列的列的逆序數(shù)逆序數(shù). .例如例如 排列排列 32514 中，中， 3. 3. 排列的奇偶性排列的奇偶性逆序數(shù)為奇數(shù)的排列稱為逆序數(shù)為奇數(shù)的排列稱為奇排列奇排列; ;逆序數(shù)為偶數(shù)的排列稱為逆序數(shù)為偶數(shù)的排列稱為偶排列偶排列. .4.4.計算排列

5、逆序數(shù)的方法計算排列逆序數(shù)的方法設(shè)排列為設(shè)排列為 ,21npppit為為ip構(gòu)成的逆序數(shù)構(gòu)成的逆序數(shù)則其逆序數(shù)為則其逆序數(shù)為121)(21 nppptttNtn例例1 1 求排列求排列 32514 的逆序數(shù)的逆序數(shù).例例2 2 計算下列排列的逆序數(shù)，并討論它們的計算下列排列的逆序數(shù)，并討論它們的 奇偶性奇偶性. 2179863541 321212 nnn分別計算出排列中每個元素前面比它大的數(shù)分別計算出排列中每個元素前面比它大的數(shù)碼個數(shù)之和，即算出排列中每個元素的逆序數(shù)，碼個數(shù)之和，即算出排列中每個元素的逆序數(shù)，每個元素的逆序數(shù)之總和即為所求排列的逆序數(shù)每個元素的逆序數(shù)之總和即為所求排列的逆序數(shù)2 2 排列具有奇偶性排列具有奇偶性. .3 計算排列逆序數(shù)常用的方法計算排列逆序數(shù)常用的方法.1 1 個不同的元素的所有排列種數(shù)為個不同的元素的所有排列種數(shù)為n!.n四、小結(jié)四、小結(jié)分別用兩種方法求排列分別用兩種方法求排列16352487的逆序數(shù)的逆序數(shù).思考題解答思考題解