全排列与逆序数

此排列当 n=4k, 4k+1 时为偶排列; 当 n=4k+2, 4k+3 时为奇排列. (3) (2k)1(2k–1)2(2k–2)3(2k–3) · (k–1)(k +1)k. · · · · 解: (2k) 1 (2k–1) 2 (2k–2) 3 (2k–3) · (k–1) (k+1) k (k–1) (k–1) k 3 0 1 1 2 2 3 于是排列(2k)1(2k–1)2(2k–2) · (k–1)(k +1)k的逆序数为: · · t = 0+1+1+2+2+ · +(k–1)+(k–1)+k · · k k 1 2 k k2. 2 此排列当 k 为偶数时为偶排列, 当 k为奇数时为 奇排列.
例2: 计算下列排列的逆序数, 并讨论其奇偶性. (1) 217986354. 解: 2 1 7 9 8 6 3 5 4 0 1 001 34 4 5 于是排列217986354的逆序数为: t = 0+1+0+0+1+3+4+4+5 = 18. 此排列为偶排列. (2) n(n–1)(n–2) · 21 · · · · 解: n (n–1) (n–2) · 2 1 2 (n–2) (n–1) 0 1 于是排列n(n–1)(n–2) · 21的逆序数为: · · nn 1 , t = 0+1+2+ · +(n–2)+(n–1) · · 2
方法2: 依次计算出排列中每个元素前面比它大的 数码个数并求和, 即算出排列中每个元素的逆序数, 则 所有元素的逆序数之总和即为所求排列的逆序数. 例1: 求排列32514的逆序数.

