北京工业大学线性代数第一章第二节.ppt

第二节排列,一、排列的概念二、逆序及逆序数三、排列的性质,2,一、排列的概念,引例,用1、2、3三个数字，可以组成多少个没有重复数字的三位数？,解,该问题是数字1、2、3的全排列，共有3！（=321=6）个没有重复数字的三位数。,123,132,213,321,231,312,每个数称为一个三元排列。,3,n个不同自然数的一个全排列称为一个n元排列。,如,4213是一个四元排列,24135是一个五元排列,因为n个不同的自然数形成的全排列共有n！个，所以我们有,n元排列的个数：,n元排列共有n!个。,一个n元排列记为,定义:,说明：如无特别说明,我们所指的n元排列是由1，2,，n组成的n元排列。,4,在例1中，所有的三元排列,123132213231312321,中只有一个是按自然顺序排列其他的都或多或少的破坏了这个顺序。,132,逆序,312,逆序,逆序,321,逆序,逆序,逆序,逆序数为1,逆序数为2,逆序数为3,二、逆序和逆序数,5,例如排列32514中，,逆序数,逆序,32514,逆序,逆序,逆序,一个排列中，如果一个大的数排在一个小的数的前面，就称这一对数构成一个逆序。,一个排列中逆序的总数称为这个排列的逆序数。,用表示排列的逆序数。,逆序,逆序,6,逆序数的计算方法,方法1,分别算出1，2,n这n个元素的,逆序的个数，这n个元素的逆序的个数之和为这个n元排列的逆序数.,(按数字从小到大的顺序计算逆序数),方法2,分别计算出排列中每个元素前面比它大的数字的个数，即算出排列中每个元素的逆序数，每个元素的逆序数之总和即为所求排列的逆序数.,(由前向后求每个数的逆序数),7,32514,3,1,0,0,1,所以排列32514的逆序数为,例1求排列32514的逆序数.,方法1:,1的前面比1大的数有三个,故逆序数为3;,2的前面比2大的数有一个,故逆序数为1;,4的前面比4大的数有一个,故逆序数为1;,3排在首位,逆序数为0;,5的前面没有比5大的数,其逆序数为0;,8,方法2,3排在首位,逆序数为0;,2的前面比2大的数只有一个3,故逆序数为1;,5的前面没有比5大的数,其逆序数为0;,1的前面比1大的数有3个,故逆序数为3;,4的前面比4大的数有1个,故逆序数为1;,所以是排列32514的逆序数为,32514,9,偶排列,逆序数为偶数的排列称为偶排列。,奇排列,逆序数为奇数的排列称为奇排列。,如,32514为奇排列,三奇排列和偶排列,排列按逆序数的奇偶性分为奇排列和偶排列。,排列12n是偶排列。,10,例2计算下列排列的逆序数，并讨论它们的奇偶性.,解,此排列为偶排列.,217986354,0,1,0,0,1,3,4,4,5,11,解,当n=4k或n=4k+1时,为偶排列.,当n=4k+2或n=4k+3时,为奇排列.,12,解,当为偶数时，排列为偶排列，,当为奇数时，排列为奇排列.,13,定义,把一个排列中某两个数的位置互换,而,其余的数不动,就得到另一个排列.这样的一,个变换称为对换.,例如：,故35214为偶排列.,由此我们猜想有如下结论：,对换奇排列32514中的2，5两个数得到,排列35214，,而,四排列的性质,14,定理,对换改变排列的奇偶性。,证：,(1)先证相邻对换的情景.,设排列为,ij,经过i,j对换成,ji,若ij,则,若ij,则,所以ij与ji的奇偶性相反。,15,(2)再证不相邻对换的情景.,设排列为,经过i,j对换变成,由（1）知，将i,k1对换得,i经过s次相邻对换变成,再将j经过s+1次相邻对换变成,其奇偶性改变一次。,经过2s+1次相邻对换变成,所以,的奇偶性与,的奇偶性相反。,则,16,推论1,在全部n元排列中，奇、偶排列,各占一半，即都是个,n元排列的总数为n!,设其中奇排列为p个,偶排列为q个.,设想将每一个奇排列都施以同一的对换,例如都对换(1,2),则可知p个奇排列全部变为偶排列,于是有pq;,同理如将全部偶排列也都施以同一对换,则q个偶排列全部变为奇排列,于是又有qp,所以得出p=q=n!/2.,证:,17,推论2,任意一个n元排列与自然排列,12n都可以经过一系列对换互变，并且所作对换的次数与这个排列的奇偶性相同。,证明,由定理知对换的次数就是排列奇偶性的变化次数,而自然排列是偶排列(逆序数为0),因此，知推论成立.,18,例如,排列32514需经过奇数次对换变为自然排列12345。即,32514