全排列及其逆序数

此排列当 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的逆序数.

逆序 例 312 逆序 此排列的逆序数为1+1=2.
定义:逆序数为奇数的排列叫做奇排列, 逆序数为偶数的排列叫做偶排列.
§2
全排列及其逆序数
计算排列逆序数的方法
分别计算出排列中每个元素前面比它大的数
码个数之和,即算出排列中每个元素的逆序数,这
每个元素的逆序数之总和即为所求排列的逆序数.
§2
全排列及其逆序数
§2
全排列及其逆序数
定义:对于n个不同的元素,规定各元素之间有一个标准次 序(通常规定由小到大为标准次序).
例 123 是元素1,2,3的标准次序
定义: 在这n个元素的任一排列中,当某两个元素的先后次 序与标准次序不同时就说有1个逆序. 逆序 逆序 例 132 213
§2
全排列及其逆序数
定义: 一个排列中所有逆序的总数称为这个排列的逆序数.
§2
全排列及其逆序数
主要内容：
一、全排列
二、排列的逆序数
考察的对象称为元素.例如:数字1,2,3.
定义:把n个不同的元素排成一列,叫做这n个元素的全 排列(简称排列). n个元素的所有排列的种数用Pn表示.
例 123,321,132,312,213,231都是元素1,2,3的排列, P3＝3×2 ×1 ＝ 6. 由上例可推知Pn＝ n！
例 求排列3241的逆序数 解: 3排在首位,逆序数为0; 2的前面比2大的数有一个数3,故逆序为1; 4是最大数,逆序为0; 1的前面比1大的数有3个数3、2、4,故逆序数为3.
于是,这个排列的逆序数为t=0+1+0+3=4,
排列3241为偶排列.
§2
总结
全排列及其逆序数
1.n个不同的元素的所有排列种数为n!. 2.排列具有奇偶性. 3.计算排列逆序数常用的方法有1种.

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)

n 个不同的元素的所有排列的种数,通常 个不同的元素的所有排列的种数,
用 P 表示 n表示. 由引例 P3 = 3 2 1 = 6. 同理
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 则称这两个数组成一个逆序 则称这两个数组成一个逆序.
t = ( n 1) + ( n 2 ) + L + 2 + 1
时为奇排列. 当 n = 4k + 2,4k + 3 时为奇排列
机动 目录 上页 下页 返回 结束
第一章 行列式
(3) (2k )1(2k 1)2(2k 2)3(2k 3 )L(k + 1)k
解
(2k ) 1 (2k 1) 2 (2k 2) 3 (2k 3)L(k + 1) k
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