【精品】线性代数1 2.doc

《【精品】线性代数1 2.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、§2全排列及其逆序数2•排列及其逆序数（1）排列由自然数1，2,…组成的一个有序数组「应••厶称为一个〃级排列.问题把〃个不同的元素排成一列，共有多少种不同的排法？/定义把〃个不同的元素排成一列，叫做这〃个元素的全排列.〃个不同元素的所有排列的种数，通常用匕表示./Pn=〃•（〃—1）•（〃—2）…3•2•1=〃！即〃个不同的元素一共有加种不同的排法.3个不同的元素一共有3!=6种不同的排法123,132,213,231,312,321所有6种不同的排法中，只有一种排法(123)中的数字是按从小到大的自然顺序排列的,

2、而其他排列中都有大的数排在小的数之前.因此大部分的排列都不是“顺序”，而是“逆对于〃个不同的元素，可规定各元素之间的标准次序.〃个不同的自然数，规定从小到大为标准次序.定义当某两个元素的先后次序与标准次序不同时，就称这两个元素组成一个逆序.k)例如在排列32514中,逆序逆序思考题：还能找到其它逆序吗?答：2和1,3和1也构成逆序.定义排列中所有逆序的总数称为此排列的逆序数.排列订2…的逆序数通常记为t（i』2••心）・奇排列：逆序数为奇数的排列.偶排列：逆序数为偶数的排列.思考题：符合标准次序的排列是奇排列还是偶排列？

3、答：符合标准次序的排列（例如：123）的逆序数等于零，因而是偶排列.计算排列的逆序数的方法设PaPz---Pn是1，2,…，〃这〃个自然数的任一排列，并规定由小到大为标准次序.先看有多少个比P1大的数排在P1前面，记为0;再看有多少个比”2大的数排在”2前面，记为力2；最后看有多少个比几大的数排在几前面，记为-；则此排列的逆序数为t=t+t2+•••+/例1:求排列32514的逆序数.解：“32514)=0+1+0+3+1=5练习：求排列453162的逆序数.解：t=9■对换在一个排列中，若其中某两数.和乙互换位置，其

4、余各数位置不变得到另一排列y…b这种变换称为一个对换，记为(也)・”(31)(42)(43)例63421T1423T1243T1234T-5T-2T厂=0结论：%1对换改变排列的奇偶性.%1任意一个〃级排列与标准排列12都可以经过一系列对换互变・①的证明■对换在相邻两数间发生，即设排列…jk…(1)经/衣对换变成...kj...(2)此时，排列(1)、⑵中从与其他数是否构成逆序的情形未发生变化；耐与氐两数构成逆序的情形有变化：若⑴中必构成逆序，则⑵中不构成逆序(逆序数减少1)若⑴中必不构成逆序，则⑵中构成逆序(逆序数增加

5、1)■一般情形设排列...jiv..isk..・(3)经/衣对换变成...kiv..isj...(4)易知，⑷可由⑶经一系列相邻对换得到：E经s+1次相邻对换成为…町»・・&・・・/经s次相邻对换成为・..kiv..isj・・・即经2s+l次相邻对换后⑶成为(4).相邻对换改变排列的奇偶性，奇数次这样的对换后排列的奇偶性改变.II思考练习(排列的逆序数)1.^542163)z(24...(2n-2)(2n)(2n-l)(2n-3)...31)2•若排列的兀1兀2・・・兀〃逆序数为I，求排列电兀加1…兀1的逆序数.1.(1

6、)9(2)1+3+…+(2兀一1)=沪2.r(xnxn_1-x1)=加；1)_1・思考练习(排列的逆序数详解)方法1在排^]x1x2...xn中,任取两数占和£(SVt),则它们必在排歹!

7、兀1兀2…心或…兀1中构成逆序，且只能在其中的一个排列中构成逆序.又在排列兀丙…心中取两数的方法共有2_n__n(n-l)Cw=2!(n-2)!=2故排列x1x2...xn与xnxn_1...x1中逆序之和为—依题意，有此即叫孔-1…兀1)=_I・方法2〃个数中比i大的数有i个（冋2,…心若在排列兀西••心中对，构成的逆序为百个，

8、则在兀几“・・・兀1中对i构成的逆序为（〃-•，于是两排列中对，构成的逆序之和为Zf+[(n_i)_ZJ=n~i(i=l，2，・・・m)从而此即心1兀2•*•兀』+力(七兀“一1…兀1)=(“_1)+(“_2)+..2+1="(；1)n(n-l)T心几一1…兀i)=1・