1-2全排列及其逆序数

例如 排列32514 中， 0 01
32514
1 逆序数为3
故此排列的逆序数为3+1+0+1+0=5.
记做 (3 2 514) 5
排列的奇偶性 逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列. 例如，在123组成的全排列中，有3个偶排列123， 231，312；有三个奇排列132，213，321 ❖一般说来，n 个数的全排列中，奇偶排列各占一半。
第二排列及其逆序数
1 全排列 2 排列的逆序数 3 逆序数的计算方法
问题 把 n 个不同的元素排成一列，共有几种不 同的排法？
定义1
把 n 个不同的元素排成一列，叫做这 n 个元素的全排列（简称排列）.
n 个不同的元素的所有排列的种数，通 常用 Pn 表示.
例如 P3 3 2 1 6.
同理 Pn n (n 1) (n 2) 3 2 1 n!.
32514 5的前面没有比5大的数,其逆序数为0; 1的前面比1大的数有3个,故逆序数为3; 4的前面比4大的数有1个,故逆序数为1;
32514 01 031 于是排列32514的逆序数为
0 1 0 3 1 5. (从头开始法)
例2 计算下列排列的逆序数，并讨论它们的奇 偶性.
1 217986354
分别计算出排列中每个元素前面比它大的数码 个数之和，即从排列中第一个元素开始，依次 算出排列中每个元素的逆序数，这每个元素的 逆序数之总和即为所求排列的逆序数.（从“头” 开始法） 例1 求排列32514的逆序数.
解 在排列32514中,
3排在首位,逆序数为0;
2的前面比2大的数只有一个3,故逆序数为1;
我们规定各元素之间有一个标准次序, n 个 不同的自然数，规定由小到大为标准排列（自然 排列）.

§2 全排列及其逆序数
一、概念的引入 二、全排列 三、排列逆序数 四、小结
一、概念的引入
引例 三个数字， 用1、2、3三个数字，可以组成多少个没 、 、 三个数字 有重复数字的三位数？ 有重复数字的三位数？
共有 3 × 2 × 1 = 6 种.
上 例也 可表 述为 ： 把 3个不 同的 元素 排成 一列 ，共 有几 种不 同的 排法 ？
4.计算排列逆序数的方法 4.计算排列逆序数的方法
即分别计算出排列中每个元素前面比它大的数 个数之和 例1 的逆序数. 求排列 32514 的逆序数
例2 计算下列排列的逆序数 （1）12345 （2）n ⋅(n -1)⋯ 2 ⋅1
四、小结
1 n 个不同的元素的所有排列种数为 n!. 排列具有奇偶性. 2 排列具有奇偶性. 3 计算排列逆序数的方法 计算排列逆序数的方法.

1 2 t s n
总数称为此排列的逆序数, 总数称为此排列的逆序数,记为 t(p1p 2 ⋯ p t ⋯ ps ⋯ pn ) 逆序数 此排列的逆序数为3. 例如 排列 321 中，此排列的逆序数为
3. 排列的奇偶性
逆序数为奇数的排列称为奇排列; 逆序数为奇数的排列称为奇排列; 奇排列 逆序数为偶数的排列称为偶排列 偶排列. 逆序数为偶数的排列称为偶排列.
问题： n 个不同的元素排成一列，共有几种不同的排法？
共有n!种 共有 种
二、全排列
个不同的元素排成一列， 定义 把 n 个不同的元素排成一列，叫做这 n 个 元素的全排列（或排列） 元素的全排列（或排列）.
二、排列的逆序数
n 个不同的自然数，我们规定由小到大为标准次序 个不同的自然数，我们规定由小到大为标准次序 标准次序. 1. 定义 在一个排列 p1 p2 ⋯ pt ⋯ ps ⋯ pn 中, 若数 pt > ps , 则称这两个数组成一个逆序 则称这两个数组成一个逆序. 排列321 中， 例如 排列 32,31,21就构成逆序 就构成逆序 就构成

