2-2 n元排列在线视频

同学们 大家好

欢迎来到MOOC课程：线性代数-先修课

第二章 行列式

2.2节 n元排列

本节的主要内容为

n元排列的逆序及逆序数

n元排列的奇偶性

对换及其对排列奇偶性的影响

首先 我们来回顾与分析一下

2阶行列式和3阶行列式的定义

我们给出这样的一个表格对它进行分析

首先 2阶行列式有两项代数和

每一项有两个元素相乘

符号正负号各半

对于3阶行列式 总项数为6项

每一项由3个元素相乘

正负号也是各自一半

于是 我们把它的每一项的具体形式

表示成这个表格当中的最右边这一列

问题在于 这个符号应该取什么

等价的就是负1上边的指数

它与列脚标j_1j_2以及j_1j_2j_3有何关系

为了分析这个问题

我们再把2阶行列式和3阶行列式

把它表示出来

并且把它表示成这样的求和号的形式

这里的求和号 就是表示连加的意思

我们的问题就集中到

如何决定列下标所属的集合S

以及刚才说的那种对应关系τ

对于2阶行列式

列下标集合为12和21

对于3阶行列式 列下标集合

为123 231 312 321 213和132

我们用蓝色标记出对应负号的那一项

于是 我们很容易发现

列下标集合S就应该等于n元全排列集合

也就是P_n

那么 我们都知道P_n的个数

就等于n的阶乘

n元全排列这个概念

在中学大家都很熟悉

我们就不再多介绍

下面 我们把目光集中到

如何决定符号的问题

也就是如何决定这个对应关系τ

我们用蓝色标记出列下标集合当中

取负号的那一项

我们会发现对于2阶行列式

顺序取正号 逆序取负号

但是 对于3阶行列式情况要复杂很多

为了分析得更清楚

我们需要引入新的记号和概念

二 n元排列及其逆序数

首先 我们复习一下n元排列的概念

定义3.1

由1,2一直到n组成的有序数组

称为一个n元排列

记为j_1j_2一直到j_n

全体n元排列组成的集合记为P_n

例如:1,2,3一直到n 是一个n阶排列

我们把这个排列叫做自然排列

显然 n阶排列一共有n的阶乘个

定义3.2 在一个n元排列j_1j_2一直到j_n中

如果一个大数排在小数的前面

用数学的语言描述

就是当s小于t时有j_s大于j_t

也就是排在前面的数比后面的数要大

则称这一对数j_s和j_t构成了一个逆序

此排列的逆序总数称为它的逆序数

我们把它记为τ

例如

5元排列23541当中

21 31 54 51和41为所有的逆序

因此 这个排列的逆序数就等于5

为求一个排列的逆序数

可以从第一个数字开始

依次检查它之后

是否有更小的数组成逆序

接着看第二个数字

以此类推……

就可以求出所有的逆序

进而 也就求出了它的逆序数

我们再来看一个例子

对于自然排列1,2一直到n

我们知道没有大数排在小数的前面

所以 它的逆序数等于0

反过来

对于n,n-1一直到1 这样的一个排列

我们计算它的逆序数 用刚才的原则

首先看第一位

n的后面一共有n-1个比它小

再看第二位也就是n-1的后边

一共有n-2个数比它小

以此类推 实际上这就是一个等差数列

计算结果 这个排列的逆序数

等于二分之n再乘以n-1

有了逆序数的概念 我们再来看

3阶行列式的列下标集合

P_3当中 我们用蓝色标记的

表示它对应的负项

我们分别去计算六个排列的逆序数

我们有如下的结果

那么 你是不是已经发现了

凡是取正号的排列 它的逆序数都是偶数

凡是取负号的排列 它的逆序数都是奇数

那么 把逆序数放到负1的指数上

就得到了我们想要的符号

好 那么我们就发现了

行列式展开项当中的符号

由它所对应的列下标的排列的

奇偶性而决定

所以 我们就给出一个排列的

奇偶性的概念

定义3.3

逆序数为偶数的排列 称为偶排列

逆序数为奇数的排列 称为奇排列

