文档介绍：§2全排列及其逆序数问题把 n 个不同的元素排成一列,共有多少种不同的排法? 定义把 n 个不同的元素排成一列,叫做这 n 个元素的全排列. n 个不同元素的所有排列的种数,通常用 P n表示. ( 1) ( 2) 3 2 1 ! n P n n n n ? ????????即 n 个不同的元素一共有 n ! 种不同的排法. 2.???????(1) ?????? 1,2, …,n,????????? i 1i 2…i n ???? n???.所有 6种不同的排法中,只有一种排法( 123 ) 中的数字是按从小到大的自然顺序排列的, 而其他排列中都有大的数排在小的数之前. 因此大部分的排列都不是“顺序”,而是“逆序”. 3个不同的元素一共有 3! =6 种不同的排法 123 ,132 ,213 ,231 ,312 ,321 对于 n 个不同的元素,可规定各元素之间的标准次序. n 个不同的自然数,规定从小到大为标准次序. 定义当某两个元素的先后次序与标准次序不同时,就称这两个元素组成一个逆序. 例如在排列 32514 中, 3 2 5 1 4 逆序逆序逆序思考题: 还能找到其它逆序吗? 答: 2和1,3和1也构成逆序. 定义排列中所有逆序的总数称为此排列的逆序数. 排列 i 1i 2 …i n的逆序数通常记为 t ( i 1i 2…i n ) . 奇排列: 逆序数为奇数的排列. 偶排列: 逆序数为偶数的排列. 思考题: 符合标准次序的排列是奇排列还是偶排列? 答: 符合标准次序的排列(例如: 123 )的逆序数等于零,因而是偶排列. 计算排列的逆序数的方法则此排列的逆序数为 1 2 n t t t t ? ????设p 1p 2 …p n是1, 2, …, n 这 n 个自然数的任一排列,并规定由小到大为标准次序. 先看有多少个比 p 1大的数排在 p 1前面,记为 t 1; 再看有多少个比 p 2大的数排在 p 2前面,记为 t 2; ……最后看有多少个比 p n大的数排在 p n前面,记为 t n; 例1:求排列 32514 : (32514) 0 1 0 3 1 5 t ? ?????练****求排列 453162 的逆序数. 9t?解: 8 ?对换: ????? i 1…i s…i t…i n????????i s?i t????, ?????????????? i 1…i t…i s…i n,??????????, ??( i si t ). ?6 )43 (1243 ?0125????????)31 (3421 ?)42 (1423 ? 1234 ??????????????.????? n???????? 12…n????????????. 9 ?????对换在相邻两数间发生,即设排列… jk… (1) 经j,k对换变成…kj… (2) 此时,排列(1) 、(2) 中j,k与其他数是否构成逆序的情形未发生变化;而 j与k两数构成逆序的情形有变化: 若(1) 中 jk构成逆序,则(2) 中不构成逆序(逆序数减少 1) 若(1) 中 jk不构成逆序,则(2) 中构成逆序(逆序数增加 1) ?一般情形设排列… ji 1…i sk… (3) 经j,k对换变成…k i 1…i s j… (4) 易知, (4) 可由(3) 经一系列相邻对换得到: k经 s+1 次相邻对换成为… kj i 1…i s… j 经s次相邻对换成为…ki 1…i s j …即经 2s+1 次相邻对换后(3) 成为(4). 相邻对换改变排列的奇偶性,奇数次这样的对换后排列的奇偶性改变. || 10 ???????????? 1.?(542163) ?(24 …(2n-2)(2n)(2n-1)(2n-3) …31) 2. 若排列的 x 1x 2…x n逆序数为 I,求排列 x nx n-1…x 1的逆序数. .I2 )1()(.2 )12(31)2( 9)1(.1 11 2?????????nnxxx nn nn?????详解继续