左
3 2 32 8/2=4 4 1 31 21 41 因此，计算排列的逆序数时，对每个元素只需考虑它 与左边(或右边)的元素所构成的逆序.
目录 上页 下页
右 32 31 21 41
排列的逆序数
对于排列中的一个元素，左边比它大的数的个数， 叫做该元素的逆序数 . 排列的逆序数 = 排列中各个元素的逆序数之和. 定义 4 排列的奇偶性 逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列. 说明 一个排列不是奇排列就是偶排列.
目录
上页
下页
作业
计算以下排列的逆序数，并判断奇偶性
①1 3 4 2 6 5 ;
②2 4 … (2n) (2n-1) (2n-3) … 1
目录
上页
下页
思考题
分别用两种方法求排列 163பைடு நூலகம்2487 的逆序数.
目录
上页
下页
思考题解答
方法 1 求出每个元素的逆序数, 并相加
t 0 011 3 2 01 8
目录
上页
下页
例 1 求排列 32514 的逆序数，并说明它的奇偶性.
分析 3： 排在首位, 逆序数为 0; 2： 前面比 2 大的数只有一个 3, 故逆序数为 1; 5： 前面没有比 5 大的数, 其逆序数为 0; 1： 前面比 1 大的数有 3 个, 故逆序数为 3; 4： 前面比 4 大的数有 1 个, 故逆序数为 1. 解 3 2 5 1 4
解
n 1 (1) nn 1n 2 3 2 1 n2 nn 1 t n 1 n 2 2 1 0 2 当 n 4k , 4k 1 (kN) 时，为偶排列, 当 n 4k 2, 4k 3 (kN) 时，为奇排列.

x1

b1a22 a11a22
a12b2 a12a21

x2

a11b2 a11a22
b1a21 a12a21

x1

b1a22 a11a22
a12b2 a12a21

x2

a11b2 a11a22
b1a21 a12a21

5
第一章 行列式
我们用符号
aa1211表aa示1222代数和a11a22a12a21
解： 1 3 … （2n-1） 2 4 … 2k… （2n)
D3x24x189x2x212x25x6
即x25x60
x2或x3
值得注意的是：四阶及四阶以上行列式没有像二、三阶 行列式那样的对角线法则
13
第一章 行列式 §1-2 全排列及其逆序数
[引例]用1、2、3三个数字 可以组成多少个没有重复数字的 三位数？
[解依] 次选定百位数、十位数、个位数。 百位数有3种选法 十位数有2种选法 个位数有1种选法 所以可以组成6个没有重复数字的三位数 这6个三位数是 123 132 213 231 312 321
十八世纪开始，行列式开始作为独立的数学概念被研究。 十九世纪以后，行列式理论进一步得到发展和完善。
3
第一章 行列式
莱布尼茨：历史上少见的通才，被誉为 十七世纪的亚里士多德。在数学上，他 和牛顿先后独立发明了微积分。在哲学 上，莱布尼茨的“乐观主义”最为著名 。 他对物理学的发展也做出了重大贡献 。
并称它为三阶行列式。
10
第一章 行列式
2、行列式中的相关术语
行列式的元素、行、列、主对角线、副对角线 3、三阶行列式的计算 （对角线法则或沙路法则 ）

τ ( j1 j2 ⋯ jn−1 jn )= ∑ ( jk 后面比jk 小的数的个数 )
k =1
n −1
信息系 刘康泽
例4 （1）排列31425 的逆序数为： ）排列31425 的逆序数为： τ(31425)=2+0+1+0+0=3 ； (31425)=2+0+1+0+0=3 （2）自然排列 1 2 3 • • • n 的逆序数是0 ； 的逆序数是 （3）排列 n (n –1) • • • 21 的逆序数为： 的逆序数为： n(n − 1) τ = (n − 1) + (n − 2) + ⋯ + 1 + 0 = 2 例5 求排列 ( 2k )1( 2k − 1) 2 ( 2k − 2 ) 3 ( 2k − 3)⋯ ( k + 1) k 的逆序数。 的逆序数。 解： (2k ) 1 (2k − 1) 2 (2k − 2 ) 3 (2k − 3 )⋯(k + 1) k
信息系 刘康泽
第1-2节 排列及行列式的定义
信息系 刘康泽 一、排列及其逆序数
1. n 级排列
由 排成的一个有序数组， 【定义】 n 个不同的数 1, 2,⋯ , n 排成的一个有序数组， 定义】 级全排列， 级排列。 称为一个 n 级全排列，简称 n 级排列。
例1 53214 45238176
1 2 3⋯ n n( n − 1) ⋯ 321
∑
j1 j2 ⋯ jn
表示对 表示对所有
信息系 刘康泽
【注】 1、以 aij 作为元素的 n 阶行列式有时简记为 det( aij ) 。 、 2、行列式表示一个特定的数，它是n行n列的表中 、行列式表示一个特定的数，它是 行 列的表中 所有位于不同行、 个元素乘积的代数和。 所有位于不同行、不同列 的n 个元素乘积的代数和。 共有 n ! 项求和。 项求和。 3、求和项 a1 j1 a2 j2 ⋯ an jn中的行排列总是按自然次 、 序排列的，且该项的符号取决于列排列的逆序数，即为： 序排列的，且该项的符号取决于列排列的逆序数，即为：

