第二节 排列及其逆序数

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)

1,2,3 ；1,3,2 ； 2,1,3 ； 2,3,1 ；3,1,2 ； 3,2,1
（2）逆序：在一个排列里，如果某一个较大的数排在某一 个 较小的数前面，则称这两个数码构成一个逆序； 例3 ：5 阶排列 4,3,5,2,1 中 4,3 、4,2 、4,1 及 3,2 、 3,1
5,2 、5,1 、2,1 等均构成反序，且共8 个反序；
（3）逆序数：在一个排列 i1 , i2 , , in 里，出现的逆序 总个数称为这个排列的逆序数；并记作 i1 , i2 , , in 例4 ：例 3 中 5 阶排列 4,3,5,2,1 中，逆序数为 8 即： 4,3,5,2,1 8
逆序数的计算：在一个排列 i1 , i2 , , in 里，先看有多少
特别，称 1,2, , n 为这
例1 ：1,2,3,4,5 ； 5,4,3,2,1 ； 3,2,1,5,4 ； 3,4,5,1,2 等等，均为 1,2,3,4,5 这5 个数码的不同排列； 结论： n 个数码 1,2, , n 的所有排列共 n! 个。
例2： 3个数码的不同排列共 3! 6 个，分别为
4,7,5,1,3,6,2 m1 m2 m3 m4 m5 m6 m7
3 5 3 0 11 0 13
（4）奇偶排列：若 i1 , i2 , , in 是奇数，则称 排列 i1 , i2 , , in 为奇排列； 排列 i1 , i2 , , in 为偶排列； 例6： 3 阶排列中 若 i1 , i2 , , in 是偶数，则称
个数排在 1 的前面，设有 m1 个，即有 m1 个数与1 构成反序； 将 1 划去；再看有多少个数排在 2 的前面，设有 m2 个，将 2 划去；‥ ‥ ‥ ，如此下去，设有 mn1 个数排在 n 1 的 前面，将 n 1 划去，最后只剩下数 n ，即 mn 0 则 i1 , i2 , , in m1 m2 mn1 mn 例5 ：7 阶排列 4,7,5,1,3,6,2 中，

例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

τ (45321) = 3 + 3 + 2 + 1 = 9
例 在n级排列1,2,…,n中，各数是按照由小到大的 自然顺序排列，这一排列称为n元自然序排列， n元自然序排列 由于其中任何一个数对都不构成逆序，因此
τ (12⋯n) = 0
另外
τ (n, n − 1,⋯,1)
= (n − 1) + (n − 2) + ⋯ + 1
二、逆序数
1、逆序和逆序数 在n级排列
j1 , j2 ,⋯ , jn 中， 如果有一个较大的数
js 排在较小的数 jt 的前面，即
j s > jt ( s < t )
构成一个逆序 逆序。 逆序
称这一对数
js , jt
一个排列中逆序中的总数，称为这个排列的逆序数 逆序数， 逆序数 记为： τ
( j1 , j 2 , ⋯ , j n )
2、例题 例 求排列45321的逆序数 解 在排列45321中， 4和后面的数形成的逆序有3个：43,42,41； 5和后面的数形成的逆序有3个：53,52,51； 3和后面的数形成的逆序有2个：32,31； 2和后面的数形成的逆序有1个：21； 1排在最后不产生逆序，故有0个逆序； 于是排列45321的逆序数为：
第一章 行列式
第一节、 第一节、二阶与三阶行列式 第二节、 第二节、排列与逆序数 第三节、线性相关与线性无关 第三节、 第四节、 第四节、行列式的性质 第五节、行列式按行（ 第五节、行列式按行（列）展开 第六节、 第六节、拉普拉斯定理 第七节、 第七节、克莱姆法则
第二节 排列与逆序数
一、排列
1、排列 由n个自然数1,2,…,n组成的一个有序数组：
n(n − 1) = 2

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 . 全体元素的 逆序数之和

