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

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

2、數(shù)，通常用用 表示表示.nnP由引例由引例1233 P. 6 nPn )1( n)2( n123 !.n 同理同理 在一個(gè)排列在一個(gè)排列 中，若數(shù)中，若數(shù) 則稱(chēng)這兩個(gè)數(shù)組成一個(gè)逆序則稱(chēng)這兩個(gè)數(shù)組成一個(gè)逆序. nstiiiii21stii 例如例如 排列排列32514 中，中， 定義定義 我們規(guī)定各元素之間有一個(gè)標(biāo)準(zhǔn)次序我們規(guī)定各元素之間有一個(gè)標(biāo)準(zhǔn)次序, n 個(gè)個(gè)不同的自然數(shù)，規(guī)定由小到大為標(biāo)準(zhǔn)次序不同的自然數(shù)，規(guī)定由小到大為標(biāo)準(zhǔn)次序.排列的逆序數(shù)排列的逆序數(shù)3 2 5 1 4逆序逆序逆序逆序逆序逆序定義定義 一個(gè)排列中所有逆序的總數(shù)稱(chēng)為此排列的一個(gè)排列中所有逆序的總數(shù)稱(chēng)為此排列的逆序數(shù)逆序數(shù).

3、例如例如 排列排列32514 中，中， 3 2 5 1 4逆序數(shù)為逆序數(shù)為31010故此排列的逆序數(shù)為故此排列的逆序數(shù)為3+1+0+1+0=5.計(jì)算排列逆序數(shù)的方法計(jì)算排列逆序數(shù)的方法方法方法1 1分別計(jì)算出排在分別計(jì)算出排在 前面比它大的數(shù)前面比它大的數(shù)碼之和即分別算出碼之和即分別算出 這這 個(gè)元素個(gè)元素的逆序數(shù)，這個(gè)元素的逆序數(shù)的總和即為所求的逆序數(shù)，這個(gè)元素的逆序數(shù)的總和即為所求排列的逆序數(shù)排列的逆序數(shù).n,n,121 n,n,121 n逆序數(shù)為奇數(shù)的排列稱(chēng)為奇排列逆序數(shù)為奇數(shù)的排列稱(chēng)為奇排列;逆序數(shù)為偶數(shù)的排列稱(chēng)為偶排列逆序數(shù)為偶數(shù)的排列稱(chēng)為偶排列.排列的奇偶性排列的奇偶性分別計(jì)算出排

4、列中每個(gè)元素前面比它大的數(shù)碼分別計(jì)算出排列中每個(gè)元素前面比它大的數(shù)碼個(gè)數(shù)之和，即算出排列中每個(gè)元素的逆序數(shù)，個(gè)數(shù)之和，即算出排列中每個(gè)元素的逆序數(shù)，這每個(gè)元素的逆序數(shù)之總和即為所求排列的逆這每個(gè)元素的逆序數(shù)之總和即為所求排列的逆序數(shù)序數(shù).方法方法2 2例例1 1 求排列求排列3251432514的逆序數(shù)的逆序數(shù). .解解在排列在排列32514中中,3排在首位排在首位,逆序數(shù)為逆序數(shù)為0;2的前面比的前面比2大的數(shù)只有一個(gè)大的數(shù)只有一個(gè)3,故逆序數(shù)為故逆序數(shù)為1;3 2 5 1 40 1 0 3 1于是排列于是排列32514的逆序數(shù)為的逆序數(shù)為13010 t. 5 5的前面沒(méi)有比的前面沒(méi)有比5大

5、的數(shù)大的數(shù),其逆序數(shù)為其逆序數(shù)為0;1的前面比的前面比1大的數(shù)有大的數(shù)有3個(gè)個(gè),故逆序數(shù)為故逆序數(shù)為3;4的前面比的前面比4大的數(shù)有大的數(shù)有1個(gè)個(gè),故逆序數(shù)為故逆序數(shù)為1;例例2 2 計(jì)算下列排列的逆序數(shù)，并討論它們的計(jì)算下列排列的逆序數(shù)，并討論它們的奇偶性奇偶性. . 2179863541解解453689712544310010 t18 此排列為偶排列此排列為偶排列.54 0100134 321212 nnn解解12 ,21 nn當(dāng)當(dāng) 時(shí)為偶排列；時(shí)為偶排列；14 ,4 kkn當(dāng)當(dāng) 時(shí)為奇排列時(shí)為奇排列.34 , 24 kkn 1 nt 2 n 32121 nnn kkkkkk132322212123 解解0 t kkk 21112,2k 當(dāng)當(dāng) 為偶數(shù)時(shí)，排列為偶排列，為偶數(shù)時(shí)，排列為偶排列，k當(dāng)當(dāng) 為奇數(shù)時(shí)，排列為奇排列為奇數(shù)時(shí)，排列為奇排列.k1 1 2 kkk 112 kkkkk0 1 1 2 2 k2 2 排列具有奇偶性排列具有奇偶性. .3 計(jì)算排列逆序數(shù)常用的方法有計(jì)算排列逆序數(shù)常用的方法有2 種種.1 1 個(gè)不同的元素的所有排列種數(shù)為個(gè)不同的元素的所有排列種數(shù)為n!.n三、小結(jié)三、小結(jié)分別用兩種方法求排列分別用兩種方法求排列16352487的逆序數(shù)的逆序數(shù).思考題