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

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

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

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

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

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

6、法一在排列在排列nppp21中，直接找出次序顛中，直接找出次序顛倒了的元素對(duì)的個(gè)數(shù)，這也就是該排列的逆序數(shù)。倒了的元素對(duì)的個(gè)數(shù)，這也就是該排列的逆序數(shù)。例例1判斷排列判斷排列2341的奇偶性。的奇偶性。解解 在排列在排列2341中，構(gòu)成逆序的數(shù)對(duì)有中，構(gòu)成逆序的數(shù)對(duì)有21, 31, 41,故排列故排列2341的逆序數(shù)的逆序數(shù). 3 t所以所以2341是奇排列。是奇排列。計(jì)算排列的逆序數(shù)的方法計(jì)算排列的逆序數(shù)的方法上頁(yè)下頁(yè)返回方法二方法二nppp21在排列在排列中，中， 如果比如果比,n),(ipi21 大的且排在大的且排在ip前面的元素有前面的元素有it則這個(gè)排列的則這個(gè)排列的逆序逆序數(shù)數(shù)是是.121 niinttttt個(gè)，個(gè)，上頁(yè)下頁(yè)返回求排列求排列3251432514的逆序數(shù)。的逆序數(shù)。解解01t12t03t34t15t于是排列的于是排列的總逆序數(shù)總逆序數(shù)為為. 513010 t例例3上頁(yè)下頁(yè)返回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成為偶排列。成為偶排列。解解