定义⒈⒈ ｎ个不同元素所排成的一列，称为（全）排列。 标准(自然排列):ｎ个不同自然数从小到大的排列。 例： 6 3 2, 2 5 1 3 4 2 3 6, 1 2 3 4 5
p1 p2 p3.......... pn , p N , i 1, 2, , n . 定义⒈⒉ 若在排列 p1 p2 ...... pn 中,某两数不是自然顺序
（４）标准排列是偶排列。
定义⒈⒋ 例： 定理⒈⒈
对换：将排列中某两数位置对调，其余数不动。
6372451 对 换 一 次 1372456 偶排列 奇排列
排列经一次对换，奇偶性改变。
推论 （１）：奇（偶）排列调为奇（偶）排列， 须作偶数次对换，奇偶性相同。 （２）：奇（偶）排列调为偶（奇）排列， 须作奇数次对换，奇偶性不同。 （３）：奇（偶）排列调为标准排列， 须作奇（偶）数次对换，标准排列是偶排列。
例1.2，求排列数的逆序数
(1)６３７２４５１ (2)１３７２４５６
(3) 1 2 3 …(n-1)n(2n)(2n-1)…(n+1) 解：(1) 排列 p1 p2 p3 p4 p5 p6 p7 6 3 7 2 4 5 1 τi 0 1 0 3 2 2 6
(6372451) i 14
i
排列的一般记法：
(即前数>后数),则称这两数构成一个逆序。 排列 p1 p2 ..... pn 的逆序总数称为逆序数。 记作：
( p1 p2 p3..... pn)
记 逆序数求法：
i 是pi 前比pi 大的数的个数，则 ( p1 p2 ... pn ) 2 3 ... n (1 0)
1 i 0 0 1 2 (n 1) (n 1)n 2 i 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 表示.

所以
Dn 1
n1 n 2
2
n!.
思考题
分别用两种方法求排列16352487的逆序数.
思考题解答
解 用方法1
1 6 3 5 2 4 8 7
N 0 31 21 01 0 8
用方法2 由前向后求每个数的逆序数.
N 0 0 1 1 3 2 0 1 8.
2的前面比2大的数只有一个3,故逆序数为1;
5的前面没有比5大的数,其逆序数为0; 1的前面比1大的数有3个,故逆序数为3;
4的前面比4大的数有1个,故逆序数为1;
3 2 5 1 4 0 1 0 3 1 于是排列32514的逆序数为
N 32541 0 1 0 3 1 5.
第二节 n 阶行列式
一、排列与逆序
二、n 阶行列式的定义 三、对换
一、排列与逆序
定义1 由自然数 1,2,, n 组成的不重复的每一种有 确定次序的排列, 称为一个 n 级排列（或排列）. 例: 1234和 4213 都是4级排列, 54123和 35142 都是5级排列. 注: n 级排列的总的个数:
2 当 k 为偶数时，排列为偶排列，

k

21 k 1k 1
2 k k ,
当 k 为奇数时，排列为奇排列.
二、n 阶行列式的定义
观察三阶行列式
a11 D a 21 a 31
说明
a12 a 22 a 32
a13 a 23 a11a22a33 a12a23a31 a13a21a32 a a11a23a32 a12a21a33 a13a22a31
解
Dn 1 a1,n1a2 ,n2 an1,1ann

