排列與逆序課件

排列與逆序排列與逆序?qū)⒂蒼個(gè)不同的自然數(shù)m1,m2,…,mn組成的一個(gè)有序數(shù)組稱(chēng)為一個(gè)n級(jí)排列.由于這里主要考慮這n個(gè)數(shù)的前后次序關(guān)系，不妨設(shè)這n個(gè)數(shù)就為1,2,…,n.于是，上面的定義可以寫(xiě)成如下定義.定義1-3排列與逆序定義1-3′將由自然數(shù)1,2,…,n組成的一個(gè)有序數(shù)組稱(chēng)為一個(gè)n級(jí)排列.人們通常按照定義1-3′給出n級(jí)排列，并且具體寫(xiě)n級(jí)排列時(shí)，在不發(fā)生混淆的情況下，只是將數(shù)字并排放在一起.例如，23541即為一個(gè)5級(jí)排列.由中學(xué)排列組合的知識(shí)可知，n級(jí)排列的總個(gè)數(shù)為n·(n－1)·(n－2)·…·2·1=n!排列與逆序試寫(xiě)出所有的3級(jí)排列.解由上面的討論可知，總共有3!=6個(gè)不同的3級(jí)排列，它們分別是123,132,213,231,312,321注意在【例1-1】的3級(jí)排列里，除了123中的數(shù)是按從小到大的遞增順序排列以外，其余的排列中，都有較大的數(shù)排在較小的數(shù)前面.例如，213中，2比1大，但是2排在1的前面.同樣，在n級(jí)排列中，也只有排列12…n中的數(shù)是按從小到大的遞增順序排列的，其他的排列都或多或少地破壞了這種順序.【例1-1】排列與逆序定義1-4在一個(gè)n級(jí)排列中，如果某兩個(gè)數(shù)的前后位置與大小順序相反，即前面的數(shù)大于后面的數(shù)，那么就稱(chēng)它們?yōu)橐粋€(gè)逆序，一個(gè)排列中逆序的總數(shù)就稱(chēng)為這個(gè)排列的逆序數(shù).通常，將j1j2…jn的逆序數(shù)記成τ(j1j2…jn)，并且我們將逆序數(shù)為奇數(shù)的排列稱(chēng)為奇排列，將逆序數(shù)為偶數(shù)的排列稱(chēng)為偶排列.排列與逆序一般地，可以利用如下方法計(jì)算一個(gè)n級(jí)排列的逆序數(shù)：設(shè)j1j2…jn是一個(gè)n級(jí)排列，如果把排在ji（i=1,2,…,n）前面且比ji大的數(shù)的個(gè)數(shù)記為si，則j1j2…jn的逆序數(shù)為

τ(j1j2…jn)=s1+s2+…+sn例如，τ(23541)=0+0+0+1+4=5，τ(32541)=0+1+0+1+4=6，因此，23541是一個(gè)5級(jí)奇排列，而32541是一個(gè)5級(jí)偶排列.更一般地，τ(12…n)=

0+0+…+0=0，從而12…n是一個(gè)n級(jí)偶排列.一般地，在n!個(gè)n級(jí)排列中，偶排列和奇排列各占一半.為了說(shuō)明這個(gè)事實(shí)，還需要進(jìn)一步研究排列的奇偶性.排列與逆序定義1-5在一個(gè)n級(jí)排列中，如果把這個(gè)排列里的任意兩個(gè)數(shù)i和j交換一下位置，而其余的數(shù)保持不動(dòng)，那么就得到了一個(gè)新的n級(jí)排列.對(duì)排列施行這樣的一個(gè)變化稱(chēng)為n級(jí)排列的一次對(duì)換，用符號(hào)(i,j)表示.例如，經(jīng)過(guò)對(duì)換(2,3)，可以將排列23541變成32541，將52431變成53421.容易驗(yàn)證，對(duì)一個(gè)排列連續(xù)實(shí)施兩次相同的對(duì)換，就將這個(gè)排列還原，變回原來(lái)的排列了.由此可知，一個(gè)對(duì)換把全部n級(jí)排列兩兩配對(duì)，使每?jī)蓚€(gè)配成對(duì)的n級(jí)排列在這個(gè)對(duì)換下互變.排列與逆序關(guān)于排列的奇偶性，可以不加證明地給出如下定理.定理1-1任何一個(gè)對(duì)換都可以改變排列的奇偶性，也就是說(shuō)，經(jīng)過(guò)一次對(duì)換，偶排列變成奇排列，奇排列變成偶排列.這個(gè)定理說(shuō)明了：當(dāng)n≥2時(shí)，n級(jí)排列的奇排列和偶排列個(gè)數(shù)相等，各為n!2個(gè).定理1-2設(shè)j1j2…jn是任意一個(gè)n級(jí)排列，則j1j2…jn與12…n可以經(jīng)過(guò)一系列對(duì)換互變，并且所作對(duì)換的個(gè)數(shù)n(j1j2…jn)的奇偶性與τ(j1