全排列与逆序数ppt课件

1 时为偶排列；
当 n 4k 2,4k 3 时为奇排列.
3 2k 12k 122k 232k 3k 1k
解
2k 1 2k 1 2 2k 2 3 2k 3k 1 k
方法2 分别计算出排列中每个元素前面比它大的数码 个数之和，即算出排列中每个元素的逆序数， 这每个元素的逆序数之总和即为所求排列的逆 序数. 例1 解 求排列32514的逆序数. 在排列32514中,
3排在首位,逆序数为0;
2的前面比2大的数只有一个3,故逆序数为1;
5的前面没有比5大的数,其逆序数为0;
思考题
分别用两种方法求排列16352487的逆序数.
思考题解答
解 用方法1
1 6 3 5 2 4 8 7
t 0 31 21 01 0 8
用方法2 由前向后求每个数的逆序数.
t 0 0 1 1 3 2 0 1 8.
思考题
证明 在全部 n 阶排列中 n 2 ,奇偶排列各占 一半.
1的前面比1大的数有3个,故逆序数为3;
4的前面比4大的数有1个,故逆序数为1; 3 2 5 1 4 0 1 0 3 1 于是排列32514的逆序数为
t 0 1 0 3 1 5.
例2 计算下列排列的逆序数，并讨论它们的奇 偶性.
1 217986354
解
2 1 7 9 8 6 3 5 4
思考题解答
证 设在全部 n 阶排列中有 s 个奇排列, t 个偶 排列,现来证 s t . 将s 个奇排列的前两个数对换,则这 s个奇排 列全变成偶排列,并且它们彼此不同,所以 s t . 若将 t 个偶排列的前两个数对换, 则这 t 个偶排列 全变成奇排列,并且它们彼此不同,于是有 t s . 故必有 s t .

思考题
分别用两种方法求排列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,故逆序数为

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