练习：求下列排列的逆序数并讨论其奇偶性． （1） n( n 1) 321 （2） (2n)1(2n 1)2(2n 2)3( n 1)n目录源自上页下页返回
结束
答案:
方法一
n( n 1) (1) ( n 1) ( n 2) 2 1 2 当 n 4k , 4k 1 时为偶排列；
四 、对换
定义: 把一个排列中某两个数的位置互换，而 其余的数不动，得到另一个排列，这一变换 称为一个对换． 将相邻两个元素对调，叫做相邻对换．
目录
上页
下页
返回
结束
定理1 对换改变排列的奇偶性．即经过一次对换， 奇排列变成偶排列，偶排列变成奇排列． 证明: 1) 特殊情形：作相邻对换 设排列为 对换 a 与b a a ba b b a1 al ab b1 bm 1 l 1 m 除 a , b 外，其它元素所成逆序不改变.
上页
下页
返回
结束
b 所成逆序不变;
a1 al a b1 bm b c1 cn
m 次相邻对换
a1 al ab b1 bm c1 cn
m 1 次相邻对换 a a b b b a c c 1 l b 1 m 1 n
a1 al ab1 bm bc1 cn ,
2m 1次相邻对换 a a bb b ac c , 1 l 1 m 1 n
当 n 4k 2, 4k 3 时为奇排列.
方法二
（2） 1 2 n ( n 1) (n 2) 2 1 n( n 1) n( n 1) n2 2 2 当 n 为偶数时为偶排列， 当 n 为奇数时为奇排列.
目录 上页 下页 返回 结束
所以一个排列中的任意两个元素对换，排列改变 奇偶性.

排列与逆序◼概念◼计算(1) 定义例如⚫排列及其逆序数1, 2, 3, 4可组成24=4!个不同的4阶排列.1, 2, …, n 可组成n !个不同的n 阶排列.由1, 2, ···, n 共n 个数码组成的一个有序数组称为一个n 阶排列.在4 阶排列1234 及1324 中，我们规定各元素之间有一个标准在1324 中，n 个不同的自然数，规定由小到大为1234为自然称为标准排列. 3在2之前，称这两个数字构成一个逆序.(2) 定义次序，标准次序.顺序，()n s t i i i i i 21例如定义 3 2 5 1 4逆序逆序逆序t s i i ＞，在一个排列中，则称这两个数组成一个逆序.(3) 排列的逆序数若数排列32514中，逆序逆序⚫逆序数为奇数的排列称为奇排列;⚫逆序数为偶数的排列称为偶排列.排列的奇偶性定义排列的逆序数.一个排列中所有逆序的总数称为此计算排列逆序数的方法分别计算出排列中每个元素前面比它大的数码个数之和，即算出排列中每个元素的逆序数，每个元素的逆序数之总和即为所求排列的逆序数.例1解在排列32514中，3排在首位，2的前面比2大的数只有一个3，于是排列32514 的逆序数为13010++++=t .5=5的前面没有比5大的数，1的前面比1大的数有3个，4的前面比4大的数有1个，求排列32514的逆序数.逆序数为0;故逆序数为1;其逆序数为0;故逆序数为3;故逆序数为1;把一个排列中某两个数字位置互换，例如定义我们把对排列所施行的这种变换排列的奇偶性发生了变化.而其余的数字位置保持不变，就构成了一个53412经过1, 5对换得到13452，τ(5341 2)=3+3+1+1=8, 这时有τ(13452)=3. 新的排列.称为排列的一个对换.一次对换改变排列奇偶性.证明1、相邻对换设…k j … （1）对换k , j 后再设…j k … （2）因为2τ⎧=⎨⎩所以，相邻对换结论成立.11τ−，11τ+，k j <当时，k j >当时；定理2、一般情形因为…k i 1i 2… i s j ……i 1i 2…i s k j ……j i 1i 2…i s k …所以，结论成立.s+1次相邻对换…………推论任何一个n阶排列都可以通过对换化成标准排列，并且所作对换的次数的奇偶性与该排列的奇偶性相同.重新考察二阶、三阶行列式每项的符号，可以得到以下规律：当行标取成标准排列，由列标排列的奇偶性决定每项前的正负号.11122122a a a a =111213212223313233a a a a a a a a a =121212()12(1)j j j j j j a a τ−∑123123123()123(1)j j j j j j j j j a a a τ−∑故二阶、三阶行列式也可以这样写：思考题排列n(n-1)⋯321的逆序数是______(1)2n n −。