01 031 于是排列32514的逆序数为 t = 0+1+0+3+1 = 5.
•奇排列：逆序数为奇数的排列; •偶排列：逆序数为偶数的排列.
例2: 计算下列排列的逆序数, 并讨论其奇偶性.
(1) 217986354.
217986354
解: 该排列逆序数为:
0 1001344 5
t = 0+1+0+0+1+3+4+4+5 = 18. 此排列为偶排列.
1. n个不同的元素的所有排列种数为n!个; 2. 排列具有奇偶性; 3. 计算排列逆序数常用的方法.
(2) n(n–1)(n–2) ···2 1 解: n (n–1) (n–2) ···2 1
0 1 2 ···(n–2) (n–1)
于是此排列的逆序数为:
t = 0+1+2+ ···+(n–2)+(n–1) nn 1,
2 当 n=4k, 4k+1 时为偶排列; 当 n=4k+2, 4k+3 时 为奇排列.
四、对换与排列奇偶性的关系
定理1: 排列中的任意两个元素对换,排列改变奇偶性.
推论1: 奇排列调成标准排列的对换次数为奇数, 偶排 列调成标准排列的对换次数为偶数. 推论2: n个自然数的所有排列中奇偶排列各占一半.
证明: 先考虑相邻对换的情形. 例如 a1 a2 ···al a b b1 ···bm 对换 a与b a1 a2 ···al b a b1 ···bm 即除 a, b 外, 其它元素的逆序数不改变.
当 a<b 时, 对换后 a 的逆序数增加1, b 的逆序数不变; 当 a>b 时, 对换后 a 的逆序数不变, b 的逆序数增加1; 因此, 相邻对换排列改变奇偶性.

本节内容已结束 ! 本节内容已结束 ! ! ! ! 本节内容已结束 本节内容已结束 本节内容已结束 本节内容已结束 若想结束本堂课, 若想结束本堂课, , ! ! 本节内容已结束 若想结束本堂课, 若想结束本堂课, 若想结束本堂课, 若想结束本堂课, , , ! 若想结束本堂课 若想结束本堂课 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮. . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮. 请单击返回按钮. 请单击返回按钮. . . 请单击返回按钮 请单击返回按钮 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 , ! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 ,! 请单击返回按钮. 请单击返回按钮 . 本节内容已结束 若想结束本堂课, 若想结束本堂课 请单击返回按钮. 请单击返回按钮 . , 若想结束本堂课, 若想结束本堂课 请单击返回按钮. 请单击返回按钮 ., 若想结束本堂课, 若想结束本堂课 请单击返回按钮. 请单击返回按钮 ,. 若想结束本堂课, 若想结束本堂课 . 请单击返回按钮. 请单击返回按钮 请单击返回按钮. 请单击返回按钮 请单击返回按钮. 请单击返回按钮.. 请单击返回按钮. 请单击返回按钮

