全排列和对换

由于对角线法则只适用于二阶与三阶行列式,为研究更高阶的行列式,下面将转到有关排列的知识,然后引出 $n$ 阶行列式的概念。

全排列

从 $n$ 个不同元素中任取 $m (m\le n)$个元素排列起来,叫做「从 $n$ 个不同元素中取出 $m$ 个元素的一个排列」,当 $m=n$ 时,称其为「全排列」

$n$ 个不同元素的所有排列的种数,通常用 $P_n$ 表示,可计算如下:

从 $n$ 个元素中任取一个元素放在第一个位置上,有 $n$ 种取法;

从剩下的 $n-1$ 个元素中任务一个放在第二个位置上,有 $n-1$ 中取法;

这样继续下去,直到最后只剩一个元素放在第 $n$ 个位置上,只有 $1$ 种取法。于是:

$$ P_n=n*(n-1)*\dots*3*2*1=n! $$


例一 用 $1, 2, 3$ 三个数字做排列,排列总数 $P_3=3!=3*2*1 = 6$,分别是: $$ 123,231,312,132,321,213 $$

对于 $n$ 个不同的元素,先规定各元素之间有一个标准次序(例如 $n$ 个不同的自然数,可规定由小到大为标准次序),于是在这 $n$ 个元素的任一排列中,当「某一对元素的先后次序」与「标准次序」不同时,称其「构成 1 个逆序」。一个排列中所有逆序的「总数」叫做这个「排列的逆序数」。

逆序数为「奇数」的排列叫做「奇排列」,逆序数为「偶数」的排列叫做「偶排列」。

逆序数的计算方法讨论如下:

设 $n$ 个元素为 $1 至 n$ 这 $n$ 个自然数,并规定由小到大为标准次序。设 $p_1p_2\dots p_n$ 为这 n 个自然数的一个排列,如果比$p_i$大的且排在$p_i$前面的元素有 $t_i$ 个,就说 $p_i$ 这个元素的逆序数是 $t_i$,全体元素的逆序数之和:

$$ t=t_1+t_2+\dots+t_n=\sum_{i=1}^{n}{t_i} $$

即为这个排列的「逆序数」。

例二 求排列 $32514$ 的逆序数

在排列 $32514$ 中:

$3$ 排在首位,逆序数 $t_1=0$;

$2$ 之前比 $2$ 大的数有一个$(3)$,逆序数 $t_2=1$;

$5$ 之前比 $5$ 大的数有 $0$ 个,逆序数 $t_3=0$;

$1$ 之前比 $1$ 大的数有 $3$ 个 $(3,2,5)$,逆序数 $t_4=3$;

$4$ 之前比 $4$ 大的数有一个$(5)$,逆序数 $t_5=1$。

于是这个排列的逆序数为: $$ t=\sum_{i=1}^{5}{t_i}=0+1+0+3+1=5 $$

对换

在排列中,将任意两个元素对调,其余元素不变,这个对调动作称为「对换」;将相邻的两个元素「对换」,称为「相邻对换」。

定理 一个排列中的任意两个元素对换,排列将改变奇偶性。

依然设 $n$ 个元素为 $1\dots n$ 这 $n$ 个自然数,并按从小到大排列。

设排列为 $a_1\dots a_labb_1\dots b_m$,对换 $a,b$ 得到 $a_1\dots a_lbab_1\dots b_m$,除了 $a,b$ 外,其他元素的逆序数经过对换并不改变,而 $a, b$ 两元素的逆序数改变为:当 $a\gt b$ 时,对换后 $a$ 的逆序数「增加1」而 $b$ 的逆序数不变;当 $a \lt b$ 时,对换后 $a$ 的逆序数不变而 $b$ 的逆序数「减少1」。所以排列经过「相邻对换」后奇偶性发生改变。将「相邻对换」重复进行多次后,即为一般对换,结果与「相邻对换」一致。

推论 奇排列对换成标准排列的对换次数为奇数,偶排列对换成标准排列的对换次数为偶数。

由上面的定理得知,「对换的次数即排列奇偶性的变化次数」,而标准排列为「偶排列」,则得证。