的奇偶性， .
而标准排列是
0 )，因此知推论成立
推论2：n元排列中（n>1,n！个排列）奇排列偶排列 各占一半。
计算排列的逆序数的方
法 :
设 p 1 p 2 p n 为 n 个自然数的一个排列，
考虑元素 p i ( i 1、、 n )， 2 p i 前面的元素有 t i 个，
如果比 p i大的且排在
就是说 pi 这个元素的逆序数为t i .
全体元素的逆序数 即是这个排列的逆序数 之和 . t t1 t 2 t n
n 个不同元素的所有排列
的种数，通常用
Pn 表示 .
Pn n ( n 1) 3 2 1 n!
例1 求排列32514的逆序数. 解 在排列32514中， 3排在首位，逆序数为 0； 2前面比2大的数有一个（3），故逆序数为1； 5是最大数，逆序数为 0； 1前面比1大的数有三个（3、2、5）,故逆序数为3； 4前面比4大的数有一个（5），故逆序数为1； 于是这个排列的逆序数为 ( 32514 ) 0 1 0 3 1 5 .
解
n 1 n ( n 1 )( n 2 ) 321 n 2

t ( n 1) ( n 2 ) 2 1
n( n 1) 2
,
当 n 4k ,
4 k 1时为偶排列，
4 k 3时为奇排列 .
ti ,
i1
n
例2 计算下列排列的逆序数，并讨论它们的 奇偶性.
(1 ) 217986354 ;
解
2 1 7 9 8 6 3 5 4
0 1 0 0 1 3 4 4 5
t ( 217986354 )

逆序
例如 排列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 全排列及其逆序数
一、全排列 二、排列逆序数 三、小结

在一个 n 阶排列中,任何一个数对不是构成 逆序就是构成顺序.如果我们把顺序的个数称为顺
序数, 则一个 n 阶排列的顺序数与逆序数的和为
n(n -1)/2. 逆序数为奇数的排列叫做奇排列,逆序数为偶 数的排列叫做偶排列.
2. 计算方法
下面来讨论计算排列的逆序数的方法. 不失一般性，不妨设 n 个元素为 1 至 次序. 设
二、全排列
对于 n 个不同的元素，也可以提出类似的问
题： 把 n 个不同的元素排成一列，共有几种不同
的排法？ 为此先给出全排列的定义.
定义 把 n 个不同的元素排成一列，叫做这
n 个元素的全排列（也简称排列）.
n 个不同元素的所有排列的种数，通常用 Pn 表
的结果可知 P3 = 3 · · = 6. 2 1 示. 由 引例 用1，2，3三个数字可以组成多少个没
例 4 求排列
32541
的逆序数.
求逆序数模型
本模型最多只能处理9个元素 请在下列输入框中输入互不相等
5 2 8 7 1 4 9 6 3
计 算
清 空
本节内容已结束 ! 本节内容已结束 ! ! ! ! 本节内容已结束 本节内容已结束 本节内容已结束 ! 本节内容已结束 若想结束本堂课, ! 本节内容已结束 若想结束本堂课, 若想结束本堂课, 若想结束本堂课, ! 本节内容已结束 若想结束本堂课, ! 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 请单击返回按钮. 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 若想结束本堂课, ! 请单击返回按钮. 本节内容已结束 ! 若想结束本堂课, 请单击返回按钮. 本节内容已结束 若想结束本堂课, 请单击返回按钮. 若想结束本堂课, 请单击返回按钮. 若想结束本堂课, 请单击返回按钮. 若想结束本堂课, 请单击返回按钮. 请单击返回按钮. 请单击返回按钮. 请单击返回按钮.

