第一章 行列式
第一节 排列及其逆序数
? 引言
? 排列与逆序数
一、引言
我们在中学曾经学习过求解二元一次线性方程
组
?
?
?
??
??
22212
12111
cxbxa
cxbxa （ 1）
当两个方程的未知数系数不成比例，即
2
1
2
1
b
b
a
a ? 时，
我们有
.baba cacax,baba cbcbx
1221
1221
2
1221
2112
1 ?
??
?
?? （ 2）
为方便记忆，我们引入 二阶行列式
bcad
db
ca
??
（ 3）
则（ 2）可以表示为
.
ba
ba
ca
ca
x,
ba
ba
bc
bc
x
22
11
22
11
2
22
11
22
11
1
?? （ 4）
即当（ 1）的系数行列式
0
ba
ba
22
11 ? 时,（ 1）的解可以
用二阶行列式表示为（ 4）。
用高斯消元法，对三元一次线性方程组
,
3333232131
2323222121
1313212111
?
?
?
?
?
???
???
???
bxaxaxa
bxaxaxa
bxaxaxa （ 5）
我们也可以得到类似的结果。即如果引入 三阶行列式
,ccccccccc
ccccccccc
ccc
ccc
ccc
322311332112312213
322113312312332211
333231
232221
131211
???
??? （ 6）
则当（ 5）的系数行列式
0
aaa
aaa
aaa
D
333231
232221
131211
?? （ 7）
时，方程组（ 5）的解可以用三阶行列式表示为
.
aaa
aaa
aaa
baa
baa
baa
x,
aaa
aaa
aaa
aba
aba
aba
x,
aaa
aaa
aaa
aab
aab
aab
x
333231
232221
131211
33231
22221
11211
3
333231
232221
131211
33331
23221
13111
2
333231
232221
131211
33323
23222
13121
1
???
（ 8）
对于 n元一次方程组，是否也有类似于上述（ 4）、
（ 8）的结果呢？这就是本章要回答的问题 。为解决
这一问题，我们要引入 n阶行列式的概念。作为定义 n
阶行列式的预备知识，下面我们将简单介绍排列的 逆
序数 的概念。
二、排列与逆序数
1、排列与逆序数的定义
把 n个不同元素排成一列，称为一个 全排列 或简
称 排列 （ permutation）。用 Pn表示 n个元素所成全
排列的个数，则 Pn＝ n！。这门课程中我们关心的主
要是一个全排列里面元素的排列次序。 在这 n！个不
同的全排列中，我们规定某一个排列的次序为 标准
顺序 。对自然数，我们规定从小到大的排列顺序为
标准顺序 。
定义 1 在一个排列中，当其中某两个元素的次
序与标准顺序中这两个元素的次序不一致时，我们
称这两个元素产生了一个逆序 (an inverse－ order)。
一个排列中所有的逆序数的总数称为这个排列的逆
序数 (number of the inverse-orders)。
例如，排列 1234的顺序为标准顺序，其逆序数为
0。在排列 1324中，元素 3和 2的次序与它们在标准顺
序中的次序不同（标准顺序中应该是 2排在 3的前面，
因为 2比 3小），因此这两个元素产生了一个逆序,
而其它任意两个元素的排列次序都与其在标准顺序
中的次序一样，因此排列 1324的逆序数为 1。
实际上，根据逆序数的定义，我们可以得到逆
序数的计算方法如下：
nbbb ?,,21
ib ib ib
设有 n个自然数,为这 n个数的一个排
列。则对每个,如果比 大且排在 前面的元素个
数为
it
，就称
ib
在这个排列中的逆序数为
it
，而
ntttt ???? 21
就是这个排列的逆序数。
例 1 求排列 4321576的逆序数。
解 4前面没有数，因此 ;01 ?t
3前面有 1个数（即数字 4）比它大，因此
2前面有 2个数比它大，因此
1前面有 3个数比它大，因此
5前面没有数比它大，因此
7前面没有数字比它大，因此
6前面有 1个数比它大，因此
因此，这个排列的逆序数为：;12 ?t;23 ?t;34 ?t;05 ?t;06 ?t;17 ?t
710032107654321 ??????????????? tttttttt
例 2 求自然数 1,2,…, n组成的排列 n (n – 1)
(n – 2) ··· 21的逆序数 。
解 由前面所述的逆序数的求法，我们可以得到此
排列的逆序数为
2/)1()1(210121 ????????????? ? nnnttttt nn ??
2、排列的奇偶性
定义 2 如果一个排列的逆序数为奇数，则称此
排列为 奇排列 （ odd permutation）；如果一个排
列的逆序数为偶数，则称此排列为 偶排列 （ even
permutation）。
例如，上述例 1中的排列即为奇排列。
定义 3 在一个排列中，将某两个元素对调位置而
其余元素保持不变的操作称为 对换 。
例如，在排列 1234中对换 2和 3，得到新排列
1324。排列 1234为标准排列，因此其逆序数为 0，它
是一个偶排列，而排列 1324的逆序数为 1，这是一个
奇排列。实际上，我们可以证明，这个结论对于一般
的排列也是正确的，即有
定理 1 在一个排列中，进行一次对换，排列改变奇
偶性。
证：先证对换两个相邻元素的情形。
设排列为 nn bbabbaaa ?? 2121 逆序数为 t 。对换
a 和 b 后，排列为 nn bbb a baaa ?? 2121,其逆序数为
't 。
显然排列中除了 a 和 b,其它元素的逆序数保持不变，
只有 a 和 b 的逆序数有可能发生变化。当 ba ? 时，
的逆序数增加 1而 的逆序数不变；当
a
b ba ? 时,的
逆序数不变而
a
b 的逆序数减少 1，总之,1' ?? tt 或者
1' ?? tt 。因此，排列改变奇偶性。
其次，证明一般情况。
kmn ccbcbbabaaa ??? 212121
设排列为,对换 a 和
b
后，
变为
kmn ccacbbbbaaa ??? 212121
。我们可以把它看成是先
m次对换相邻元素 a 与 ),,1( mib
i ??
变成
kmn ccabcbbbaaa ??? 212121
，再 对换 a 和 b,然后作 m
次对换相邻元素
ib
与 )2,1( mib ??,变成
kmn ccacbbbbaaa ??? 212121
。因此，这种情况下，对换
a 和 b,相当于作了 2m+1次相邻元素的对换，故它
改变排列的奇偶性。
由于标准顺序的排列的逆序数为 0，由定理 1我
们有：
推论 1 奇排列变成标准顺序的排列须经过奇数次
对换；偶排列变成标准顺序的排列须经过偶数次对换。
由于 n个不同元素的全排列的总数为 n!，由定理 1，我
们还有：
推论 2 在 n个不同元素的全排列中，奇偶排列各
占一半，均为 n!/2个。
证：设 P为 n个不同元素的全排列组成的集合，其
中 A表示全体奇排列所成的集合,而 B为全体偶排列
所成的集合。显然 P＝ A∪ B，而 P的元素个数为 n!。
设 A的元素个数为 r,B的元素个数为 t。现在我们对 A
中的 r个排列（均为奇排列）都对换其第一、第二个元
素，则我们得到 r个偶排列（即变成了 B中的排列），
故 r≤t。同理，我们可以得到 t≤r。即 r＝ t。
第一节 排列及其逆序数
? 引言
? 排列与逆序数
一、引言
我们在中学曾经学习过求解二元一次线性方程
组
?
?
?
??
??
22212
12111
cxbxa
cxbxa （ 1）
当两个方程的未知数系数不成比例，即
2
1
2
1
b
b
a
a ? 时，
我们有
.baba cacax,baba cbcbx
1221
1221
2
1221
2112
1 ?
??
?
?? （ 2）
为方便记忆，我们引入 二阶行列式
bcad
db
ca
??
（ 3）
则（ 2）可以表示为
.
ba
ba
ca
ca
x,
ba
ba
bc
bc
x
22
11
22
11
2
22
11
22
11
1
?? （ 4）
即当（ 1）的系数行列式
0
ba
ba
22
11 ? 时,（ 1）的解可以
用二阶行列式表示为（ 4）。
用高斯消元法，对三元一次线性方程组
,
3333232131
2323222121
1313212111
?
?
?
?
?
???
???
???
bxaxaxa
bxaxaxa
bxaxaxa （ 5）
我们也可以得到类似的结果。即如果引入 三阶行列式
,ccccccccc
ccccccccc
ccc
ccc
ccc
322311332112312213
322113312312332211
333231
232221
131211
???
??? （ 6）
则当（ 5）的系数行列式
0
aaa
aaa
aaa
D
333231
232221
131211
?? （ 7）
时，方程组（ 5）的解可以用三阶行列式表示为
.
aaa
aaa
aaa
baa
baa
baa
x,
aaa
aaa
aaa
aba
aba
aba
x,
aaa
aaa
aaa
aab
aab
aab
x
333231
232221
131211
33231
22221
11211
3
333231
232221
131211
33331
23221
13111
2
333231
232221
131211
33323
23222
13121
1
???
（ 8）
对于 n元一次方程组，是否也有类似于上述（ 4）、
（ 8）的结果呢？这就是本章要回答的问题 。为解决
这一问题，我们要引入 n阶行列式的概念。作为定义 n
阶行列式的预备知识，下面我们将简单介绍排列的 逆
序数 的概念。
二、排列与逆序数
1、排列与逆序数的定义
把 n个不同元素排成一列，称为一个 全排列 或简
称 排列 （ permutation）。用 Pn表示 n个元素所成全
排列的个数，则 Pn＝ n！。这门课程中我们关心的主
要是一个全排列里面元素的排列次序。 在这 n！个不
同的全排列中，我们规定某一个排列的次序为 标准
顺序 。对自然数，我们规定从小到大的排列顺序为
标准顺序 。
定义 1 在一个排列中，当其中某两个元素的次
序与标准顺序中这两个元素的次序不一致时，我们
称这两个元素产生了一个逆序 (an inverse－ order)。
一个排列中所有的逆序数的总数称为这个排列的逆
序数 (number of the inverse-orders)。
例如，排列 1234的顺序为标准顺序，其逆序数为
0。在排列 1324中，元素 3和 2的次序与它们在标准顺
序中的次序不同（标准顺序中应该是 2排在 3的前面，
因为 2比 3小），因此这两个元素产生了一个逆序,
而其它任意两个元素的排列次序都与其在标准顺序
中的次序一样，因此排列 1324的逆序数为 1。
实际上，根据逆序数的定义，我们可以得到逆
序数的计算方法如下：
nbbb ?,,21
ib ib ib
设有 n个自然数,为这 n个数的一个排
列。则对每个,如果比 大且排在 前面的元素个
数为
it
，就称
ib
在这个排列中的逆序数为
it
，而
ntttt ???? 21
就是这个排列的逆序数。
例 1 求排列 4321576的逆序数。
解 4前面没有数，因此 ;01 ?t
3前面有 1个数（即数字 4）比它大，因此
2前面有 2个数比它大，因此
1前面有 3个数比它大，因此
5前面没有数比它大，因此
7前面没有数字比它大，因此
6前面有 1个数比它大，因此
因此，这个排列的逆序数为：;12 ?t;23 ?t;34 ?t;05 ?t;06 ?t;17 ?t
710032107654321 ??????????????? tttttttt
例 2 求自然数 1,2,…, n组成的排列 n (n – 1)
(n – 2) ··· 21的逆序数 。
解 由前面所述的逆序数的求法，我们可以得到此
排列的逆序数为
2/)1()1(210121 ????????????? ? nnnttttt nn ??
2、排列的奇偶性
定义 2 如果一个排列的逆序数为奇数，则称此
排列为 奇排列 （ odd permutation）；如果一个排
列的逆序数为偶数，则称此排列为 偶排列 （ even
permutation）。
例如，上述例 1中的排列即为奇排列。
定义 3 在一个排列中，将某两个元素对调位置而
其余元素保持不变的操作称为 对换 。
例如，在排列 1234中对换 2和 3，得到新排列
1324。排列 1234为标准排列，因此其逆序数为 0，它
是一个偶排列，而排列 1324的逆序数为 1，这是一个
奇排列。实际上，我们可以证明，这个结论对于一般
的排列也是正确的，即有
定理 1 在一个排列中，进行一次对换，排列改变奇
偶性。
证：先证对换两个相邻元素的情形。
设排列为 nn bbabbaaa ?? 2121 逆序数为 t 。对换
a 和 b 后，排列为 nn bbb a baaa ?? 2121,其逆序数为
't 。
显然排列中除了 a 和 b,其它元素的逆序数保持不变，
只有 a 和 b 的逆序数有可能发生变化。当 ba ? 时，
的逆序数增加 1而 的逆序数不变；当
a
b ba ? 时,的
逆序数不变而
a
b 的逆序数减少 1，总之,1' ?? tt 或者
1' ?? tt 。因此，排列改变奇偶性。
其次，证明一般情况。
kmn ccbcbbabaaa ??? 212121
设排列为,对换 a 和
b
后，
变为
kmn ccacbbbbaaa ??? 212121
。我们可以把它看成是先
m次对换相邻元素 a 与 ),,1( mib
i ??
变成
kmn ccabcbbbaaa ??? 212121
，再 对换 a 和 b,然后作 m
次对换相邻元素
ib
与 )2,1( mib ??,变成
kmn ccacbbbbaaa ??? 212121
。因此，这种情况下，对换
a 和 b,相当于作了 2m+1次相邻元素的对换，故它
改变排列的奇偶性。
由于标准顺序的排列的逆序数为 0，由定理 1我
们有：
推论 1 奇排列变成标准顺序的排列须经过奇数次
对换；偶排列变成标准顺序的排列须经过偶数次对换。
由于 n个不同元素的全排列的总数为 n!，由定理 1，我
们还有：
推论 2 在 n个不同元素的全排列中，奇偶排列各
占一半，均为 n!/2个。
证：设 P为 n个不同元素的全排列组成的集合，其
中 A表示全体奇排列所成的集合,而 B为全体偶排列
所成的集合。显然 P＝ A∪ B，而 P的元素个数为 n!。
设 A的元素个数为 r,B的元素个数为 t。现在我们对 A
中的 r个排列（均为奇排列）都对换其第一、第二个元
素，则我们得到 r个偶排列（即变成了 B中的排列），
故 r≤t。同理，我们可以得到 t≤r。即 r＝ t。
