文档介绍：§2 全排列及其逆序数
问题把 n 个不同的元素排成一列,共有多少种不同的排法?
定义把 n 个不同的元素排成一列,叫做这 n 个元素的全排列. n 个不同元素的所有排列的种数,通常用Pn 表示.
即n 个不同的元素一共有n! 种不同的排法.
(1)排列
由自然数1,2,…,n,组成的一个有序数组i1i2…in
称为一个n级排列.
所有6种不同的排法中,只有一种排法(123)中的数字是按从小到大的自然顺序排列的,而其他排列中都有大的数排在小的数之前.
因此大部分的排列都不是“顺序”,而是“逆序”.
3个不同的元素一共有3! =6种不同的排法
123,132,213,231,312,321
对于n 个不同的元素,可规定各元素之间的标准次序.
n 个不同的自然数,规定从小到大为标准次序.
定义当某两个元素的先后次序与标准次序不同时,就称
这两个元素组成一个逆序.
例如在排列32514中,
3 2 5 1 4
逆序
逆序
逆序
思考题:还能找到其它逆序吗?
答:2和1,3和1也构成逆序.
定义排列中所有逆序的总数称为此排列的逆序数.
排列 i1i2 … in 的逆序数通常记为 t ( i1i2…in ) .
奇排列:逆序数为奇数的排列.
偶排列:逆序数为偶数的排列.
思考题:符合标准次序的排列是奇排列还是偶排列?
答:符合标准次序的排列(例如:123)的逆序数等于零,因而是偶排列.
计算排列的逆序数的方法
则此排列的逆序数为
设 p1p2 … pn 是 1, 2, …, n 这 n 个自然数的任一排列,并规定由小到大为标准次序.
先看有多少个比 p1大的数排在 p1前面,记为 t1 ;
再看有多少个比 p2大的数排在 p2前面,记为 t2 ;
……
最后看有多少个比 pn大的数排在 pn前面,记为 tn ;
例1:
求排列 32514 的逆序数.
解:
练****br/>求排列 453162 的逆序数.
解:
8
对换:
在一个排列i1…is…it …in中,若其中某两
数is和it互换位置, 其余各数位置不变得到另一排列
i1…it…is …in,这种变换称为一个对换, 记为( isit).
例6
结论:
①对换改变排列的奇偶性.
②任意一个n级排列与标准排列12…n都可以经过一
系列对换互变.
9
①的证明
对换在相邻两数间发生,即
设排列…jk…(1) 经j,k对换变成…kj…(2)
此时,排列(1)、(2)中j,k与其他数是否构成逆序的情形未
发生变化;而j与k两数构成逆序的情形有变化:
若(1)中jk构成逆序,则(2)中不构成逆序(逆序数减少1)
若(1)中jk不构成逆序,则(2)中构成逆序(逆序数增加1)
一般情形
设排列…ji1…isk…(3) 经j,k对换变成…k i1…is j…(4)
易知,(4)可由(3)经一系列相邻对换得到:
k经s+1次相邻对换成为…kj i1…is …
j经s次相邻对换成为…ki1…is j …
即经2s+1次相邻对换后(3) 成为(4). 相邻对换改变排列的奇偶
性,奇数次这样的对换后排列的奇偶性改变. ||
10
思考练****排列的逆序数)
1.(542163) (24…(2n-2)(2n)(2n-1)(2n-3)…31)
2. 若排列的x1x2…xn逆序数为I,求排列xn xn-1…x1的逆序数.
答
案
详解
继续