即 n 个不同的元素一共有n! 种不同的排法.
（这里暂时Байду номын сангаас把元素想象成是写有编号的小球）
3个不同的元素一共有3! = 6种不同的排法
123，132，213，231，312，321
所有6种不同的排法中，只有一种排法 （123）中的数字是按从小到大的自然 顺序排列的，而其他排列中都有大的 数排在小的数之前. 因此大部分的排列都不是“顺序”， 而是乱序的，或者说其中有“逆序”.
练习1：求排列 453162 的逆序数. （奇排列）
解： （t 453162） 0+2+3+0+4 9
练习2： 求排列 463152 的逆序数. （偶排列）
t（463152） 0+0+2+3+1+4 10
猜想：对换一次改变排列的奇偶性？书P5
二、对换的定义
定义
在排列中，将任意两个元素对调，其余的元素 不动，这种作出新排列的手续叫做对换．
将相邻两个元素对换，叫做相邻对换．
例如
a1 al a b b1 bm a1 al b a b1 bm
a1 al a b1 bmb c1 cn a1 al b b1 bma c1 cn
三、对换与排列奇偶性的关系
定理1 对换改变排列的奇偶性.
证明 先考虑相邻对换的情形．
t ta1
tal ta tb tb1
§2 全排列和对换
为了研究 n 阶行列式的定义，我们首 先来学习全排列和逆序数的概念
一、排列及其逆序数
问题 把 n 个不同的元素排成一列，共有多少种不同的
排法？
定义 把 n 个不同的元素排成一列，叫做这 n 个元素 的全排列. n 个不同元素的所有排列的种数，通常用 Pn 表示.

(q1q2 qn )
an1 an 2 ... ann


q1q2 ...qn
(1) aq 1aqq 2 ...aq n
1 2 n

(1)
1 2
al s al s ...al
1 1 2 2
n sn
1 (l1l2 ln )
2 ( s1s2 sn )
例如 排列32514 中，
逆序 3 2 5 1 4 逆序 逆 逆序
排列的奇偶性 逆序数为奇数的排列称为奇排列;
逆序数为偶数的排列称为偶排列.
计算排列逆序数的方法 分别计算出排列中每个元素前面比它大的数码 个数之和，即算出排列中每个元素的逆序数， 这每个元素的逆序数之总和即为所求排列的逆序数.
例1
推论1
奇排列变成自然排列的对换次数为奇数， 偶排列变成自然排列的对换次数为偶数。
推论2 n 2 时，全体
n 级排列中，奇排列和偶排列
n! 2
的个数相等，各为
个。
三阶行列式
a 11 D a 21 a 31 a 12 a 22 a 32 a 13 a 23 a 11 a 22 a 33 a 12 a 23 a 31 a 13 a 21 a 32 a 33
的三个元素的下标排列．
n 二、 阶行列式的定义
定义1 由 n 2 个数 a ij ( i , j 1, 2, n )
a 11 称记 号 D a 21 a n1 a 12 a 22 an2
排成 n 行 n 列
a1 n a2n a nn


i1 i 2 i n
( 1)
小结
1 n 个不同的元素的所有排列种数为 n !.

al a bb1
bm
对换 a 与 b
a1
al b ab1
bm
除a,b外，其它元素的逆序数不改变. 逆序数加1或减1，奇偶性改变.
2)
一般情形
对换a与b
a1 al a b1 bm b b c1 cn
a1 al ab1 bm bc1 cn
a1
al bb1
bm ac1
cn ,
m 次相邻对换 a 1
若将t 个偶排列的前两个数对换, 则这t 个偶排列 全变成奇排列,并且它们彼此不同,于是有 t s . 故必有 s t .
本节小结
1. n元排列 2. 逆序 3. 逆序数 4. 奇偶排列 5. 对换 结论1 任一排列经过一次对换奇偶性改变. 结论2 全部n元排列中,奇偶排列各占一半.
t 18
例2 讨论排列 n n 1 n 2 解
nn 1n 2321
n1 n2
321的奇偶性.
t n 1 n 2 2 1 n n 1 , 2 当n 4k ,4k 1 时为偶排列；
当n 4k 2,4k 3 时为奇排列.
例3 选择i和j,使1i25j4869成为奇排列、偶排列.
1
4.对换
n元排列中, 任意对调两个元素的位置,其余元素 不动,这种变换叫做对换．
奇 偶
25143
偶
25413
奇
这些排列的
奇偶性呢？
2 1 6 排列经过一次对换必改变奇偶性. 证明 1) 特殊情形：相邻对换 设排列为 a1
2.逆序
n元排列中,若较大的元素排在较小的元素 前面，称为一个逆序. 比如 3 2 5 1 4
3.逆序数
排列中所有逆序的总数称为此排列的逆序数.