那么 对我们刚才P_3的这个例子

我们就会发现

前三个为偶排列

而后三个为奇排列

再回到2阶行列式和3阶行列式的定义

以及我们的总结表当中

我们就可以用逆序数

来表示负1上边的这个指数

下边 我们再在理论上来证明一下

为什么这个正负号是各半的?

三 对换与排列的奇偶性

定义3.4 在一个排列中

把两个数i与j的位置互换

这样的操作

我们称为对换 并把它记为(i,j)

例如 对换(4,5)作用在五元排列23541上

它就把4和5的位置交换

从而 就得到了23451

那么 我们分别计算一下

这两个排列的逆序数

我们会发现:第一个等于5

而第二个等于4

这个原因 也很简单

因为除了54以外其余的逆序

都不变 所以对换之后

奇偶性一定会发生变化

刚才我们讨论的是4和5正好相邻的(情况)

下面 我们再来看一个不相邻的情况

对换(3,4)作用在23514上面

我们会得到它变成了24513

实际上 经过如下几次相邻的对换

我们也可以实现同样的效果

我们把这个变换的过程列出

我们可以看到经过了五次相邻对换

所以 对换后奇偶性也发生了变化

对于这一个例子当中我们看到了

对换中的元素不管是相邻的

还是不相邻的

它对排列都造成了奇偶性的变化

下边 我们会说明这并不是一个偶然现象

定理3.1 对换改变排列奇偶性

下面 我们来证明这个结论

假设该对换为(j,k)

第一种情况 若j与k在排列中相邻

则对换后其余逆序不变

则新得到的对换

最多在原来的对换后边加1或者是减1

那么 它的奇偶性一定发生变化

第二种情况

若j与k在排列中不相邻

设j与k之间

有s个元素

则 我们可以经过s+1次的相邻变换

把j变到k的后边

然后 又经过s次的相邻变换

把k换到了原来j的位置

一共需要经过2s+1次的相邻对换

由情形(1)我们就知道

对换发生后 奇偶性也发生了改变

所以 我们在理论上证明了定理3.1

对换将会改变排列的奇偶性

由刚才的定理

我们可以得到如下的推论

推论1 全部n元排列中的奇偶排列各占一半

下面 我们来证明这个结论

首先 我们把所有的n元排列

分成两个集合

一个是所有的奇排列集合

并且设它的个数为s个

另一个是所有的偶排列集合

并且设它的个数为t个

那么 对于每一个奇排列

经过(1,2)对换以后

一定就变成了偶排列

而且 不同的奇排列对换之后

得到的是不同的偶排列

于是 我们就可以知道s小于等于t

反过来 对于每一个偶排列

经过(1,2)对换以后 一定变成奇排列

并且不同的偶排列

在(1,2)对换以后得到的是不同的奇排列

因此 我们就可以得到t小于等于s

结合上面两个结论 我们就可以推出

s等于t,也就是奇排列和偶排列的个数相同

它们在所有排列当中各占一半

例如: 在P_2当中

排列21在(1,2)对换下变成了12

在P_3当中所有的奇排列为132 213和321

经过(1,2)对换以后

分别得到了231 123和312

我们还可以得到另一个推论

推论2 对于任何一个排列

j_1,j_2一直到j_n 一定存在一个整数t

使得经过t次对换后

它变成自然排列1,2一直到n

且t与j_1j_2...j_n这个排列的逆序数

是同奇偶的

存在性的证明很容易

我们只证明奇偶性

由于每次对换都会改变奇偶性

而自然排列的逆序数

等于0 是一个偶数

所以 我们就可以知道

t与τ(j_1j_2...j_n)是同奇偶的

在本讲当中我们介绍了

n元排列的逆序及逆序数

介绍了排列的奇偶性

它由逆序数而决定

我们介绍了对换及其对奇偶性的影响

我们得到了以下三个结论

结论1 对换改变排列的奇偶性

结论2 奇偶排列各占一半

结论3

奇排列经过奇次对换后可化为自然排列

偶排列经过偶次对换后可化为自然排列

本讲的内容就到这儿