求排列的逆序数两种思路 [方法一] 排列中比每一元素P大的且排在P:前面的元素个数 的总和T=T1+T2+…+Tm,即是这个排列的逆序数。 [方法二] 排列中比每一元素p:小的且排在p:后面的元素个数 ;的总和t=1十t2+…+Tn,也是这个排列的逆序数。 例如：求(32145) 【法一】 【法二】 3 2 1 4 5 3 2 1 4 5 ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 2 0 2 1 0 x(32145) =3 (3 2145) =3
求排列的逆序数两种思路 排列中比每一元素 pi 大的且排在 前面的元素个数 i τ 1 2 n 的总和 ττ τ τ =+++ ，即是这个排列的逆序数。 i p [方法一] 排列中比每一元素 小的且排在 后面的元素个数 的总和 ，也是这个排列的逆序数。 i p i p i τ 1 2 n ττ τ τ =+++ [方法二] 例如：求 τ（32145） 32145 01200 τ 32145 3 ↓↓↓↓↓ ∴ 【法一】 （ ）＝ 32145 21000 τ 32145 3 ↓↓↓↓↓ ∴ 【法二】 （ ）＝
排列的奇偶性 逆序数为奇数的排列称为奇排列； 逆序数为偶数的排列称为偶排列 [注]逆序数为0称作偶排列，例如：t(123.n): 例4计算下列排列的逆序数，并讨论它们的奇偶性 1) 217986354 解：21 7 9 8 6 3 5 4 0 ↓ ↓ ↓ 3 4 4 5 x=5+4+4+3+1+0+0+1+0=18 故此排列为偶排列
逆序数为奇数的排列称为奇排列； 逆序数为偶数的排列称为偶排列. 排列的奇偶性 例4 计算下列排列的逆序数，并讨论它们的奇偶性. 1） ２１７９８６３５４ +4 解： τ = 5 = 18 故此排列为偶排列. + 4 + 3 + 1 + 0 + 0 + 1 + 0 2 1 7 9 8 6 3 5 4 0 1 0 0 1 3 4 4 5 [注] 逆序数为0称作偶排列, 例如: . τ (123...n)
2)(n-1)(n-2)…321 : 解 01 n-3n-2n- t=(n-1)+(n-2)+…+2+1= n(n-1) 2 当n=4k,4k+1 时为偶排列； 当n=4k+2,4k+3时为奇排列. 3)(2k)1(2k-1)2(2k-2)3(2k-3)…(k+1)k (k为自然数) 解(2k)(2k-)2(2k-2)3(2k-3)(k+1)k 。。k-1 T=k2 当k为偶数时，该排列为偶排列； 当k为奇数时，该排列为奇排列
当 n = 4k,4k + 1 时为偶排列； 当 n = 4k + 2,4k + 3时为奇排列. ( 1) 2 1 2 n n − τ = − (n 1) + (n − 2) + ++= 解 nn n ( − − 1 23 2 1 )( ) 0 1 2 n − 3 n − 2 n − 1 2） nn n ( − − 1 2 321 )( ) 解 (2 12 122 232 3 1 kk k k kk ) ( −− −+ ) ( ) ( )( ) ↓ 0 ↓ 1 ↓ 1 ↓ 2 ↓ 2 ↓ k 1 k ↓ − 2 τ = k 当 k 为奇数时，该排列为奇排列. 当 k 为偶数时，该排列为偶排列； 3） (2 12 122 232 3 1 kk k k kk ) ( −− −+ ) ( ) ( )( ) （k为自然数）
对换 1、定义 在一个排列中，将某两个数4，b对调，其余各 数位置不变，这样的变换称为一个对换，记为(，b). 特别：将相邻两个元素对调，叫做相邻对换 例如 a1…,abb1…bnm 1) a,…a,bab…bm 01…4ab1…bmbC1…Cm 2) 41…a,bb…bnaG…c
特别：将相邻两个元素对调，叫做相邻对换. 1、定义 对 换 在一个排列中，将某两个数a,b对调，其余各 数位置不变，这样的变换称为一个对换,记为(a,b). 例如 aa bb 1 1 l m a b aa bb 1 1 l m b a 11 1 lmn aabb c a b c 11 1 lm n a ab b c b a c 1） 2）
2.对换与排列奇偶性的关系 定理1任意一个排列经过一次对换后，改变奇偶性. 证明 1°相邻两个数对换 41…4abb…bn Ca,b）,…,bab…bm 除，b外，其它元素的逆序数不改变， 结论 对换相邻两个元素，排列改变奇偶性
定理1 任意一个排列经过一次对换后，改变奇偶性． 证明 1°相邻两个数对换 除 a,b 外，其它元素的逆序数不改变. 2．对换与排列奇偶性的关系 l m a a ab b b 1 1 a b l m a a ba b b 1 1 ab ba （ ， ） 结论 对换相邻两个元素，排列改变奇偶性