课堂练习： P31 1.11.2
课堂练习： P31 1.1 1.2
二.排列与逆序 定义1：由自然数1,2，.，n组成的一个有序数组 称为一个n元排列。 例如：1,2,3,4,5 5,1,2,3,4都是数1,2,3,4,5的一个排列。 5,3,2,1,4 考虑：n个数的不同排列有n!个。 自然排列：按数的大小次序，由小到大排列。 考虑：元排列中，自然排列只有一种 除此之外，任一元排列都一定出现较大数码 排在较小数码之前的情况
二. 排列与逆序 定义1：由自然数1，2，······，n 组成的一个有序数组 称为一个n 元排列。 例如： 1，2，3，4，5 5，1，2，3，4 5，3，2，1，4 都是数1，2，3，4，5的一个排列。 考虑：n个数的不同排列有 n ! 个。 自然排列： 按数的大小次序，由小到大排列。 考虑：n元排列中，自然排列只有一种 除此之外，任一n元排列都一定出现较大数码 排在较小数码之前的情况
定义2：在一个排列中，若某个较大的数排在某个较小的 数前面，就称这两个数构成一个逆序。 一个排列中出现的逆序的总数称为这个排列的 逆序数 通常记为x(i,i2,.,n) 奇排列：逆序数为奇数的排列。 偶排列：逆序数为偶数的排列
定义2： 在一个排列中，若某个较大的数排在某个较小的 数前面，就称这两个数构成一个逆序。 一个排列中出现的逆序的总数称为这个排列的 奇排列： 逆序数为奇数的排列。 偶排列： 逆序数为偶数的排列。 ( , , , ) 1 2 n 逆序数 通常记为 i i i
计算排列的逆序数的方法： 法1：个数的任一n元排列，先看数1，看有多少个比1大的数 排在1前面，记为m; 再看有多少个比2大的数排在2前面，记为m,; 继续下去，最后至数n,前面比n大的数显然没有， 记为mn=0; 则此排列的逆序数为T=m,+m2+.+m
计算排列的逆序数的方法： 法1：n个数的任一n元排列，先看数1，看有多少个比1大的数 排在1前面，记为 ; m1 再看有多少个比2大的数排在2前面，记为 ; m2 继续下去，最后至数n，前面比n大的数显然没有， = 0 ; 记为 m n 则此排列的逆序数为 = m1 + m2 ++ m n
法2：n元排列i,i,.,in的逆序数 (,i,.,in)=数i后面比i小的数的个数 +数i,后面比i,小的数的个数 十·。 +数i,后面比i小的数的个数 法3：(i,2,.,i)=数in前面比i,大的数的个数 +数i,前面比i,大的数的个数 十 +数i,前面比i,大的数的个数
法2： n 元排列 n i ,i , ,i 1 2 的逆序数 (i 1 ,i 2 , ,i n ) = 数i 1 后面比i 1 小的数的个数 + 数i 2 后面比i 2 小的数的个数 + + 数 i n−1 后面比i n−1 小的数的个数 法3： (i 1 ,i 2 , ,i n ) = 数 i n 前面比i n 大的数的个数 + 数 i n−1 前面比i n−1 大的数的个数 + + 数i 2 前面比i 2 大的数的个数