4的前面比4大的数有1个,故逆序数为1; 32514 01 031
于是排列32514的逆序数为 t 0 1 0 3 1 5.
例2 计算下列排列的逆序数，并讨论它们的奇 偶性.
1 7986354
解
217986354
0 10 0 1 3 4 4 5
t 5 4 4310010
18
此排列为偶排列.
i1 前面比i1 大的数码个数； i1 i 2 i n
向前看大 向后看小
③ i1 后面比i1 小的数码个数 i2 后面比i2 小的数码个数
in 后面比in 小的数码个数； i1 i 2 in
向后看小 向前看大
例1 求排列32514的逆序数.
解 在排列32514中, 3排在首位,逆序数为0; 2的前面比2大的数只有一个3,故逆序数为1; 5的前面没有比5大的数,其逆序数为0; 1的前面比1大的数有3个,故逆序数为3;
分别用两种方法求排列16352487的逆序数.
思考题解答
解 用方法1 1 63 5 2 4 8 7 t 03121010 8
用方法2 由前向后求每个数的逆序数. t 0 0 1 1 3 2 0 1 8.
2 nn 1n 2321
解 n1
nn1n 2321 n 2
t n 1 n 2 2 1 nn 1,
2 当 n 4k ,4k 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
01 1 2 2
k
t 0 1 1 2 2 k 1 k 1 k
21 k 1k 1 k k 2,

§ 2 全排列及其逆序数一、全排列个不同元素排成一列。

可将个不同元素按1~ 进行编号，则个不同元素的全排列可看成这个自然数的全排列。

个不同元素的全排列共有种。

逆序的定义：取一个排列为标准排列，其它排列中某两个元素的次序与标准排列中这两个元素的次序相反时，则称这两个元素构成一个逆序。

通常取从小到大的排列为标准排列，即 1~ 的全排列中取123 为标准排列。

二、逆序及逆序数逆序数的定义：一个排列的逆序数的总数称为逆序数。

逆序数为偶数称为偶排列，逆序数为奇数称为奇排列，标准排列规定为偶排列。

逆序数的计算：设为的一个全排列，则其逆序数为其中为排在前，且比大的数的个数。

例：求的逆序数。

解：，逆序数算法在网上看了很多用mergesort求逆序数的代码，发觉很多都不太对，主要是在merge时求本次merge是前后两部分的逆序数过程，其实merge时由于前后两部分都是已经排好序的，假设merge的两个数组分别为a[n1],b[n2],合并时的逆序数就应该=b中所有小于a[1]的个数，小于a[2]的个数，小于a[3]的个数...小于a[n1]的个数之和=a中所有大于b[1]的个数，大于b[2]的个数，大于b[3]的个数...大于b[n2-1]的个数之和。

因此对于此次合并逆序数的个数有两种计算方法，一是以a中元素作为判断来计算，一是以b中元素作为判断来计算。

以a中元素作为为例：计算过程为，每当把a中某一个元素a[i]插入合并后的数组中时，计算b中已经插入合并后的数组中的元素个数ki，把这些所有的ki加起来即为本次合并的逆序数，具体的代码如下其中的iversion为逆序数。

int inversion=0;void merge(int* a,int p,int q,int r){int n1=r-p+1;int n2=q-r;int i,j,k;k=0;int *tmp=new int[n1+n2];for(i=p,j=r+1;i<=r&&j<=q;){if(a[i]<=a[j]){tmp[k]=a[i];inversion+=j-r;i++;k++;}else{tmp[k]=a[j];j++;k++;}}while(i<=r){tmp[k++]=a[i++];inversion+=q-r;}while(j<=q){tmp[k++]=a[j++];}for(i=p;i<=q;i++)a[i]=tmp[i-p];delete [] tmp;}如果所有人是线性排列,那我们的工作就是类似冒泡程序做的工作,,1,2,3,4,5变为5,4,3,2,1 ,耗时n(n-1)/2但是出现了环,也就是说1,2,3,4,5变为3,2,1,5,4也可满足条件我们可以把这个环等分成两个部分,每个部分看成是线性的,再把它们花的时间加起来. 当n是偶数时, 每份人数n/2 ,即(n/2-1)*(n/2)*2当n是偶数时,两份的人数分别是n/2和n-n/2,即(n/2-1)*(n/2)+ ((n-n/2)-1)*(n-n/2)/2*/int main(){int t,n,i,r,s;cin>>t;while(t--){cin>>n;if(n%2==0){r=n/2;s=(n/2-1)*(n/2);}else{r=n/2;n=n-r;s=(r-1)*r/2+(n-1)*n/2;}cout<<s<<endl;}return 0;}若是线形无环，将1-n变为n-1，求逆序数n*(n-1)/2即可(线性代数)但本题由于是环，则在1-n中取一k，将1-n 变为形如k-1，n-(k+1)也可满足条件，比如1,2,3,4,5变为3,2,1,5,4也可满足条件。

