09级第1章行列式n级排列及其逆序数

《09级第1章行列式n级排列及其逆序数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章行列式(1)-2§1.2n级排列1引例用1、2、3三个数字，可以组成多少个没有重复数字的三位数？种取法.共有解123123百位百位数有3种取法1如百位数取1121十位3百位数确定后,十位数有2种取法一、概念的引入个位123个位数有1种取法如十位数取22问题定义1将n个不同的元素排成一行(或列)，叫做这n个元素的一个全排列（或排列）.二、n级排列及其逆序数(2)自然数1,3,…,2n-1的一个排列例如:(1)自然数1,2,…,n的一个排列3n个自然数1,2,…,n的所有排列的种数，通常用由引例同理定义2由自然数1,2,…,n所组成的一个有序数组,称为一个n级排列.将n级排列(1

2、2…n)称为自然顺序排列(简称自然排列).以下提到的排列是指n级排列,提到的元素是指n级排列中某个数.4在排列中,我们规定各元素之间由小到大为标准次序.排列的逆序数例如在排列32514中共有5个逆序,如图示.32514逆序逆序逆序逆序逆序在一个排列中,若元素满足则称这两个元素构成一个逆序(或反序).定义35中所有逆序的总数称为此排列的的逆序数,记为定义4一个排列6方法1在它后面比它小的数码的个数,即对这n-1个元素分别算出与它后面的元素构成逆序的个数，逆序的个数总和即为所求排列的逆序数.简称向后(或向右)比较法.例1求排列32514的逆序数.故此排列的逆序数为2+1+2+0=5.32

3、5141220计算排列逆序数的方法7例2求排列32514的逆序数.故此排列的逆序数为1+0+3+1=5.3251431*方法2在它前面比它大的数码的个数,即对这n-1个元素分别算出与它前面的元素构成逆序的个数，逆序的个数总和即为所求排列的逆序数.简称向前(或向左)比较法.8例3计算下列排列的逆序数，并讨论它们的奇偶性.解:(采用“向后比较法”计算排列的逆序数)此排列为偶排列.=1+0+4+5+4+3+0+1=18定义5逆序数为奇数的排列称为奇排列;逆序数为偶数的排列称为偶排列.9解:(采用“向后比较法”计算排列的逆序数)当n=2,逆序数=1时为奇排列;当n=3,逆序数=3时为奇排列;

4、当n=4,逆序数=6时为偶排列;当n=5,逆序数=10时为偶排列;当n=4k+2,逆序数=(2k+1)(4k+1)时为奇排列;当n=4k+3,逆序数=(4k+3)(2k+1)时为奇排列;当n=4k+4,逆序数=(2k+2)(4k+3)时为偶排列;当n=4k+5,逆序数=(4k+5)(2k+2)时为偶排列;其中,k是非负整数.10三、对换的定义定义1在排列中，将某两个元素互换，其余元素不动，将原排列变成新排列的这种变换叫做对换(或互换)．将相邻两个元素对换，叫做相邻对换(或相邻互换)．例如,相邻对换例如,对换11四、对换与排列的奇偶性的关系定理1一个排列中的任意两个元素对换，改变排列的

5、奇偶性．证明:1.先证相邻对换的情形设排列为除a,b外，对其它元素的逆序个数不改变.将相邻两个元素a,b对换:12经对换后,a的逆序个数不变,b的逆序个数增加1,则逆序数增加1;当时，采用“向后比较法”16352487例如:排列将相邻两个数2,4对换,得16354287排列则逆序数增加1.13当时，经对换后a的逆序个数减少1，b的逆序个数不变,则逆序数减少1.16352487例如:排列将相邻两个数5,2对换,得16325487排列则逆序数减少1.总之,对换相邻两个元素，逆序数增加1或减少1.改变排列的奇偶性.14次相邻对换将b向前作m次相邻对换:设排列为现来对换与将a向后作m+1次相

6、邻对换:2.再证一般对换的情形则15所以排列中的任意两个元素a,b对换，可通过2m+1次相邻对换得到.上面已证明对换相邻两个元素，改变排列的奇偶性.而2m+1为奇数,则通过奇数次相邻对换改变排列的奇偶性.证完.16例4求证:在全部n(n2)级排列中,奇偶排列各占一半.证:设在全部n级排列中全部奇排列有s个,全部偶排列有t个,现来证s=t=n!/2.将每个奇排列的前两个数对换(或经过任何一次对换),则这s个奇排列全变成偶排列,所以s≼t若将每个偶排列的前两个数对换(或经过任何一次对换),,则这t个偶排列全变成奇排列,于是t≼s.则s=t=n!/2,奇偶排列各占一半.17例:自然数1,

7、2,3的全部n级排列:奇排列213321132偶排列123231312奇偶排列各占一半18经过若干次相邻对换,将排列(246135)变为自然排列.例5解:第一,将排列(246135)中的1依次与6,4,2作相邻对换,经过3次相邻对换,得到排列(124635).第二,将排列(124635)中的3依次与6,4作相邻对换,经过2次相邻对换,得到排列(123465).第三,将排列(123465)中的5与6作相邻对换,经过1次相邻对换,得到排列(123456).总共