線性代數(shù)2.2-排列

1、1/162/16一、排列一、排列定義定義稱為一個(gè)稱為一個(gè) 級(jí)級(jí)排列排列n由由1，2，n 組成的一個(gè)有序數(shù)組組成的一個(gè)有序數(shù)組, ,123，132，213，231，312，321如如: 所有的所有的3級(jí)排列是級(jí)排列是 共共6=3！個(gè)個(gè).n!1 2(1)nnnnP ( (階乘階乘)注：注：所有不同級(jí)排列的總數(shù)是所有不同級(jí)排列的總數(shù)是n3/16二、逆序逆序數(shù)二、逆序逆序數(shù) 我們規(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)次序. .定義定義一個(gè)排列中逆序的一個(gè)排列中逆序的總數(shù)稱為這個(gè)排列的總數(shù)稱為這個(gè)排

2、列的逆序數(shù)逆序數(shù)在一個(gè)排列中，如果一對(duì)數(shù)的前后位置在一個(gè)排列中，如果一對(duì)數(shù)的前后位置與標(biāo)準(zhǔn)次序相反，即前面的數(shù)大于后面的數(shù)，與標(biāo)準(zhǔn)次序相反，即前面的數(shù)大于后面的數(shù)，則稱這對(duì)數(shù)為一個(gè)則稱這對(duì)數(shù)為一個(gè)逆序逆序；4/16 排列排列 123 稱為稱為標(biāo)準(zhǔn)排列標(biāo)準(zhǔn)排列，其逆序數(shù)為其逆序數(shù)為n注：注： 排列排列 的逆序數(shù)常記為的逆序數(shù)常記為1 2().nj jj 1 2nj jj例例1排列排列 31542 中，逆序有中，逆序有(31542)5 31， 32， 54， 52， 425/16求逆序數(shù)的方法求逆序數(shù)的方法 后面比后面比 小的數(shù)的個(gè)數(shù)小的數(shù)的個(gè)數(shù)1 21()nj jjj 1j1nj 后面比后面比

3、小的數(shù)的個(gè)數(shù)小的數(shù)的個(gè)數(shù).1nj 2j 后面比后面比 小的數(shù)的個(gè)數(shù)小的數(shù)的個(gè)數(shù)2j或或前面比前面比 大的數(shù)的個(gè)數(shù)大的數(shù)的個(gè)數(shù)1 22()nj jjj 2j3j 前面比前面比 大的數(shù)的個(gè)數(shù)大的數(shù)的個(gè)數(shù)3j nj 前面比前面比 大的數(shù)的個(gè)數(shù)大的數(shù)的個(gè)數(shù)nj方法一方法一方法二方法二6/16的逆序數(shù)的逆序數(shù). . 例例2求求 級(jí)排列級(jí)排列2n135(21)(2 )(22)42nnn解：解：135(21)(2 )(22)42nnn121n 1n 方法一方法一12(1)(1)21(1)nnn n 17/16逆序數(shù)為奇數(shù)的排列稱為逆序數(shù)為奇數(shù)的排列稱為奇排列奇排列；逆序數(shù)為偶數(shù)的排列稱為逆序數(shù)為偶數(shù)的排列稱

4、為偶排列偶排列三三 、奇排列、偶排列、奇排列、偶排列定義定義標(biāo)準(zhǔn)排列標(biāo)準(zhǔn)排列 123 為偶排列為偶排列n注：注：練習(xí)練習(xí)：求下列排列的逆序數(shù)并討論其奇偶性：求下列排列的逆序數(shù)并討論其奇偶性(1)321n n （1）(2 )1(21)2(22)3(1)nnnnn（2）8/16答案答案:2(1)(1)22n nn nn12(1)(2)21nnn （2）當(dāng)當(dāng) 時(shí)為偶排列；時(shí)為偶排列；4 , 41nkk當(dāng)當(dāng) 時(shí)為奇排列時(shí)為奇排列.42, 43nkk當(dāng)當(dāng) 為偶數(shù)時(shí)為偶排列，為偶數(shù)時(shí)為偶排列，k當(dāng)當(dāng) 為奇數(shù)時(shí)為奇排列為奇數(shù)時(shí)為奇排列.k方法一方法一方法二方法二(1)(1)(1)(2)212n nnn 9/

5、16四四 、對(duì)換、對(duì)換定義定義把一個(gè)排列中某兩個(gè)數(shù)的位置互換，而把一個(gè)排列中某兩個(gè)數(shù)的位置互換，而其余的數(shù)不動(dòng)，得到另一個(gè)排列，這一變換其余的數(shù)不動(dòng)，得到另一個(gè)排列，這一變換稱為一個(gè)稱為一個(gè)對(duì)換對(duì)換將相鄰兩個(gè)元素對(duì)調(diào)，叫做將相鄰兩個(gè)元素對(duì)調(diào)，叫做相鄰對(duì)換相鄰對(duì)換10/16證明證明1) 特殊情形：作相鄰對(duì)換特殊情形：作相鄰對(duì)換mlbbabaa11對(duì)換對(duì)換 與與abmlbbbaaa11除除 外，其它元素所成逆序不改變外，其它元素所成逆序不改變.b,aab對(duì)換改變排列的奇偶性即經(jīng)過一次對(duì)換，對(duì)換改變排列的奇偶性即經(jīng)過一次對(duì)換，奇排列變成偶排列，偶排列變成奇排列奇排列變成偶排列，偶排列變成奇排列定理定