例1 求排列45321旳逆序数. 解 在排列45321中,
4排在首位,逆序数为0; 5是最大数，故逆序数为0;
3旳前面比3大旳数有两个:4 , 5 ,故逆序数为2; 2旳前面比2大旳数有三个:4 , 5 , 3,故逆序数为3; 1旳前面比1大旳数有4个:4,5,3,2,故逆序数为4.
453 21
00 2 34
t n 1 n 2 2 1 nn 1,
2 当 n 4k,4k 1 时为偶排列；
当 n 4k 2,4k 3 时为奇排列.
三、对换旳定义
定义 在排列中，将任意两个元素对调，其他 元素不动，这种作出新排列旳手续叫做 对换． 将相邻两个元素对调，叫做相邻对换．
例如
a1 al a bb b1 bm a1alaa b1bm b c1cn a1 al bb aa b1 bm a1al b b1bm a c1cn
四、对换与排列旳奇偶性旳关系
定理1 一种排列中旳任意两个元素对换，排列 变化奇偶性． 证明 略
推论 奇排列调成原则排列旳对换次数为奇数， 偶排列调成原则排列旳对换次数为偶数.
证明 由定理1知对换旳次数就是排列奇偶性旳
变化次数, 而原则排列是偶排列(逆序数为0),所以 知推论成立.
于是排列45321旳逆序数为
t 0 0 2 3 4 9.
例2 计算下列排列旳逆序数，并讨论它们旳奇 偶性.
1 217986354
解
217986354
0 10 0 1 3 4 4 5
t 5 4 4310010
18
此排列为偶排列.
2 nn 1n 2321
解 n1
nn1n 2321 n 2
措施1
分别计算出排在1,2, ,n 1,n前面比它大旳数 码个数即分别算出 1,2, ,n 1,n 这 n个元素

b 经对换后 a 的逆序数不变 ， 的逆序数减少1.
因此对换相邻两个元素，排列改变奇偶性. 设排列为 a1 al ab1 bm bc1 cn 现来对换 a 与 b .
a1 al a b1 bm b c1 cn
m 次相邻对换
a1 al ab b1 bm c1 cn
m 1 次相邻对换 a a b b b a c c 1 l 1 m a 1 n
的逆序数.
例如
排列32514 中，
0
0
1
3 2 5 1 4
1
逆序数为3
故此排列的逆序数为3+1+0+1+0=5.
例 1、用多种方法求排列16352487的逆序数. 2、 t (i1i2 in ) 的取值范围？ 3、求n(n-1) …21的逆序数。 4、若 ( i1i2 in ) t 求 ( in i2i1 )
对换与排列的奇偶性的关系
定理1 一个排列中的任意两个元素对换，排列 改变奇偶性． 证明 设排列为
对换 a 与 b
a1 al ab b1 bm
a1 al ba b1 bm ba
除 a , b 外，其它元素的逆序数不改变.
当 a b时，
经对换后 a 的逆序数增加1 ,
当 a b时，
b 的逆序数不变;
四、小结
1 n 个不同的元素的所有排列种数为 n!. 2 排列具有奇偶性. 3 计算排列逆序数常用的方法有多种. 4 对换改变排列的奇偶性.
计算法的本质：
本质为计算排列中的每一元与其前面的元
所产生的逆序数，然后逐个相加，即得排 列的逆序数。各种方法的区别在于计算排 列中每一元的逆序数的顺序，第一种方法 是按元本身从小到大计算，而第二种方法 是按元后在的位置从右往左计算。