Pn = n ⋅ ( n − 1) ⋅ ( n − 2) ⋅ L ⋅ 3 ⋅ 2 ⋅ 1 = n!.
排列的逆序数 我们规定各元素之间有一个标准次序, 我们规定各元素之间有一个标准次序 n 个 不同的自然数，规定由小到大为标准次序 标准次序. 不同的自然数，规定由小到大为标准次序 定义 在一个排列 (i1 i 2 L i t L i s L i n ) 中，若数 it > i s 则称这两个数组成一个逆序 则称这两个数组成一个逆序. 逆序 3 2 5 1 4 逆序
排列的奇偶性 逆序数为奇数的排列称为奇排列 逆序数为奇数的排列称为奇排列; 奇排列 逆序数为偶数的排列称为偶排列 逆序数为偶数的排列称为偶排列. 偶排列
例1 计算排列
n(n-1)(n-2)…321 …321
的逆序数。 的逆序数。
解: 考虑1 8 n(n − 1)(n − 2 )L 321 1 42 43 44 4 4 (n − 2)
t=0+1+＋2＋…+(n-2)+(n-1) =0+1+＋ …+(n-2)+(nn (n − 1 ) = 2
三、小结
理解全排列的概念 掌握全排列逆序数的求法
第一章 第二节
全排列与逆序数
一、概念的引入
引例 三个数字， 用1、2、3三个数字，可以组成多少个没有 、 、 三个数字 重复数字的三位数？ 重复数字的三位数？
解
百位 十位 个位
1 1 2 1 2 3
2 1 3
3
3种放法 种放法 2种放法 种放法 1种放法 种放法
共有 3 × 2 × 1 = 6
种放法. 种放法
二、全排列及其逆序数
问题 把 n 个不同的元素排成一列 ，共有几种不 同的排法？ 同的排法？ 定义 把 n 个不同的元素排成一列，叫做这 n 个 个不同的元素排成一列， 元素的全排列（或排列） 元素的全排列（或排列）.

三、排列的奇偶性
逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列. 定义 把排列中两个元素位置进行对调， 称为对排列作一次对换。 定理：对换改变排列的奇偶性. 证明：先证明是相邻对换的情况，再证非 相邻对换的情况。 推论 将奇（偶）排列变成标准排列需用奇（偶）数 次对换。
第一章
行列式
§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

定义 把 n 个不同的元素排成一列，叫做这 n 个元素的全排列（简称排列）。
n 个不同元素的所有排列的种数，通常用 Pn表 示。
例如, 引例的结果是 P3=3×2×1=6。
上页 下页 返回
计算 Pn 的公式：
首先从 n 个元素中任取一个放在第一个位置上， 有 n 种取法；
又从剩下的 n－1 个元素中任取一个放在第二 个位置上，有 n－1 种取法；
§2 全排列及其逆序数
★全排列的概念 ★逆序的概念 ★计算排列逆序数的方法
由于对角线法则只适用于二、三
阶行列式，为研究四阶及更高阶的行
列式，必须用到逆序数的概念。本节
主要介绍全排列的概念以、3三个数字，可以组成多少个没有重 复数字的三位数？ 解 总共有3×2×1= 6种放法。
这6个不同的三位数是： 123， 132， 213， 231， 312， 321。
上页 下页 返回
全排列的概念
在数学中，把考察的对象叫做元素。 于是引例可抽象成：把 3 个不同的元素排成一列， 共有几种不同的排法？ 一般地，我们可以讨论“把 n 个元素排成一列，共 有几种不同的排法”的问题。
上页 下页 返回
排列分类

奇排列：逆序数为奇数的排列 偶排列：逆序数为偶数的排列
上页 下页 返回
计算排列的逆序数的方法
不妨设 n 个元素为 1 至 n 这 n 个自然数，并
规定由小到大为标准次序。
设
p1 p2 pn
为这 n 个自然数的一个排列。
方法一 在排列 p1 p2 pn 中，直接找出次序颠 倒了的元素对的个数，这也就是该排列的逆序数。
t 0 0 0 0 0 0 2 4 6 8 20

逆序
例如 排列32514 中， 排列
3 2 5 1 4
逆序 逆序
2. 一个排列中所有逆序的总数称为此排列的逆序数. 一个排列中所有逆序的总数称为此排列的逆序数 逆序数. 例如: 其逆序数为5. 例如 排列 32514 , 其逆序数为 其逆序数为4. 排列 31524 , 其逆序数为 3. 排列的奇偶性 逆序数为奇数的排列称为奇排列 逆序数为奇数的排列称为奇排列; 奇排列 逆序数为偶数的排列称为偶排列 逆序数为偶数的排列称为偶排列. 偶排列
4.计算排列逆序数的方法 计算排列逆序数的方法 设排列为 p1 p2 L pn , t i 为 pi 构成的逆序数 则其逆序数为 t = t ( p1 p2 L pn ) = t1 + t 2 + Lt n−1 计算下列排列的逆序数,并讨论它们的奇偶性 并讨论它们的奇偶性. 例 计算下列排列的逆序数,并讨论它们的奇偶性.
二、排列的逆序数
规定各元素之间有一个标准次序, 规定各元素之间有一个标准次序 n 个不同的自 然数, 规定由小到大为标准次序 标准次序. 然数 …pt…ps…pn中, 若数 pt >ps, 则称这两个数组成一个逆序 逆序. 则称这两个数组成一个逆序 (即：大的数在小的数左边, 则这两数构成一个逆序） 即 大的数在小的数左边 则这两数构成一个逆序）
(1) 217986354 ( 2) n( n − 1)( n − 2)L 321
四、小结
1. n个不同的元素的所有排列总数为 个不同的元素的所有排列总数为n!. 个不同的元素的所有排列总数为 2. 排列具有奇偶性 排列具有奇偶性. 3. 计算排列逆序数. 计算排列逆序数
§2 全排列及其逆序数
一、全排列 二、排列逆序数 三、小结

记 D1
1 ta p11a p2 2 a pnn
对于D中任意一项
1
a a t 1 p1 2 p2
anpn
,
总有且仅有 D1 中的某一项 1 s aq1 a1 q2 2 aqnn ,
与之对应并相等; 反之, 对于 D1 中任意一项
1 t a p11a p2 2 a pnn , 也总有且仅有D中的某一项 1s a1q1a2q2 anqn , 与之对应并相等, 于是D与 D1
n 个不同的元素的所有排列的种数，通常
用 Pn表示.
由引例 P3 3 2 1 6. 同理 Pn n (n 1) (n 2) 3 2 1 n!.
排列的逆序数
我们规定各元素之间有一个标准次序, n 个 不同的自然数，规定由小到大为标准次序.
在n个元素的任一排列中，当某两个元素的 先后次序与标准次序不同时,则称这两个数组成 一个逆序.
证明 由定理1知对换的次数就是排列奇偶性的
变化次数, 而标准排列是偶排列(逆序数为0),因此 知推论成立.
定理2 n阶行列式也可定义为
D
1 t a p11a p2 2 a pnn
其中 t 为行标排列 p1 p2 pn的逆序数.
证明 按行列式定义有
D
1 ta1 p1a2 p2 anpn
定义 一个排列中所有逆序的总数称为 此排列的逆序数.
排列的奇偶性 逆序数为奇数的排列称为奇排列; 逆序数为偶数的排列称为偶排列.
例1 求排列32514的逆序数. 解 在排列32514中, 3排在首位,逆序数为0; 2的前面比2大的数只有一个3,故逆序数为1; 5的前面没有比5大的数,其逆序数为0; 1的前面比1大的数有3个,故逆序数为3;
中的项可以一一对应并相等, 从而 D D1.

2020/3/1
22
五、关于等价定义的说明
对于行列式中的任一项
(1) a1p1...aipi ...a jpj ...anpn
(1)
其中 1...i... j...n为自然排列， 为列下标排
列 p1...pi...p j... pn 的逆序数。对换 (1) 中元
素a
与
ip i
a jp
j
成：
(1) a1p1...a jpj ...aipi ...anpn
解：∵ 排列p1 p2 p3…pn与排列 pn…p3 p2 p1的逆序
数之和等于1～ n 这 n 个数中任取两个数的组合
数即 ：

(
p1 p2... pn )

(
pn
pn1... p1)

Cn2

n(n 1) 2

(
pn
pn1... p1)

n(n 1) 2

k
2020/3/1
9
例4 求排列(2k)1(2k 1)2(2k 2)...(k 1)k
a22 ...
... a2n ... ...
a11a22...ann
0 0 ... ann
2020/3/1
16
3) 次上三角行列式
a1,1 ... a1,n1 a1,n
a2,1 ... a2,n1 ... ... ...
0 ...
n ( n 1)
(1) 2 a1,na2,n1...an,n
例6 若 a13a2ia32a4k , a11a22a3ia4k , ai2a31a43ak 4 为四阶行列式的项，试确定i与k，使前两项带正号， 后一项带负号。