6、理1設(shè)排列為設(shè)排列為11/16當(dāng)當(dāng) 時(shí)，時(shí)，ba ab所成逆序不變所成逆序不變;經(jīng)對(duì)換后經(jīng)對(duì)換后 的逆序增加的逆序增加1個(gè)個(gè) ,經(jīng)對(duì)換后經(jīng)對(duì)換后 所成逆序不變所成逆序不變 ， 的逆序減少的逆序減少1個(gè)個(gè).ab因此對(duì)換相鄰兩個(gè)元素，排列改變奇偶性因此對(duì)換相鄰兩個(gè)元素，排列改變奇偶性.設(shè)排列為設(shè)排列為nmlcbcbabaa111當(dāng)當(dāng) 時(shí)，時(shí)，ba 現(xiàn)來對(duì)換現(xiàn)來對(duì)換 與與a.b2)一般情形一般情形12/16次相鄰對(duì)換次相鄰對(duì)換mnmlccbbabaa111次相鄰對(duì)換次相鄰對(duì)換1 mnmlccabbbaa111,111nmlcbcbabaa次相鄰對(duì)換次相鄰對(duì)換12 m,111nmlcacbbbaa所以

7、一個(gè)排列中的任意兩個(gè)元素對(duì)換，排列改變所以一個(gè)排列中的任意兩個(gè)元素對(duì)換，排列改變奇偶性奇偶性.abnmlccbbbaaa111abab13/16所有所有 級(jí)排列中，奇、偶排列各半，級(jí)排列中，奇、偶排列各半，n!2n均為均為 個(gè)個(gè). 設(shè)在全部設(shè)在全部 階排列中，有階排列中，有 個(gè)奇排列，個(gè)奇排列， 個(gè)個(gè)偶排列，下證偶排列，下證 nstts 將將 個(gè)奇排列的前兩個(gè)數(shù)對(duì)換，則這個(gè)奇排列的前兩個(gè)數(shù)對(duì)換，則這 個(gè)奇排列個(gè)奇排列全變成偶排列，并且它們彼此不同，全變成偶排列，并且它們彼此不同，ss 同理，將同理，將 個(gè)偶排列的前兩個(gè)數(shù)對(duì)換，則這個(gè)偶排列的前兩個(gè)數(shù)對(duì)換，則這 個(gè)個(gè)偶排列全變成奇排列，并且它們彼此不同，偶排列全變成奇排列，并且它們彼此不同，tt推論推論證明證明.st.ts故故!.2nst14/16一系列對(duì)換互換，并且所作對(duì)換的次數(shù)與這個(gè)一系列對(duì)換互換，并且所作對(duì)換的次數(shù)與這個(gè)任意一個(gè)排列與標(biāo)準(zhǔn)排列任意一個(gè)排列與標(biāo)準(zhǔn)排列 都可經(jīng)過都可經(jīng)過123n排列的奇偶性相同排