n( n 1 ) , = 2 时为偶排列； 当 n = 4k ,4k + 1 时为偶排列；
t = ( n 1) + ( n 2 ) + L + 2 + 1
时为奇排列. 当 n = 4k + 2,4k + 3 时为奇排列
(4) (2k )1(2k 1)2(2k 2)3(2k 3)L (k + 1)k
于是排列32514的逆序数为 t = 0 + 1 + 0 + 3 + 1 = 5. 的逆序数为 于是排列
计算下列排列的逆序数，并讨论它们的奇偶性. 例2 计算下列排列的逆序数，并讨论它们的奇偶性
(1)
4132
(2) 3712456
（2） ）
解（1）4 1 3 2 ）
3 7 1 2 4 5 6
0 0 2 2 1 1 1
第二节 全排列及其逆序数
一、排列
定义 由自然数 2, , n 组成的不重复的每一 由自然数1, 种有确定次序的排列, 称为一个n 种有确定次序的排列 称为一个 阶排列 (简称排列 简称排列). 简称排列 都是4 例如 1234 和4312都是 阶排列 都是 阶排列, 24315是一个 阶排列 是一个5 阶排列. 是一个
t = 0 +0 + 2 + 2 + 1 + 1 + 1
0 1 1 2
t = 0+1+1+ 2 = 4
此排列为偶排列 此排列为偶排列. 偶排列
=7
此排列为奇排列 此排列为奇排列. 奇排列
(3)
解
n(n 1)(n 2 )L 321
n 6444 74444 4 1 8 n(n 1)2 2 )L 321 1 4(n443 44 4 (n 2)

0 1


1

2

2

0 1 1 2 2 k 1 k 1 k
2 当 k 为偶数时，排列为偶排列，

k

21 k 1k 1
2 k k ,
当 k 为奇数时，排列为奇排列.
机动
目录
上页
下页
返回
结 n ( n 1) ( n 2) 3 2 1 n!.
机动 目录 上页 下页 返回 结束
LOGO
排列的逆序数 我们规定各元素之间有一个标准次序, n 个 不同的自然数，规定由小到大为标准次序.
定义 在一个排列 i1 i 2 i t i s i n 中，若数 i t i s 则称这两个数组成一个逆序. 例如 排列32514 中， 逆序 3 2 5 1 4
1 n 个不同的元素的所有排列种数为 n!. 2 排列具有奇偶性.
机动
目录
上页
下页
返回
结束
思考题
求排列16352487的逆序数. 解 1 6 3 5 2 4 8 7
LOGO
0 0 1 1 3 2 0 1 8.
机动
目录
上页
下页
返回
结束
LOGO 2012年秋
计算排列逆序数的方法
LOGO
分别计算出排列中每个元素前面比它大的数码 个数之和，即算出排列中每个元素的逆序数， 这每个元素的逆序数之总和即为所求排列的逆 序数.
机动
目录
上页
下页
返回
结束
例1
解
求排列32514的逆序数.
在排列32514中,
LOGO

思考题
分别用两种方法求排列16352487的逆序数 的逆序数. 分别用两种方法求排列 的逆序数
思考题解答
解 用方法1 用方法1 1 6 3 5 2 4 8 7
t = 0+ 3+1+ 2+1+ 0+1+ 0= 8
用方法2 用方法2 由前向后求每个数的逆序数. 由前向后求每个数的逆序数
t = 0 + 0 + 1 + 1 + 3 + 2 + 0 + 1 = 8.
t = 0 + 1 + 0 + 3 + 1 = 5.
计算下列排列的逆序数， 例2 计算下列排列的逆序数，并讨论它们的奇 偶性. 偶性
(1) 217986354
解
2 1 7 9 8 6 3 5 4
0 10 0 1 3 4 4 5
t = 5 + 4 + 4+ 3+1+ 0+ 0+1+ 0
= 18
此排列为偶排列 此排列为偶排列. 偶排列
一、概念的引入
引例 用1、2、3三个数字，可以组成多少个没 三个数字， 、 、 三个数字 有重复数字的三位数？ 有重复数字的三位数？ 解
百位 十位 个位
1 1 1 2 1 2 3
2 2 1 3
3 3
3种放法 种放法 2种放法 种放法 1种放法 种放法
共有 3 × 2 × 1 = 6
种放法. 种放法
3排在首位 逆序数为 排在首位,逆序数为 排在首位 逆序数为0; 2的前面比 大的数只有一个 故逆序数为 的前面比2大的数只有一个 故逆序数为1; 的前面比 大的数只有一个3,故逆序数为

行列式是线性代数中的重要概念，它是以可排列的逆序奇偶性为基础，由行列地位相同的不重复行列元素乘积项的代数和构成。为了深入理解行列式，需要掌握全排列和逆序数的概念。全排列是从n个元素中取出n个元素进行不重复有逆序之和，根据逆序数的奇偶性，可以将排列分为奇排列和偶排列。求逆序数的基本方法是通过逐一考察每个元素前面的逆序元素个数，并求和得到。此外，对换是排列中的一种重要操作，它可以改变排列的奇偶性。这些概念和性质对于后续学习行列式的计算和应用具有重要意义。

例3 用行列式的定义计算
0 0 0 1 0 0 0 2 0 0 Dn n1 0 0 0 0 0 0 0 0 n
解 Dn 1 t a1,n1a2,n2 an1,1ann
1t 1 2 n 1 n 1t n!, tn 1n 2 21n
01 2L n 3 n 2 0
1234
例3 计算
0 D
4
2
1
0056
0008
解
1234Βιβλιοθήκη 0421D 00
5
6 a11a22a a 33 44 1 4 5 8 160.
0008
同理可得下三角行列式
a11
0 0 0
a21 a22 0 0
an1
an2
an3 ann
a11a22 ann .
例4 证明对角行列式
1 2
因此对换相邻两个元素，排列改变奇偶性 . 再证一般对换的情形 .
设排列为 a1 alab1 bmbc1 cn , 现来对换 a 与b.
a1 al a b1 bm b c1 cn
m 次相邻对换 a1 al ab b1 bmc1 cn
m 1 次相邻对换 a1 al b b1 bm a c1 cn
t 0 1 0 3 1 5.
例2 计算下列排列 nn 1n 2L 321
的逆序数，并讨论它的奇偶性.
解
t 1 2 L (n 2) n 1
nn 1
,
2
当 n 4k,4k 1 时为偶排列；
当 n 4k 2,4k 3 时为奇排列.
第一章 行列式
第三节 n 阶行列式的定义
一、概念的引入
1
a a t p1q1 p2q2
a pnqn

0+1+0+2+4=7
故排列42531的逆序个数为7，即τ(42531)=7，
因而是奇排列.
返回
上一页 下一页
(2) 同理可得：
τ[135…(2n-1)246…(2n)]=0+(n-1)+(n-2)+…+2+1=
n(n 1) 2
所给排列当n=4k或4k+1时为偶排列，当n=4k+2或4k+3
时为奇排列.
把行列式
§3 行列式的性质
的行换成同序数的列,
称为行列式D的转置行列式。
返回
上一页 下一页
性质1 行列式与它的转置行列式相等 。
证： 记
即bij＝aji
(i，j＝1，2，…，n)
按行列式定义
返回
上一页 下一页
性质2 互换行列式的两行（列），行列式反号。 证
交换第p、q两列，得行列式
返回
上一页 下一页
同理可证
返回
上一页 下一页
代数余子式的重要性质（行列式按行（列）展开公式）:
返回
上一页 下一页
例 计算n阶行列式 解法一
返回
上一页 下一页
例 计算n阶行列式
解法二(递推法) 由行列式Dn可知
将Dn按第1列展开
返回
上一页 下一页
这个式子对任何n(n2) 都成立,故有
返回
上一页 下一页
例 利用递推公式法计算 解：按第一行展开
Dn＝
返回
上一页 下一页
例 证明
上面的行列式中，未写出的元素都是0。 证: 因为行列式的值为
而排列j1j2…jn只能是n(n－1)…21的排列， 故逆序数

三、排列的逆序数
我们规定各元素之间有一个标准次序, n 个 不同的自然数，规定由小到大为标准次序. 1. 定义 在一个排列 p 1 p 2 p t p s p t p s , 则称这两个数组成一个逆序.
p n 中,
若数
(即：大的数在小的数左边，则这两数构成一个逆序） 例如 排列32514 中， 逆序 3 2 5 1 4
t N(p514 的逆序数.
例2
计算下列排列的逆序数，并讨论它们的
奇偶性.
1 2
217986354 n n 1 n 2 321
逆序
逆序
2. 定义 一个排列中所有逆序的总数称为此排
列的逆序数. 例如 排列 32514 中，
3. 排列的奇偶性
逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列.
4.计算排列逆序数的方法
设排列为 p 1 p 2 则其逆序数为 例1
pn , ti 为 pi
构成的逆序数
t1 t 2 t n 1
P3 3 2 1 6 .
P n n ( n 1 ) ( n 2 ) 3 2 1 n !.
1. 由1,2,…,n-1,n（n个数）组成的一个全排列称 为一个n级排列。 如：12345，54321，43512均为5级排列 2. 123…(n-1)n(具有自然顺序的排列为)标准排列。
§2 全排列及其逆序数
一、概念的引入
二、全排列
三、排列逆序数 四、小结
一、概念的引入
引例 用1、2、3三个数字，可以组成多少个没 有重复数字的三位数？
共有 3 2 1 6
种放法.
二、全排列
问题

1，2显，然3叫，做百元位素上.可上以述从问1，题2就，是3三：个把数三字个中不任同选的
元一素个排，所 成一以有列，3种共放有法几；种十不位同上的只排能法从？剩下的两个 数字中选一个，所以有2种放法； 而个位上只能放 最后剩下的一个数字，所以只有1种放法. 因此，
二、全排列
对于 n 个不同的元素，也可以提出类似的问 题： 把 n 个不同的元素排成一列，共有几种不同 的排法？ 为此先给出全排列的定义.
定义 把 n 个不同的元素排成一列，叫做这 n 个元素的全排列（也简称排列）.
n 个不同元素的所有排列的种数，通常用 Pn 表
示. 由引例 用1的，结2，果3可三知个P数3 =字3可·以2 ·组1 成= 6多. 少个没
有重复数字的三位数？
解 这个问题相当于说，把三个数字分别放在
为了得出计算 Pn 的公式，可以仿照引例 用1，2
进行讨论：
有重复数字的三位
从 n 个元素中任取一个放在第一个位解置上这位与个数
从剩下的 n – 1 个元素中任取一个放在显第然二，百位上
个位置上，有 n – 1 种取法；
一个，所以有3种放
这样继续下去，直到最后只剩下数一字个中元选素一放个，所
在第 n 个位置上，只有 1 种取法. 于最是后剩下的一个数
2. 计算方法
下面来讨论计算排列的逆序数的方法. 不失一般性，不妨设 n 个元素为 1 至 n 这 n 个 自然数， 并规定由小到大为标准次序. 设
p1 p2 pn
为这 n 个自然数的一个排列，考虑元素 pi （i = 1, 2, … , n）， 如果比 pi 大的且排在 pi 前面的元素有 ti 个，就说 pi 这个元素的逆序数是 ti . 全体元素的 逆序数之和

三、排列的奇偶性
逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列. 定义 把排列中两个元素位置进行对调， 称为对排列作一次对换。 定理：对换改变排列的奇偶性. 证明：先证明是相邻对换的情况，再证非 相邻对换的情况。 推论 将奇（偶）排列变成标准排列需用奇（偶）数 次对换。
第一章
行列式
§1.1 全排列及其对换
一、全排列的定义 n 个不同的元素排成一列，叫做这 n
个元素的全排列，简称排列。 例 123456 是 6 个数的全排列， 53421 是 5 个数的全排列。
二排列的逆序数
对于n 个不同的元素，规定各元素之间由小 到大为标准次序. 定义 当某两个元素的先后次序与标准次序不同 时，就说有一个逆序，一个排列中所有逆序的总 数叫做这个排列的逆序数。 求逆序数的方法： t ( p1 p2 pn ) t1 t2 tn 其中 ti 是排列中与元素 pi 相关的逆序数，即位于 pi前且比 pi 大的的元素个数。
例 (1) 求排列3412中逆序数 .
2 nn 1n 2 321
(1) t (3412) 0 0 2 2 4; 解：
(2) t (n n 1 n 2 321) 0 1 2 (n 1) 1 n(n 1) 2