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

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

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

3、nstiiiii21stii 例如例如 排列排列32514 中，中， 1. 定義定義 我們規(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ù)在小的數(shù)左邊，則這兩數(shù)構(gòu)成一個(gè)逆序）即：大的數(shù)在小的數(shù)左邊，則這兩數(shù)構(gòu)成一個(gè)逆序）三、排列的逆序數(shù)三、排列的逆序數(shù)例如例如 排列排列32514 中，中， 在一個(gè)排列在一個(gè)排列 中中, 若數(shù)若數(shù) 則稱這兩個(gè)數(shù)組成一個(gè)逆序則稱這兩個(gè)數(shù)組成一個(gè)逆序.nstppppp21,stpp 1. 定義定義 我們規(guī)定各元素

4、之間有一個(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ù)在小的數(shù)左邊，則這兩數(shù)構(gòu)成一個(gè)逆序）即：大的數(shù)在小的數(shù)左邊，則這兩數(shù)構(gòu)成一個(gè)逆序）2. 定義定義 一個(gè)排列中所有逆序的總數(shù)稱為此排一個(gè)排列中所有逆序的總數(shù)稱為此排列的列的逆序數(shù)逆序數(shù). .例如例如 排列排列 32514 中，中， 3. 3. 排列的奇偶性排列的奇偶性逆序數(shù)為奇數(shù)的排列稱為逆序數(shù)為奇數(shù)的排列稱為奇排列奇排列; ;逆序數(shù)為偶數(shù)的排列稱為逆序數(shù)為偶數(shù)的排列稱為偶排列偶排列. .4.4.計(jì)算排列

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