线性代数与几何：1-2 全排列及其逆序数.ppt

文档介绍：第二节 全排列及其逆序数
从上节的例子我们知道，对角线法则只适用于
二阶与三阶行列式，对四阶和四阶以上的行列式
就不适用了.
怎样计算四阶和四阶以上的行列式呢?
我们先从二阶与三阶行列式的计算中找一找规律．
二阶行列式一共有两项，每一项均由不同行不同列的元素组成。其组成的规律是
如果行标都取自然数1，2；列标只能取1，2
或2，1。所以二阶行列式中有两项 ， 。
先看二阶行列式
再看三阶行列式
三阶行列式一共有6项，每一项均由不同行不同列
的元素组成。其组成的规律是
如果行标都取自然数1，2，3；列标只能取1，2，3；
2，3，1；3，1，2；3，2，1；2，1，3；1，3，2。
所以三阶行列式中有6项 。
通过上述分析，我们知道了二阶行列式和三阶行列式
项的组成方法。既和排列有关。
一、全排列
定义
把n个不同的自然数按一定次序排成一列,{p1,…,pn}。
n个不同的自然数的所有排列，称为n元全排列, n元全排列的个数通常用Pn表示.
例如{1，2，3}是一个三元排列，
{2，3，1}也是一个三元排列。
排列{1，2，…,n}称为n元自然排列.
二阶行列式和三阶行列式项的组成方法
1）行标取自然排列时，列标分别取全排列.
2）项的个数就是全排列的个数。
另外，我们还发现无论二阶行列式还是三阶行列式，均有一些项的前面取“+”，一些项的前面取“-”。怎样确定那些项的前面取“+”，
那些项的前面取“-”呢？我们发现和排列的顺序有关。
例如 排列{3,2,5,1,4} 中，
定义
排列的逆序数
3 2 5 1 4
逆序
逆序
逆序
在一个n元排列中，若一个大的数排在一个小的数的前面，则称这个排列有一个逆序。
我们规定各元素之间有一个标准次序, n 个不同的自然数，
规定由小到大为标准次序.
定义 一个n元排列{p1,…,pn}中所有逆序的总数称为此排列的逆序数，记为
分别计算出排列中每个元素前面比它大的数码
个数之和，即算出排列中每个元素的逆序数，
这每个元素的逆序数之总和即为所求排列的逆
序数.
例4 求排列{3,2,5,1,4}的逆序数.
解
在排列{3,2,5,1,4}中
3排在首位,逆序数为0;
2的前面比2大的数只有一个3,故逆序数为1;
计算排列逆序数的方法
3 2 5 1 4
于是排列的逆序数为
5的前面没有比5大的数,其逆序数为0;
1的前面比1大的数有3个,故逆序数为3;
4的前面比4大的数有1个,故逆序数为1;
例5 计算下列排列的逆序数，并讨论它们的奇偶性.
解