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

1、2 全排列及其逆序數(shù)全排列及其逆序數(shù)全排列的概念全排列的概念 逆序的概念逆序的概念 計算排列逆序數(shù)的方法計算排列逆序數(shù)的方法下頁關(guān)閉 由于對角線法則只適用于二、三由于對角線法則只適用于二、三階行列式，為研究四階及更高階的行階行列式，為研究四階及更高階的行列式，必須用到逆序數(shù)的概念。本節(jié)列式，必須用到逆序數(shù)的概念。本節(jié)主要介紹全排列的概念以及逆序數(shù)的主要介紹全排列的概念以及逆序數(shù)的求法。求法。用用1 1、2 2、3 3三個數(shù)字，可以組成多少個沒有重三個數(shù)字，可以組成多少個沒有重引例引例 解解總共有總共有3 32 21= 1= 6 6種種放法。放法。123123， 132132， 213213，

2、231231， 312312， 321321。這這6 6個不同的三位數(shù)是：個不同的三位數(shù)是：復(fù)數(shù)字的三位數(shù)？復(fù)數(shù)字的三位數(shù)？上頁下頁返回在數(shù)學(xué)中，把考察的對象叫做在數(shù)學(xué)中，把考察的對象叫做元素元素。全排列的概念全排列的概念于是引例可抽象成：把于是引例可抽象成：把 3 個不同的元素排成一列，個不同的元素排成一列，共有幾種不同的排法？共有幾種不同的排法？ 一般地，我們可以討論一般地，我們可以討論“把把 n 個元素排成一列，共個元素排成一列，共有幾種不同的排法有幾種不同的排法”的問題。的問題。上頁下頁返回 定義定義 把把 n 個不同的元素排成一列，叫做這個不同的元素排成一列，叫做這 n 個元素的個元

3、素的全排列全排列（簡稱（簡稱排列排列）。）。 n 個不同元素的所有排列的種數(shù)，通常用個不同元素的所有排列的種數(shù)，通常用 Pn表表示。示。例如例如, , 引例的結(jié)果是引例的結(jié)果是 P3=3=32 21=61=6。上頁下頁返回 首先從首先從 n 個元素中任取一個放在第一個位置上，個元素中任取一個放在第一個位置上，有有 n 種取法；種取法； 又從剩下的又從剩下的 n1 1 個元素中任取一個放在第二個元素中任取一個放在第二個位置上，有個位置上，有 n1 1 種取法；種取法； 這樣繼續(xù)下去，直到最后只剩下一個元素放在這樣繼續(xù)下去，直到最后只剩下一個元素放在第第 n 個位置上，只有種取法。個位置上，只有種

4、取法。計算計算 Pn 的公式：的公式：上頁下頁返回于是于是 n 個元素全排列的個元素全排列的總數(shù)總數(shù)是：是：!12)1(nnnPn 例如例如;241234! 44 P.12012345! 55 P上頁下頁返回 對于對于 n 個不同的元素，規(guī)定各元素之間有一個個不同的元素，規(guī)定各元素之間有一個標(biāo)準(zhǔn)次序標(biāo)準(zhǔn)次序（例如（例如 n 個不同的自然數(shù)，可以規(guī)定個不同的自然數(shù)，可以規(guī)定由小由小到大到大為標(biāo)準(zhǔn)次序）。為標(biāo)準(zhǔn)次序）。 在這在這 n 個元素的任一排列中，當(dāng)某兩個元素的個元素的任一排列中，當(dāng)某兩個元素的先后次序與標(biāo)準(zhǔn)次序不同先后次序與標(biāo)準(zhǔn)次序不同時，就說有時，就說有1 1個逆序個逆序。逆序的概念與全

5、排列的分類逆序的概念與全排列的分類 一個排列中所有逆序的總數(shù)叫做這個排列的一個排列中所有逆序的總數(shù)叫做這個排列的逆逆序數(shù)序數(shù)。上頁下頁返回偶排列：偶排列：逆序數(shù)為偶數(shù)的排列逆序數(shù)為偶數(shù)的排列 顯然，排列的逆序數(shù)為非負(fù)整數(shù)，因此按數(shù)的顯然，排列的逆序數(shù)為非負(fù)整數(shù)，因此按數(shù)的一個分類得到：一個分類得到：排列分類排列分類 奇排列：奇排列：逆序數(shù)為奇數(shù)的排列逆序數(shù)為奇數(shù)的排列上頁下頁返回 不妨設(shè)不妨設(shè) n 個元素為個元素為 1 1 至至 n 這這 n 個自然數(shù)，并個自然數(shù)，并規(guī)定規(guī)定由小到大由小到大為標(biāo)準(zhǔn)次序。為標(biāo)準(zhǔn)次序。設(shè)設(shè) 為這為這 n 個自然數(shù)的一個排列。個自然數(shù)的一個排列。nppp21方法一方

6、法一在排列在排列nppp21中，直接找出次序顛中，直接找出次序顛倒了的元素對的個數(shù)，這也就是該排列的逆序數(shù)。倒了的元素對的個數(shù)，這也就是該排列的逆序數(shù)。例例1判斷排列判斷排列2341的奇偶性。的奇偶性。解解 在排列在排列2341中，構(gòu)成逆序的數(shù)對有中，構(gòu)成逆序的數(shù)對有21, 31, 41,故排列故排列2341的逆序數(shù)的逆序數(shù). 3 t所以所以2341是奇排列。是奇排列。計算排列的逆序數(shù)的方法計算排列的逆序數(shù)的方法上頁下頁返回方法二方法二nppp21在排列在排列中，中， 如果比如果比,n),(ipi21 大的且排在大的且排在ip前面的元素有前面的元素有it則這個排列的則這個排列的逆序逆序數(shù)數(shù)是是.121 niinttttt個，個，上頁下頁返回求排列求排列3251432514的逆序數(shù)。的逆序數(shù)。解解01t12t03t34t15t于是排列的于是排列的總逆序數(shù)總逆序數(shù)為為. 513010 t例例3上頁下頁返回3 2 5 1 43 2 5 1 4Ex.2求排列求排列1 3 5 7 9 10 8 6 4 2的逆序數(shù)。的逆序數(shù)。解解208642000000 tEx.3 求求ji,使使9561274ji成為偶排列。成為偶排列。解解