《线性代数与几何：1-2 全排列及其逆序数》由会员分享，可在线阅读，更多相关《线性代数与几何：1-2 全排列及其逆序数（20页珍藏版）》请在金锄头文库上搜索。
1、第二节 全排列及其逆序数 从上节的例子我们知道，对角线法则只适用于从上节的例子我们知道，对角线法则只适用于二阶与三阶行列式，对四阶和四阶以上的行列式二阶与三阶行列式，对四阶和四阶以上的行列式就不适用了就不适用了. 怎样计算四阶和四阶以上的行列式呢怎样计算四阶和四阶以上的行列式呢?我们先从二阶与三阶行列式的计算中找一找规律我们先从二阶与三阶行列式的计算中找一找规律 二阶行列式一共有两项，每一项均由不同行二阶行列式一共有两项，每一项均由不同行不同不同列列的元素组成。其组成的规律是的元素组成。其组成的规律是 如果行标都取自然数如果行标都取自然数1，2；列标只能取；列标只能取1，2或或2，1。所以二阶
2、行列式中有两项。所以二阶行列式中有两项 ， 。先看二阶行列式先看二阶行列式再看三阶行列式再看三阶行列式 三阶行列式一共有三阶行列式一共有6项，每一项均由不同行不同列项，每一项均由不同行不同列的元素组成。其组成的规律是的元素组成。其组成的规律是 如果行标都取自然数如果行标都取自然数1，2，3；列标只能取；列标只能取1，2，3；2，3，1；3，1，2；3，2，1；2，1，3；1，3，2。所以三阶行列式中有所以三阶行列式中有6项项 。 通过上述分析，我们知道了二阶行列式和三阶行列式通过上述分析，我们知道了二阶行列式和三阶行列式项的组成方法。既和排列有关。项的组成方法。既和排列有关。一、全排列定义定义
3、把把n个不同的自然数按一定次序排成一列个不同的自然数按一定次序排成一列,称为一个称为一个n元排列元排列.记为记为p1,pn。 n个不同的自然数的所有排列，称为个不同的自然数的所有排列，称为n元元全排列全排列, n元全排列的个数通常用元全排列的个数通常用Pn表示表示. 例如例如1，2，3是一个三元排列，是一个三元排列，2，3，1也是一个三元排列也是一个三元排列。排列排列1，2，,n称为称为n元自然排列元自然排列. 二阶行列式和三阶行列式项的组成方法二阶行列式和三阶行列式项的组成方法 1）行标取自然排列时，列标分别取全排列）行标取自然排列时，列标分别取全排列. 2）项的个数就是全排列的个数。）项的
4、个数就是全排列的个数。 另外，我们还发现无论二阶行列式还是三阶行列另外，我们还发现无论二阶行列式还是三阶行列式，均有一些项的前面取式，均有一些项的前面取“+”，一些项的前面取，一些项的前面取“-”。怎样确定那些项的前面取。怎样确定那些项的前面取“+”， 那些项的前面取那些项的前面取“-”呢？我们发现和排列的顺序有呢？我们发现和排列的顺序有关。关。例如例如 排列排列3,2,5,1,4 中，中， 定义定义排列的逆序数排列的逆序数3 2 5 1 4逆序逆序逆序逆序逆序逆序 在一个n元排列中，若元排列中，若一个大的数排在排在一个小的数的前面，则称这个排列有一个逆序。排列有一个逆序。 我们规定各元素之间
5、有一个标准次序我们规定各元素之间有一个标准次序, n 个不同的自然数，个不同的自然数，规定由小到大为标准次序规定由小到大为标准次序.定义定义 一个一个n元元排列排列p1,pn中所有逆序的总中所有逆序的总数称为此排列的数称为此排列的逆序数逆序数，记为，记为 分别计算出排列中每个元素前面比它大的数码分别计算出排列中每个元素前面比它大的数码个数之和，即算出排列中每个元素的逆序数，个数之和，即算出排列中每个元素的逆序数，这每个元素的逆序数之总和即为所求排列的逆这每个元素的逆序数之总和即为所求排列的逆序数序数.例例4 4 求排列求排列3,2,5,1,4的逆序数的逆序数.解解在排列在排列3,2,5,1,4
6、中中3排在首位排在首位,逆序数为逆序数为0;2的前面比的前面比2大的数只有一个大的数只有一个3,故逆序数为故逆序数为1;计算排列逆序数的方法计算排列逆序数的方法3 2 5 1 4于是排列的逆序数为于是排列的逆序数为5的前面没有比的前面没有比5大的数大的数,其逆序数为其逆序数为0;1的前面比的前面比1大的数有大的数有3个个,故逆序数为故逆序数为3;4的前面比的前面比4大的数有大的数有1个个,故逆序数为故逆序数为1;例例5 5 计算下列排列的逆序数，并讨论它们的奇计算下列排列的逆序数，并讨论它们的奇偶性偶性.解解解解逆序数逆序数逆序数的性质定义: 将一个排列中的某两个数的位置互换而其余的数不动,这
7、样得到一个新的排列.这种变换称为对排列作一次对换,将相邻的两个数对换称为相邻对换.逆序数为奇数的排列称为奇排列逆序数为奇数的排列称为奇排列;逆序数为偶数的排列称为偶排列逆序数为偶数的排列称为偶排列.排列的奇偶性排列的奇偶性定理1 对排列进行一次对换将改变其奇偶性.证：首先证明对排列进行一次相邻的对换将改变其奇偶性设原排列为a1,an,a,b,b1,bm将a,b对换后所得新排列为a1,an,b,a,b1,bm由于在新排列中a1,an,b1,bm的位置没有改变，所以它们的逆序数逆序数没有改变。只有。只有a,b的位置改变了。 因此对排列进行一次相邻的对换将改变其奇偶性。再证一般情况由定理1可得下列推
8、论证毕证毕推论1 将奇排列变成自然排列所需的对换次数为奇数, 将偶排列变成自然排列所需的对换次数为偶数. 证：因为自然排列的逆序数逆序数为零，所以是偶排列。如果原排列是奇排列，变成偶排列需要的对换次数为奇数，所以奇排列变成自然排列所需的对换次数为奇数。同理可证偶排列的情况。证毕证毕推论2 在全体n元排列(n1)中,奇排列和偶排列各占一半. 证：设在全体n元排列(n1)中,奇排列一共有s个，偶排列一共有t个.将每个奇排列的前面两个数字对换，可得到s个偶排列，所以st。将每个偶排列的前面两个数字对换，可得到t个偶排列，所以ts。因此s=t,奇排列和偶排列各占一半.证毕证毕 我们有了逆序数逆序数的概
9、念后，再来讨论行列式的项前面的符号就很方便了。先看二阶行列式先看二阶行列式如果行标都取自然数如果行标都取自然数1，2；列标的；列标的排列为1，2或或2，1其中1，2是是偶排列， 前面的符号为“+”；2，1是是奇排列， 前面的符号为“-”；再看三阶行列式再看三阶行列式 如果行标都取自然数如果行标都取自然数1，2，3；列标排列为；列标排列为1，2，3；2，3，1；3，1，2；3，2，1；2，1，3；1，3，2。其中，其中，1，2，3；2，3，1；3，1，2是是偶排列，相应的项前面的符号为“+”；3，2，1；2，1，3；1，3，2是是奇排列，相应的项前面的符号为“-”。 通过上述分析，我们找到了构造二阶行列式和三阶行列式有通过上述分析，我们找到了构造二阶行列式和三阶行列式有别于对角线法的新的方法。别于对角线法的新的方法。 下面一节，我们将用新的方法定义一般的n价行列式，当然，我们希望用新的方法定义的n价行列式可以原来解一般的n元线性方程组.
