高等代数第3章第2节排列ppt课件

.,1,第3章行列式,3.2排列,.,2,内容分布一、排列与反序二、对换及反序的性质教学目的了解排列、反序、对换的定义；会计算排列的反序数；了解排列及对换的性质重点、难点反序数的计算,.,3,定义由n个不同数码1，2，n组成的一个有序数组称为一个n元排列,例如：,1，2，3，4，5,4，1，5，3，2,5，3，2，1，4,都是数1,2,3,4,5的一个排列,考虑：n个数码的不同排列有个,n!,自然排列：,按数码的大小次序，由小到大排列,考虑：,n元排列中，自然排列只有一种,任一n元排列都一定出现较大数码排在较小数码之前的情况,一、排列与反序,除此之外，,.,4,定义在一个排列中，若某个较大的数码排在某个较小的数码前面，就称这两个数码构成一个反序（或称为逆序）一个排列中出现的反序总数称为这个排列的反序数（或逆序数）,奇排列：,反序数为奇数的排列,偶排列：,反序数为偶数的排列,排列12的反序数为,0，,排列231的反序数为,排列321的反序数为,2，,3，,如：,(12)=0,(231)=2,(321)=3,常用(i1i2in)表示排列i1i2in的反序数,.,5,计算排列的反序数的方法：,方法一：,n个数的任一n元排列，先看数1，看有多少个比1大的数排在1前面，记为,再看有多少个比2大的数排在2前面，记为,继续下去，最后至数n，前面比n大的数显然没有,则此排列的反序数为,记为,.,6,方法二：,数i1后面比i1小的数的个数,+数i2后面比i2小的数的个数,+,+数in1后面比in1小的数的个数,方法三：,数in前面比in大的数的个数,+数in1前面比in1大的数的个数,+,+数i2前面比i2大的数的个数,.,7,例：求排列3，2，5，1，4的逆序数,解：,（法1）,（法2）,（法3）,例：,(453162)=,9,(453128679)=,10,(3712456)=,7,(768135492)=,21,(n(n1)21)=,.,8,例：计算排列2k,1,2k1,2,k+1,k的逆序数,排列2k,1,2k1,2,2k2,3,k+1,k,解：,设mi为排在数i的左边且比i大的数的个数,则,所以题设排列的逆序数为,.,9,那么排列xnxn1x2x1中就恰有(ni)mi个比xi大的数在xi的左边,例：假设n个数码的排列x1x2xn1xn的逆序数为k，那么排列xnxn1x2x1的逆序数为多少？,解：,在n个数码1,2,n中，,数有ni个,对任一数i，大于i的,若在排列x1x2xn中，,有mi个比xi大的数,在xi左边，,而有(ni)mi个比xi大的数在xi的右边,故排列xnxn1x2x1的逆序数为,.,10,例：假设n个数码的排列x1x2xn1xn的逆序数为k，那么排列xnxn1x2x1的逆序数为多少？,解二：,对于任意一对数码xk,xm，,它或在x1x2xn,中是逆序，,或在xnxn1x2x1中是逆序，,且只能在一个,排列中构成逆序,因此，x1x2xn1xn的逆序数与xnxn1x2x1的逆序数之和为,从而排列xnxn1x2x1的逆序数为,.,11,二、对换及排列的性质,观察1,2,3这三个数码的全体排列情况：,.,12,定义如果把一个排列中的任意两个数码i与j交换位置，而其余数码不动，那么就得到一个新的排列对于排列所施行的这样一个变换叫做对该排列作一次对换,简称对换，并且用符号(i,j)来表示,例如，,例：写出把排列12435变成排列25341的那些变换,解：,这种变换步骤不唯一，如可以按如下步骤变换：,.,13,定理任意一个n元排列都可以经过一些对换变成自然排列，并且所作对换的个数与这个排列有相同的奇偶性,定理3.2.2每一个对换都改变排列的奇偶性,定理3.2.3当n2时，n个数的所有排列中，奇偶排列各占一半，各有个,定理3.2.1设i1i2in和j1j2jn是n个数码的任意两个排列，那么总可以通过一系列对换由i1i2in得出j1j2jn,.,14,证明：,设n个数的排列中，,奇排列有p个，偶排列,则pqn！,对这p个奇排列，施行同一对换(i,j)，,同理可得,所以,定理3.2.3当n2时，n个数的所有排列中，奇偶排列各占一半，各有个,有q个，,则由定理,3.2.2得到p个偶排列,由于对这p个偶排列施行对换,(i,j)，又可以得到原来的p个奇排列，,所以这p个偶,排列各不相等,但我们一共只有q个偶排列，,故,.,15,例：选择i与k使1274i56k9成偶排列,解：,在原排列中缺少3和8,令i=3，k=8可得排列127435689.,因为,排列127435689,排列